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) = 6Em 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 é -
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 é -
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 é -
Se o grau de cada região for pelo menos K (≥ K), então
Se o grau de cada região for no máximo K (≤ K), então
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
Se for um gráfico planar com componentes 'K', então
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| − 4Existe 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 |