Teoria dos Grafos - Isomorfismo

Um gráfico pode existir em diferentes formas, com o mesmo número de vértices, arestas e também a mesma conectividade de arestas. Esses gráficos são chamados de gráficos isomórficos. Observe que rotulamos os gráficos neste capítulo principalmente com o propósito de fazer referência a eles e reconhecê-los uns dos outros.

Gráficos Isomórficos

Dois gráficos G 1 e G 2 são considerados isomórficos se -

  • Seu número de componentes (vértices e arestas) é o mesmo.

  • Sua conectividade de borda é mantida.

Note- Em suma, dos dois gráficos isomórficos, um é uma versão ajustada do outro. Um gráfico sem etiqueta também pode ser considerado um gráfico isomórfico.

There exists a function ‘f’ from vertices of G1 to vertices of G2
   [f: V(G1) ⇒ V(G2)], such that
Case (i): f is a bijection (both one-one and onto)
Case (ii): f preserves adjacency of vertices, i.e., if the edge {U, V} ∈ G1, then the
edge {f(U), f(V)} ∈ G2, then G1 ≡ G2.

Note

Se G 1 ≡ G 2 então -

| V (G 1 ) | = | V (G 2 ) |

| E (G 1 ) | = | E (G 2 ) |

As sequências de graus de G 1 e G 2 são iguais.

Se os vértices {V 1 , V 2 , .. Vk} formam um ciclo de comprimento K em G 1 , então os vértices {f (V 1 ), f (V 2 ),… f (Vk)} devem formar um ciclo de comprimento K em G 2 .

Todas as condições acima são necessárias para que os gráficos G 1 e G 2 sejam isomórficos, mas não o suficiente para provar que os gráficos são isomórficos.

  • (G 1 ≡ G 2 ) se e somente se (G 1 - ≡ G 2 -) onde G 1 e G 2 são gráficos simples.

  • (G 1 ≡ G 2 ) se as matrizes de adjacência de G 1 e G 2 forem iguais.

  • (G 1 ≡ G 2 ) se e somente se os subgráficos correspondentes de G 1 e G 2 (obtidos pela exclusão de alguns vértices em G1 e suas imagens no gráfico G 2 ) são isomórficos.

Example

Quais dos gráficos a seguir são isomórficos?

No gráfico G 3 , o vértice 'w' tem apenas grau 3, enquanto todos os outros vértices do gráfico têm grau 2. Logo, G3 não é isomórfico a G 1 ou G 2 .

Tomando complementos de G 1 e G 2 , você tem -

Aqui, (G 1 - ≡ G 2 -), portanto (G 1 ≡ G 2 ).

Gráficos Planares

Um gráfico 'G' é considerado plano se puder ser desenhado em um plano ou esfera de modo que duas arestas não se cruzem em um ponto não vértice.

Example

Regiões

Cada gráfico planar divide o plano em áreas conectadas chamadas regiões.

Example

Grau de uma região limitada r = deg(r) = Número de arestas envolvendo as regiões r.

deg(1) = 3
deg(2) = 4
deg(3) = 4

deg(4) = 3
deg(5) = 8

Grau de uma região ilimitada r = deg(r) = Número de arestas envolvendo as regiões r.

deg(R1) = 4
deg(R2) = 6

Em gráficos planos, as seguintes propriedades são válidas -

Em um gráfico planar com 'n' vértices, a soma dos graus de todos os vértices é -

n Σ i = 1 grau (V i ) = 2 | E |

De acordo com Sum of Degrees of Regions/ Teorema, em um gráfico planar com 'n' regiões, a soma dos graus das regiões é -

n Σ i = 1 grau (ri) = 2 | E |

Com base no teorema acima, você pode tirar as seguintes conclusões -

Em um gráfico planar,

Se o grau de cada região for K, então a soma dos graus das regiões é -

K | R | = 2 | E |

Se o grau de cada região for pelo menos K (≥ K), então

K | R | ≤ 2 | E |

Se o grau de cada região for no máximo K (≤ K), então

K | R | ≥ 2 | E |

Note - Suponha que todas as regiões tenham o mesmo grau.

De acordo com Euler’s Formulae em gráficos planares,

Se um gráfico 'G' é um plano conectado, então

| V | + | R | = | E | + 2

Se for um gráfico planar com componentes 'K', então

| V | + | R | = | E | + (K + 1)

Onde, | V | é o número de vértices, | E | é o número de arestas e | R | é o número de regiões.

Edge Vertex Inequality

Se 'G' é um gráfico planar conectado com o grau de cada região pelo menos 'K', então,

| E | ≤ k / (k-2) {| v | - 2}

Você sabe, | V | + | R | = | E | + 2

K. | R | ≤ 2 | E |

K (| E | - | V | + 2) ≤ 2 | E |

(K - 2) | E | ≤ K (| V | - 2)

| E | ≤ k / (k-2) {| v | - 2}

Se 'G' é um gráfico plano simples conectado, então

|E| ≤ 3|V| − 6
|R| ≤ 2|V| − 4

Existe pelo menos um vértice V • ∈ G, tal que deg (V) ≤ 5.

Se 'G' é um gráfico plano simples conectado (com pelo menos 2 arestas) e sem triângulos, então

|E| ≤ {2|V| – 4}

Teorema de Kuratowski

Um grafo 'G' é não planar se e somente se 'G' tem um subgrafo que é homeomorfo a K 5 ou K 3,3 .

Homomorfismo

Dois gráficos G 1 e G 2 são ditos homomórficos, se cada um desses gráficos puder ser obtido a partir do mesmo gráfico 'G' dividindo algumas arestas de G com mais vértices. Dê uma olhada no seguinte exemplo -

Divida a aresta 'rs' em duas arestas adicionando um vértice.

Os gráficos abaixo são homomórficos ao primeiro gráfico.

Se G 1 é isomórfico a G 2 , então G é homeomórfico a G2, mas o inverso não precisa ser verdadeiro.

  • Qualquer gráfico com 4 ou menos vértices é plano.

  • Qualquer gráfico com 8 ou menos arestas é plano.

  • Um gráfico completo K n é plano se e somente se n ≤ 4.

  • O grafo bipartido completo K m, n é planar se e somente se m ≤ 2 ou n ≤ 2.

  • Um grafo não planar simples com número mínimo de vértices é o grafo completo K 5 .

  • O grafo não plano simples com número mínimo de arestas é K 3, 3 .

Gráfico poliédrico

Um gráfico plano conectado simples é chamado de gráfico poliédrico se o grau de cada vértice for ≥ 3, ou seja, grau (V) ≥ 3 ∀ V ∈ G.

  • 3 | V | ≤ 2 | E |

  • 3 | R | ≤ 2 | E |