Grafos: Completo, Bipartido e Isomorfismo

Prévia do material em texto

Grafos 
• A figura a seguir ilustra os grafos simples 
completos com 1, 2, 3 e 4 vértices; 
• O grafo simples completo com n vértices é 
denotado por 𝑘𝑛 
Grafo Bipartido Completo 
• Um grafo é um grafo bipartido completo 
(ou grafo bipartite completo) se seus 
vértices podem ser divididos em dois 
conjuntos disjuntos não vazios 𝑁1 e 𝑁2 tais 
que dois vértices são adjacentes se, e 
somente se, um deles ∈ N1 e o outro ∈ N2. 
Se = |𝑁1| = m e |𝑁2|= n, este grafo é 
denotado por 𝐾𝑚,𝑛. 
• Considere o grafo simples a seguir. 
• Ele não é um grafo completo porque nem todo 
vértice é adjacente a todos os demais vértices. 
• No entanto, os vértices podem ser divididos em 
dois conjuntos disjuntos, {1,2} e {3,4,5} de tal 
forma que quaisquer dois vértices tomados no 
mesmo conjunto não são adjacentes, mas todos 
dois vértices escolhidos em conjuntos diferentes 
são adjacentes. 
• Considere o grafo simples a seguir. 
• Ele não é um grafo completo porque nem todo 
vértice é adjacente a todos os demais vértices. 
• No entanto, os vértices podem ser divididos em 
dois conjuntos disjuntos, {1,2} e {3,4,5} de tal 
forma que quaisquer dois vértices tomados no 
mesmo conjunto não são adjacentes, mas todos 
dois vértices escolhidos em conjuntos diferentes 
são adjacentes. 
Grafo 
Bipartido 
𝑲𝟐,𝟑 
Grafos Isomorfos 
• Dois grafos podem parecer muito diferentes em suas 
representações gráficas, mas serem, ainda assim, o 
mesmo grafo de acordo com nossa definição. 
• Os grafos nas figuras a seguir são os mesmos, eles têm 
os mesmos vértices, as mesmas arestas e a mesma 
função de associação de arestas e seus extremos. (Na 
representação de um grafo, as arestas podem 
interceptar-se em pontos que não sejam vértices do 
grafo.) 
• O grafo da próxima figura também é o mesmo 
grafo dos dois anteriores. 
• Se mudarmos os rótulos dos vértices e arestas 
do grafo segundo a correspondência a seguir, os 
grafos se tornarão os mesmos: 
 
• Estruturas que são iguais, exceto por uma 
mudança de nomes(rótulos), são ditas 
isomorfas. 
• Definição: Grafos Isomorfos Dois grafos 
(𝑁1, 𝐴1, g1) e (𝑁2, 𝐴2, g2) são isomorfos se 
existem bijeções f1: N1 → N2 e f2: A1 → A2 tais 
que, para cada arco a ∈ A1, g1(𝑎) = x-y se, e 
somente se, g2[f2(𝑎)] = f1(x) - f1(y). 
• Os grafos mostrados na a seguir são isomorfos. 
• As bijeções que estabelecem o isomorfismo são 
parcialmente dadas : 
• Para provarmos que os grafos são isomorfos, 
precisamos completar a definição da função f2, e 
então mostrar que a relação entre arestas e seus 
extremos é preservada para todos os casos 
possíveis. 
• Prove que os Grafos são isomorfos. 
 
 
 
 
• O isomorfismo de grafos é fácil de estabelecer no 
caso de examinarmos grafos simples. 
• Se pudermos encontrar uma função f1, que leve 
vértices em vértices, então uma função f2 que 
leve arestas em arestas é trivial porque existe no 
máximo uma aresta entre cada par de vértices. 
Portanto, vale o seguinte teorema: 
• Teorema sobre Isomorfismo de Grafos Simples 
• Dois grafos simples (N1, A1e g1) e (N2, A2e g2) 
são isomorfos se houver uma bijeção f: N1 → 
N2 tal que para quaisquer vértices 𝑛𝑖e 𝑛𝑗 de N1, 
𝑛𝑖 e 𝑛𝑗 são adjacentes se, e somente se, f(𝑛𝑖) e 
f(𝑛𝑗) são adjacentes. 
• A função f é chamada de isomorfismo do grafo 
1 no grafo 2. 
• Encontre um isomorfismo do grafo da figura a 
no grafo b 
• Determinar que dois grafos são isomorfos requer 
que encontremos a bijeção e então mostremos 
que a propriedade da adjacência é preservada. 
• Para mostrar que dois grafos não são isomorfos, 
precisamos mostrar que a(s) bijeção(ões) 
necessária(s) não existe(m). 
• Poderíamos tentar todas as bijeções possíveis (já 
que há um número finito de vértices e arestas, 
existe um número finito de bijeções). 
• No entanto, este método se tornaria 
rapidamente inviável em grafos de qualquer 
tamanho razoável. 
• Ao invés disso, podemos procurar outras razões 
pelas quais tais bijeções não possam existir. 
• Apesar de não ser uma tarefa simples em todos os 
casos, existem certas condições sob as quais se 
torna fácil ver que dois grafos não são isomorfos 
• Essas condições incluem: 
1. Um grafo tem mais vértices que o outro. 
2. Um grafo tem mais arestas que o outro. 
3. Um grafo tem arestas paralelas e o outro não. 
4. Um grafo tem um laço e o outro não. 
5. Um grafo tem um vértice de grau kc o outro não. 
6. Um grafo é conexo e o outro não. 
7. Um grafo tem um ciclo e o outro não. 
• Demonstre que os dois grafos a seguir não são 
isomorfos. 
 
 
 
 
• E os seguintes grafos? 
• Demonstre que os dois grafos a seguir não são 
isomorfos. 
 
 
 
 
 
• O Grafo à esquerda tem dois nós de grau 2, mas 
o grafo da direita não; 
• ou, o grafo à esquerda tem arcos paralelos, mas 
o grafo a direita não 
• E os seguintes grafos? 
 
 
 
 
• Os dois grafos não são isomorfos. 
• Perceba que cada grafo tem seis vértices e sete arestas. 
• Nenhum dos dois tem laços nem arcos paralelos. 
• Ambos são conexos. 
• Ambos têm três ciclos, quatro vértices de grau 2 e dois 
vértices de grau 3. 
• Portanto, nenhum dos testes óbvios de isomorfismo se 
aplica. 
• No entanto, o segundo grafo tem um vértice de grau 2 
que é adjacente a dois vértices de grau 3; o que não 
ocorre no primeiro, e, portanto, os grafos não são 
isomorfos. 
Desafio 
• Considere 𝑘5, um grafo simples completo com 
cinco vértices. 
• Construa este grafo sem que os arcos se 
interceptem. 
Desafio 
• Considere 𝑘5, um grafo simples completo com 
cinco vértices. 
• Construa este grafo sem que os arcos se 
interceptem. 
• Essa construção não é possível. 
• Um grafo simples completo com cinco vértices 
não é um grafo planar. 
Grafos Planares 
• Um grafo planar é um grafo que pode ser 
representado (em uma folha de papel, isso é, um 
plano) de modo que seus arcos se intersectam 
apenas em nós. 
• Por exemplo, projetistas de circuitos integrados 
querem que todos os componentes de um chip 
formem um grafo planar, de modo a não haver 
cruzamento de conexões. 
• Um matemático suíço do século XVIII, Leonhard 
Euler (pronuncia-se "óiler") descobriu um fato 
importante sobre grafos planares. 
 
• Um grafo simples, conexo e planar (quando 
desenhado em sua representação planar, sem 
interseção de arestas) divide o plano em um 
número de regiões, incluindo as regiões 
totalmente fechadas e uma região infinita 
exterior. 
• Euler observou uma relação entre o número n de 
vértices, o número a de arestas e o número r de 
regiões neste tipo de grafos. 
• Esta relação é denominada de fórmula de Euler: 
n - a + r = 2 
• Verifique a fórmula de Euler para o grafo 
conexo, planar e simples para o seguinte grafo. 
 
 
 
 
 
 
 
• Verifique a fórmula de Euler para o grafo 
conexo, planar e simples para o seguinte grafo. 
 
 
 
 
 
 
• n = 6 
• a = 7 
• r = 3 
 
• Verifique a fórmula de Euler para o grafo 
conexo, planar e simples para o seguinte grafo. 
 
 
 
 
 
 
• n = 6 
• a = 7 
• r = 3 
 
 
n - a + r = 2 
 
6 – 7 + 3 = 2 
• Se incluirmos mais restrições no grafo, existem 
duas consequências na fórmula de Euler que nos 
levam ao seguinte teorema. 
• Teorema sobre o Número de Vértices e Arestas 
• Para um grafo conexo, simples e planar com n 
vértices e a arestas: 
1. Se a representação planar divide o plano em r 
regiões, então n - a + r = 2 (1) 
2. Se n ≥ 3, então a ≤ 3n – 6 (2) 
3. Se n ≥ 3 e se não existem ciclos decomprimento 
3, então a ≤ 2n – 4 (3) 
• Podemos usar esse teorema para provar que certos 
grafos não são planares. 
Exemplo 
• 𝑘5 é um grafo conexo simples com cinco vértices (e 10 
arestas). Ele é planar? 
• Se ele fosse um grafo planar, a desigualdade (2) do 
nosso teorema deveria ser verdadeira, mas não é 10 ≤ 
3(5) - 6. 
• Portanto, 𝑘5 não é planar. 
• 𝑘3,3 é um grafo conexo simples com seis vértices (e 
nove arestas). Não possui ciclos de comprimento 3, 
uma vez que isto exigiria que dois vértices em um dos 
subconjuntos fossem adjacentes. 
• Se fosse um grafo planar, a desigualdade (3) deveria ser 
verdadeira, mas 9 ≤ 2(6) - 4. Portanto, K3,3 não é 
planar 
• Podemos usar esse teorema para provar que certos 
grafos não são planares. 
Exemplo 
• 𝑘5 é um grafo conexo simples com cinco vértices (e 10 
arestas). 
• Se ele fosse um grafo planar, a desigualdade (2) do 
nosso teorema deveria ser verdadeira, mas não é 10 ≤ 
3(5) - 6. 
• Portanto, 𝑘5 não é planar. 
• 𝑘3,3 é um grafo conexo simples com seis vértices (e 
nove arestas). Não possui ciclos de comprimento 3, 
uma vez que isto exigiria que dois vértices em um dos 
subconjuntos fossem adjacentes. 
• Se fosse um grafo planar, a desigualdade (3) deveria ser 
verdadeira, mas 9 ≤ 2(6) - 4. Portanto, K3,3 não é 
planar 
• Podemos usar esse teorema para provar que certos 
grafos não são planares. 
Exemplo 
• 𝑘5 é um grafo conexo simples com cinco vértices (e 10 
arestas). 
• Se ele fosse um grafo planar, a desigualdade (2) do 
nosso teorema deveria ser verdadeira, mas não é 10 ≤ 
3(5) - 6. 
• Portanto, 𝑘5 não é planar. 
• 𝑘3,3 é um grafo conexo simples com seis vértices (e 
nove arestas). Não possui ciclos de comprimento 3, 
uma vez que isto exigiria que dois vértices em um dos 
subconjuntos fossem adjacentes. Ele é planar? 
• Se fosse um grafo planar, a desigualdade (3) deveria ser 
verdadeira, mas 9 ≤ 2(6) - 4. Portanto, K3,3 não é 
planar 
• Podemos usar esse teorema para provar que certos 
grafos não são planares. 
Exemplo 
• 𝑘5 é um grafo conexo simples com cinco vértices (e 10 
arestas). 
• Se ele fosse um grafo planar, a desigualdade (2) do 
nosso teorema deveria ser verdadeira, mas não é 10 ≤ 
3(5) - 6. 
• Portanto, 𝑘5 não é planar. 
• 𝑘3,3 é um grafo conexo simples com seis vértices (e 
nove arestas). Não possui ciclos de comprimento 3, 
uma vez que isto exigiria que dois vértices em um dos 
subconjuntos fossem adjacentes. 
• Se fosse um grafo planar, a desigualdade (3) deveria ser 
verdadeira, mas 9 ≤ 2(6) – 4 não é verdade. Portanto, 
𝑘3,3 não é planar 
• Podemos observar que para 𝑘3,3 , a desigualdade 
(2) ficaria da seguinte forma: 
 9 ≤ 3(6) – 6 o que é verdade 
• Essa desigualdade é uma condição necessária, mas 
não suficiente, para um grafo com n ≥ 3 ser planar. 
• Os grafos não planares 𝑘3,3 e 𝑘5 têm um papel 
importante na teoria dos grafos não planares. 
• Para enunciar qual é esse papel, precisamos de 
mais uma definição. 
• Grafos Homeomorfos: Dois grafos são ditos homeomorfos 
se ambos podem ser obtidos do mesmo grafo por uma 
sequência de subdivisões elementares, nas quais um único 
arco x – y é substituído por dois novos arcos, x – v e v – y, 
ligando um novo nó v. 
• Os grafos das partes (b) e (c) da figura a seguir são 
homeomorfos porque podem ser obtidos do grafo da 
figura(a) através de uma sequência de subdivisões 
elementares. 
 
 
 
 (a) (b) (c) 
• Um grafo planar não pode ser transformado em um 
grafo não-planar através de subdivisões elementares e 
um não-planar não pode ser transformado em um 
planar com subdivisões elementares. 
• Como um resultado, grafos homeomorfos são ambos 
planares ou não-planares. 
• O teorema a seguir, atribuído ao matemático polonês 
Kuratowski, caracteriza grafos não-planares. 
• Teorema de Kuratowski 
– Um grafo é não-planar se, e somente se, contém um subgrafo 
homeomorfo a 𝑘3,3 ou 𝑘5 
• A primeira figura é um grafo de Petersen. 
• Se olharmos na parte superior do grafo, podemos ver que o vértice a é 
adjacente aos vértices e,f e b e nenhum destes são adjacentes uns aos outros. 
• Além disso, o vértice e é adjacente aos vértices d e j, bem como ao vértice a e 
os vértices a, d e j não são adjacentes uns aos outros. Esta informação é 
transcrita no segundo grafo, que é um subgrafo de 𝑘3,3 . 
• As arestas necessárias para completar 𝑘3,3 são mostradas como linhas 
tracejadas no terceiro. Essas arestas não pertencem ao grafo de Petersen; por 
exemplo, não há a aresta j-f. No entanto, existe um caminho no grafo de 
Petersen que de j a f usa o vértice intermediário h, isto é, j-h e h-f. 
• Analogamente, existem caminhos j-g e g-b, d-i e i-f e d-c e c-b. A inclusão 
desses caminhos ao segundo resulta no quarto grafo, que é um subgrafo do 
grafo de Petersen e também pode ser obtida através de uma sequência de 
subdivisões elementares do terceiro. 
Exercícios 
• Qual dos grafos a seguir não é isomorfo aos 
outros e por quê? 
Exercícios 
• Qual dos grafos a seguir não é isomorfo aos 
outros e por quê? 
O segundo pois não possui nó de grau 0 
Exercícios 
• Demonstre que 𝑘2,3 é um grafo planar. 
Exercícios 
• Demonstre que 𝑘2,3 é um grafo planar. 
Exercícios 
• Se um grafo simples, conexo e planar tem seis 
vértices, todos de grau 3, em quantas regiões 
ele divide o plano? 
 
 
 
Exercícios 
• Se um grafo simples, conexo e planar tem seis 
vértices, todos de grau 3, em quantas regiões 
ele divide o plano? 
 
 
 
• n – a + r = 2 
• n = 6 a = 9 
• 6 – 9 + r = 2 r = 5 
Exercícios 
• Diga se os dois grafos apresentados são ou não 
isomorfos. Se forem, apresente a função que 
estabelece o isomorfismo entre eles; caso 
contrário, explique por quê. 
Exercícios 
• Para cada um dos grafos a seguir determine se o 
grafo é planar (mostrando uma representação 
planar) ou não-planar (encontrando um subgrafo 
homeomorfo a 𝑘3,3 ou 𝑘5