Espaço para bicicletas - Cycle space

Na teoria dos grafos , um ramo da matemática, o espaço do ciclo (binário) de um gráfico não direcionado é o conjunto de seus subgráficos de graus pares .

Este conjunto de subgráficos pode ser descrito algebricamente como um espaço vetorial sobre o campo finito de dois elementos . A dimensão deste espaço é a classificação do circuito do gráfico. O mesmo espaço também pode ser descrito em termos da topologia algébrica como o primeiro grupo de homologia do gráfico. Usando a teoria da homologia, o espaço do ciclo binário pode ser generalizado para espaços do ciclo sobre anéis arbitrários .

Definições

Teoria dos grafos

Um grafo parcial de um dado gráfico G pode ser definido a partir de qualquer subconjunto S das bordas de L . O subgrafo tem o mesmo conjunto de vértices que o próprio G (este é o significado da palavra "spanning"), mas tem os elementos de S como suas arestas. Assim, um gráfico G com m bordas tem 2 ^m abrangendo subgráficos, incluindo L em si, bem como o gráfico vazio sobre o mesmo conjunto de vértices como L . A colecção de todas as subgráficos abrangendo de um gráfico L forma o espaço de borda de L .

Um grafo G , ou um de seus subgráficos, é considerado euleriano se cada um de seus vértices tiver um número par de arestas incidentes (esse número é chamado de grau do vértice). Esta propriedade tem o nome de Leonhard Euler que provou em 1736, em seu trabalho sobre as Sete Pontes de Königsberg , que um gráfico conectado tem um passeio que visita cada borda exatamente uma vez se e somente se for Euleriana. No entanto, um subgrafo Euleriano não precisa ser conectado; por exemplo, o gráfico vazio, no qual todos os vértices estão desconectados uns dos outros, é euleriano. O espaço do ciclo de um gráfico é a coleção de seus subgráficos abrangentes de Euler.

Álgebra

Se alguém aplicar qualquer operação de conjunto , como união ou interseção de conjuntos, a dois subgráficos abrangentes de um determinado gráfico, o resultado será novamente um subgráfico. Desta forma, o espaço de borda de um gráfico arbitrário pode ser interpretado como uma álgebra booleana .

A diferença simétrica de dois subgráficos Eulerianos (vermelho e verde) é um subgráfico Euleriano (azul).

O espaço do ciclo, também, tem uma estrutura algébrica, mas mais restritiva. A união ou interseção de dois subgráficos Eulerianos pode não ser Euleriana. No entanto, a diferença simétrica de dois subgráficos Eulerianos (o gráfico que consiste nas arestas que pertencem a exatamente um dos dois gráficos dados) é novamente Euleriana. Isso decorre do fato de que a diferença simétrica de dois conjuntos com um número par de elementos também é par. Aplicar este fato separadamente às vizinhanças de cada vértice mostra que o operador diferença simétrica preserva a propriedade de ser euleriano.

Uma família de conjuntos fechados sob a operação de diferença simétrica pode ser descrita algebricamente como um espaço vetorial sobre o corpo finito de dois elementos . Este campo tem dois elementos, 0 e 1, e suas operações de adição e multiplicação podem ser descritas como a adição e multiplicação familiares de inteiros , considerados o módulo 2 . Um espaço vetorial consiste em um conjunto de elementos junto com uma operação de adição e multiplicação escalar que satisfaz certas propriedades que generalizam as propriedades dos espaços vetoriais reais familiares ; para o espaço do ciclo, os elementos do espaço vetorial são os subgráficos eulerianos, a operação de adição é a diferenciação simétrica, a multiplicação pelo escalar 1 é a operação de identidade e a multiplicação pelo escalar 0 leva todos os elementos para o gráfico vazio, que forma o elemento de identidade aditivo para o espaço do ciclo. ${\ displaystyle \ mathbb {Z} _ {2}}$

O espaço da aresta também é um espaço vetorial se usarmos a diferença simétrica como adição. Como espaços vetoriais, o espaço do ciclo e o espaço de corte do gráfico (a família de conjuntos de arestas que abrangem os cortes do gráfico) são os complementos ortogonais um do outro dentro do espaço de aresta. Isso significa que um conjunto de arestas em um gráfico forma um corte se e somente se cada subgrafo Euleriano tem um número par de arestas em comum com , e forma um subgrafo Euleriano se e somente se cada corte tem um número par de arestas em comum com . Embora esses dois espaços sejam complementos ortogonais, alguns gráficos possuem subgráficos não vazios que pertencem a ambos. Tal subgrafo (um corte Euleriano) existe como parte de um grafo se e somente se tem um numero par de florestas abrangentes . ${\ displaystyle \ mathbb {Z} _ {2}}$${\ displaystyle S}$${\ displaystyle S}$${\ displaystyle S}$${\ displaystyle S}$${\ displaystyle G}$${\ displaystyle G}$

Topologia

Um gráfico não direcionado pode ser visto como um complexo simplicial com seus vértices como simplicidade zero-dimensional e as bordas como simplicidade unidimensional. O complexo de cadeia deste espaço topológico consiste em seu espaço de aresta e espaço de vértice (a álgebra booleana de conjuntos de vértices), conectados por um operador de fronteira que mapeia qualquer subgrafo de abrangência (um elemento do espaço de aresta) para seu conjunto de graus ímpares vértices (um elemento do espaço do vértice). O grupo de homologia

${\ displaystyle H_ {1} (G, \ mathbb {Z} _ {2})}$

consiste nos elementos do espaço da borda que mapeiam para o elemento zero do espaço do vértice; esses são exatamente os subgráficos de Euler. Sua operação de grupo é a operação de diferença simétrica em subgráficos Eulerianos.

A substituição nesta construção por um anel arbitrário permite a definição de espaços cíclicos a serem estendidos a espaços cíclicos com coeficientes no anel dado, que formam módulos sobre o anel. Em particular, o espaço do ciclo integral é o espaço ${\ displaystyle \ mathbb {Z} _ {2}}$

${\ displaystyle H_ {1} (G, \ mathbb {Z}).}$

Pode ser definido em termos teóricos de grafos escolhendo uma orientação arbitrária do grafo e definindo um ciclo integral de um grafo como uma atribuição de inteiros às arestas de (um elemento do grupo abeliano livre nas arestas) com a propriedade que, em cada vértice, a soma dos números atribuídos às arestas de entrada é igual à soma dos números atribuídos às arestas de saída. ${\ displaystyle G}$${\ displaystyle G}$

Um membro de ou de (o módulo do espaço do ciclo ) com a propriedade adicional de que todos os números atribuídos às arestas são diferentes de zero é chamado de fluxo em lugar nenhum ou fluxo em lugar nenhum . ${\ displaystyle H_ {1} (G, \ mathbb {Z})}$${\ displaystyle H_ {1} (G, \ mathbb {Z} _ {k})}$${\ displaystyle k}$${\ displaystyle k}$

Classificação do circuito

Como um espaço vetorial, a dimensão do espaço do ciclo de um gráfico com vértices, arestas e componentes conectados é . Este número pode ser interpretado topologicamente como o primeiro número de Betti do gráfico. Na teoria dos gráficos, é conhecido como classificação do circuito , número ciclomático ou nulidade do gráfico. ${\ displaystyle n}$${\ displaystyle m}$${\ displaystyle c}$ ${\ displaystyle m-n + c}$

Combinar esta fórmula para a classificação com o fato de que o espaço do ciclo é um espaço vetorial sobre o campo de dois elementos mostra que o número total de elementos no espaço do ciclo é exatamente . ${\ displaystyle 2 ^ {m-n + c}}$

Bases de ciclo

Uma base de um espaço vetorial é um subconjunto mínimo de elementos com a propriedade de que todos os outros elementos podem ser escritos como uma combinação linear de elementos de base. Cada base de um espaço de dimensão finita tem o mesmo número de elementos, que é igual à dimensão do espaço. No caso do espaço do ciclo, uma base é uma família de subgráficos exatamente Eulerianos, com a propriedade de que cada subgrafo Euleriano pode ser escrito como a diferença simétrica de uma família de elementos de base. ${\ displaystyle m-n + c}$

Existência

Pelo teorema de Veblen , cada subgrafo Euleriano de um dado grafo pode ser decomposto em ciclos simples , subgráficos nos quais todos os vértices têm grau zero ou dois e nos quais os vértices de grau dois formam um conjunto conectado. Portanto, é sempre possível encontrar uma base em que os elementos básicos sejam, eles próprios, ciclos simples. Essa base é chamada de base de ciclo do gráfico fornecido. Mais fortemente, é sempre possível encontrar uma base na qual os elementos de base são ciclos induzidos ou mesmo (em um gráfico conectado a 3 vértices ) ciclos induzidos cuja remoção não separa o gráfico restante.

Bases fundamentais e fracamente fundamentais

Uma forma de construir uma base de ciclo é formar uma floresta abrangente do gráfico e, então, para cada aresta que não pertence à floresta, formar um ciclo que consiste em junto com o caminho na floresta conectando os pontos finais de  . O conjunto de ciclos formado desta forma é linearmente independente (cada um contém uma aresta que não pertence a nenhum dos outros ciclos) e tem o tamanho correto para ser uma base, portanto é necessariamente uma base. Uma base formada dessa maneira é chamada de base de ciclo fundamental . ${\ displaystyle e}$${\ displaystyle C_ {e}}$${\ displaystyle e}$${\ displaystyle e}$${\ displaystyle C_ {e}}$${\ displaystyle e}$${\ displaystyle m-n + c}$

Se houver uma ordenação linear dos ciclos em uma base de ciclo de modo que cada ciclo inclua pelo menos uma aresta que não faz parte de nenhum ciclo anterior, então a base de ciclo é chamada de fundamentalmente fraca . Cada base de ciclo fundamental é fracamente fundamental (para todas as ordenações lineares), mas não necessariamente vice-versa. Existem gráficos e bases de ciclo para esses gráficos que não são fracamente fundamentais.

Bases de peso mínimo

Se as arestas de um gráfico recebem pesos de números reais, o peso de um subgrafo pode ser calculado como a soma dos pesos de suas arestas. A base de peso mínimo do espaço do ciclo é necessariamente uma base do ciclo e pode ser construída em tempo polinomial. A base de peso mínimo nem sempre é fundamentalmente fraca, e quando não é NP-difícil encontrar a base fundamental fraca com o peso mínimo possível.

Gráficos planos

Homologia

Se um gráfico planar estiver embutido no plano, seu complexo de cadeia de arestas e vértices pode ser embutido em um complexo de cadeia dimensional superior que também inclui os conjuntos de faces do gráfico. O mapa de fronteira deste complexo de cadeia leva qualquer 2-cadeia (um conjunto de faces) para o conjunto de arestas que pertencem a um número ímpar de faces na 2-cadeia. O limite de uma cadeia 2 é necessariamente um subgrafo Euleriano, e todo subgrafo Euleriano pode ser gerado dessa maneira a partir de exatamente duas cadeias 2 diferentes (cada uma das quais é o complemento da outra). Segue-se disso que o conjunto de faces limitadas do embedding forma uma base de ciclo para o gráfico planar: remover a face ilimitada desse conjunto de ciclos reduz o número de maneiras pelas quais cada subgrafo Euleriano pode ser gerado de dois para exatamente um.

Critério de planaridade de Mac Lane

O critério de planaridade de Mac Lane , em homenagem a Saunders Mac Lane , caracteriza os gráficos planares em termos de seus espaços e bases de ciclo. Ele afirma que um grafo não direcionado finito é planar se e somente se o grafo tem uma base de ciclo na qual cada aresta do grafo participa de no máximo dois ciclos de base. Em um grafo plano, uma base de ciclo formada pelo conjunto de faces limitadas de um embedding tem necessariamente esta propriedade: cada aresta participa apenas dos ciclos de base para as duas faces que separa. Por outro lado, se uma base de ciclo tem no máximo dois ciclos por aresta, então seus ciclos podem ser usados ​​como o conjunto de faces limitadas de uma incorporação plana de seu gráfico.

Dualidade

O espaço de ciclo de um gráfico plano é o espaço de corte de seu gráfico dual e vice-versa. A base do ciclo de peso mínimo para um gráfico planar não é necessariamente a mesma que a base formada por suas faces limitadas: ela pode incluir ciclos que não são faces e algumas faces podem não ser incluídas como ciclos na base do ciclo de peso mínimo. Existe uma base de ciclo de peso mínimo na qual dois ciclos não se cruzam: para cada dois ciclos na base, ou os ciclos encerram subconjuntos disjuntos das faces limitadas, ou um dos dois ciclos encerra o outro. Seguindo a dualidade entre espaços de ciclo e espaços de corte, esta base para um gráfico planar corresponde a uma árvore de Gomory-Hu do gráfico dual, uma base de peso mínimo para seu espaço de corte.

Nenhum fluxo zero

Em gráficos planares, colorações com cores distintas são duais para nenhum fluxo zero sobre o anel do módulo de inteiros . Nessa dualidade, a diferença entre as cores de duas regiões adjacentes é representada por um valor de fluxo na borda que separa as regiões. Em particular, a existência de nenhum 4-flow em lugar nenhum é equivalente ao teorema das quatro cores . O teorema de snark generaliza esse resultado para gráficos não planares. ${\ displaystyle k}$${\ displaystyle \ mathbb {Z} _ {k}}$${\ displaystyle k}$

Referências