Baixe o app para aproveitar ainda mais
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
Compartilhar