Gráfico de quociente - Quotient graph
Na teoria dos grafos , um grafo quociente Q de um grafo G é um grafo cujos vértices são blocos de uma partição dos vértices de G e onde o bloco B é adjacente ao bloco C se algum vértice em B é adjacente a algum vértice em C com respeito para o conjunto de arestas de L . Em outras palavras, se G tem conjunto de arestas E e conjunto de vértices V e R é a relação de equivalência induzida pela partição, então o gráfico de quociente tem conjunto de vértices V / R e conjunto de arestas {([ u ] R , [ v ] R ) | ( u , v ) ∈ E ( G )}.
Mais formalmente, um gráfico de quociente é um objeto de quociente na categoria de gráficos. A categoria de grafos é concretizável - mapear um gráfico para seu conjunto de vértices o torna uma categoria concreta - então seus objetos podem ser considerados como "conjuntos com estrutura adicional", e um gráfico de quociente corresponde ao gráfico induzido no conjunto de quocientes V / R do seu conjunto vértice V . Além disso, há um homomorfismo de grafo (um mapa de quociente ) de um grafo para um grafo de quociente, enviando cada vértice ou aresta para a classe de equivalência a que pertence. Intuitivamente, isso corresponde a "colar" (formalmente, "identificar") vértices e arestas do gráfico.
Exemplos
Um gráfico é trivialmente um gráfico quociente de si mesmo (cada bloco da partição é um único vértice), e o gráfico que consiste em um único ponto é o gráfico quociente de qualquer gráfico não vazio (a partição consiste em um único bloco de todos os vértices ) O gráfico de quociente não trivial mais simples é aquele obtido pela identificação de dois vértices ( identificação de vértices ); se os vértices estiverem conectados, isso é chamado de contração de aresta .
Tipos especiais de quociente
A condensação de um gráfico direcionado é o gráfico de quociente onde os componentes fortemente conectados formam os blocos da partição. Esta construção pode ser usada para derivar um gráfico acíclico direcionado de qualquer gráfico direcionado.
O resultado de uma ou mais contrações de aresta em um grafo não direcionado G é um quociente de G , no qual os blocos são os componentes conectados do subgrafo de G formado pelas arestas contraídas. No entanto, para quocientes mais geralmente, os blocos da partição que dão origem ao quociente não precisam formar subgráficos conectados.
Se L é um gráfico que cobre de um outro gráfico H , então H é um gráfico de quociente G . Os blocos da partição correspondente são as imagens inversas dos vértices de H sob o mapa de cobertura. No entanto, os mapas de cobertura têm um requisito adicional que não é verdadeiro em termos mais gerais para os quocientes, que o mapa seja um isomorfismo local.
Complexidade computacional
É NP-completo , dado um gráfico cúbico de n- vértice G e um parâmetro k , para determinar se G pode ser obtido como um quociente de um gráfico plano com n + k vértices.
