Baixe o app para aproveitar ainda mais
Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original
Teoria dos Grafos/GrafosA1.pdf Teoria dos Grafos Edson Prestes Teoria dos Grafos P. O. Boaventura Netto, “Grafos: Teoria, Modelos e Algoritmos”, São Paulo, E. Blucher 2001; R. J. Trudeau, “Introduction to Graph Theory”, New York, Dover Publications, 1993; Kaufmann, Arnold. “Exercices de combinatorique avec solutions”. Paris: Dunod, 1969-1972 3v. Harary, Frank. “Graph theory”. Reading, Mass.: Addison- Wesley, c1969. 274 p. : il. West, Douglas B.. “Introduction to graph theory”. 2nd ed. Upper Saddle River: Prentice Hall, c2001. 588 p. Referências Teoria dos Grafos A teoria dos Grafos surgiu com os trabalhos de L. Euler, G. Kirchhoff e A. Cayley. Esta teoria tem sido utilizada largamente em diferentes áreas da biologia, química e na matemática aplicada. O problema das pontes de Königsberg é o primeiro e mais famoso problema em teoria dos grafos resolvido por Euler em 1736. Introdução Teoria dos Grafos O problema das pontes de Königsberg Na cidade de Königsberg existiam sete pontes que cruzavam o rio Pregel estabelecendo ligações entre duas ilhas e entre as ilhas e as margens opostas do rio. O problema consiste em determinar se é possível ou não fazer um passeio pela cidade começando e terminando no mesmo lugar, cruzando cada ponte exatamente uma única vez. Introdução Teoria dos Grafos Introdução pontes de Königsberg Teoria dos Grafos Um grafo G consiste de um conjunto finito e não vazio de n nós, denotado por, V(G) e m arestas, denotado por, A(G). O termo grafo foi criado pelo químico E. Frankland e adotado em 1884. Ele vem da contração de notação gráfica. Cada aresta corresponde a um par não ordenado de nós. Introdução Teoria dos Grafos Os nós constituintes de uma aresta podem ser diferentes ou não. Se não forem diferentes então a aresta forma um laço. Introdução Teoria dos Grafos Harary define um multigrafo como aquele grafo que possui mais de uma aresta conectando dois vértices, mas que não possui loops. Se o grafo possui loop e múltiplas linhas conectando dois vértices então ele é chamado pseudografo. Em multigrafos/pseudografos, convém rotular as arestas para distingui- las entre si, devido a multiplicidade de conexões entre os vértices. Introdução Teoria dos Grafos Dizemos que uma aresta é incidente aos nós aos quais está associada. Arestas incidentes em um mesmo nó são chamadas arestas adjacentes. Nós incidentes em uma mesma aresta são chamados nós adjacentes. Um nó pode estar isolado dos demais, caso ele não esteja ligado através de uma aresta aos restantes. Introdução Teoria dos Grafos Introdução G1 G2 Dados os grafos abaixo O grafo G1 é descrito por V(G1)={1,2,3,4,5} e A(G1)={(1,2),(1,3), (1,4), (2,3),(2,4)}. O grafo G2 é descrito por V(G2)={1,2,3,4} e A(G1)={a,b,c,d,e,f}. Teoria dos Grafos Um grafo dirigido, ou dígrafo, é um grafo cujas arestas são pares ordenados, comumente chamados de arcos ou arestas direcionadas. Os dígrafos diferem dos grafos orientados por possuírem pares simétricos de arestas direcionadas. Introdução Dígrafo Grafo Orientado Teoria dos Grafos O grau de um nó corresponde ao número de arestas incidentes a ele. Cada laço conta como duas arestas. O menor grau presente em um grafo G é denotado por O maior grau presente em um grafo G é denotado por Introdução Teoria dos Grafos A soma total dos graus de todos os vértices de um grafo é sempre par Prova por indução no número de arestas Introdução B.I. : Suponha um grafo sem arcos. Todos os seus vértices têm grau zero e portanto a soma geral dos graus dos vértices é zero (par) H.I. : Suponha que para todo grafo de n arestas a soma dos graus de todos os vértices é par. P.I. : Suponha um grafo G de n+1 arestas. Seja G' um grafo igual a G exceto com menos uma aresta. Portanto G' tem n arestas e pela H.I. tem como soma total dos graus de seus vértices um número par. A inclusão da aresta removida faz com a soma dos graus seja incrementada de 2 (é incrementado de 1 o grau dos vértices constituintes da aresta), portanto a soma dos graus dos vértices de G é um número par. Teoria dos Grafos Em um grafo qualquer, o número de vértices com grau ímpar tem que ser par Prova por indução no número de arestas Introdução B. I. Suponha um grafo sem arestas, neste caso temos a soma dos graus de todos os vértices sendo par. Como a quantidade de vértices com grau impar é igual a zero. Então temos uma quantidade par de vértices de grau ímpar. H. I. Suponha um grafo com n arestas e um número par de vértices com grau impar Teoria dos Grafos Introdução P. I. Seja G um grafo com n+1 arestas. Seja G', o grafo resultante da retirada de uma aresta (v,w). Pela H.I. G’ tem um número par de vértices com grau impar Vamos analisar o grafo G, baseado nas seguintes situações dos vértices v e w em G’: v tem grau impar e w tem grau impar v tem grau impar e w tem grau par v tem grau par e w tem grau par A adição da aresta (v,w) em G' pode resultar nas seguintes situações: • v tem grau impar e w tem grau impar em G’. A adição da aresta (v,w) faz com que v passe a ter grau par assim como w. Como a quantidade de vértices de grau impar é par e como transformamos 2 vértices de grau impar em vértices de grau par, G tem uma quantidade par de vértices de grau impar. Teoria dos Grafos Introdução • v tem grau impar e w tem grau par em G‘. A adição da aresta (v,w) faz com que v passe a ter grau par e w passe a ter grau impar. Logo, G tem uma quantidade par de vértices com grau ímpar. • v tem grau par e w tem grau par em G‘. A adição da aresta (v,w) faz com que tanto v quanto w passem a ter grau impar. Como tínhamos em G' uma quantidade par de vértices de grau impar, e como aumentou em 2 esta quantidade, temos que a quantidade de vértices de grau ímpar em G é par. Teoria dos Grafos Um passeio entre os nós i e j é uma seqüência alternada de nós e arestas que começa no nó i e termina no nó j. Introdução Um exemplo de passeio entre os nós 1 e 4 do grafo G1 é (1,(1,3),3,(2,3),2,(1,2),1,(1,4),4). Poderíamos pensar que apenas a ordem dos nós é importante. Entretanto, podemos ter passeios diferentes com a mesma seqüência de nós. G1 G2 Por exemplo, no grafo G2 temos os seguintes passeios entre os nós 3 e 4: (3,d,2,a,4) , (3,c,2,a,4) Teoria dos Grafos Um caminho é um passeio que não contém nós repetidos. Entre os nós 1 e 4 do grafo G1 temos os seguintes caminhos (1,4),(1,2,4),(1,3,2,4). Introdução G1 O comprimento de um caminho entre os vértices u e v é a quantidade de arestas presentes no caminho. Se existirem mais de um caminho de u a v, então o comprimento do caminho de u a v será igual ao menor comprimento dentre todos os caminhos de u a v. Teoria dos Grafos Um circuito é um passeio fechado, ou seja, o nó de partida é igual ao nó de chegada. Um ciclo é um caminho fechado, isto é , um passeio que contém exatamente dois nós iguais: o primeiro e o último. Ciclos de comprimento 1 são laços(loops). Uma característica interessante de um ciclo é que o número de arestas pertencentes a ele é igual a número de vértices. Introdução Teoria dos Grafos Introdução - Subgrafo O grafo H é um subgrafo de G, denotado por se e Se temos , ou seja, H é um subgrafo próprio de G. Um subgrafo gerador de G é um subgrafo H, com V(H)=V(G). Teoria dos Grafos/GrafosA10.pdf Teoria dos Grafos Edson Prestes Teoria dos Grafos Árvores – Algoritmo de Kruskal O algoritmo de Kruskal permite determinar a spanning tree de custo mínimo. Este custo corresponde à soma dos pesos (distância, tempo, qualidade, ...) associados a cada aresta do grafo. O algoritmo recebe como entrada um grafo G conexo com pesos e monta um grafo desconexo G’, o qual corresponde a uma floresta de árvores composta unicamente pelos vértices de G. Em seguida, ele ordena as arestas de G em ordem crescente e seleciona a cada instante a de menor peso. A aresta selecionada é marcada, para não ser analisada mais tarde, e verificada se pode ser adicionada ao grafo G' de forma a não gerar ciclos. O processo termina quando G' estiver conexo. Teoria dos Grafos Árvores – Algoritmo de Kruskal Determine a spanning tree de custo mínimo no grafo abaixo usando o algoritmo de Kruskal Teoria dos Grafos Árvores – Algoritmo de Kruskal Teoria dos Grafos Árvores – Algoritmo de Kruskal Teoria dos Grafos Árvores – Algoritmo de Dijkstra O algoritmo de Dijkstra é usado para determinar a menor rota entre duas posições em um grafo. Ele assume que o caminho entre dois vértices, u e v, é composto sempre dos menores caminhos entre dois vértices quaisquer componentes do caminho. O algoritmo considera um grafo G (ou dígrafo) com arestas de pesos positivos e um vértice inicial u. O peso da aresta formada pelos vértices u e v é w(u,v). Se u e v não são adjacentes então w(u,v)= Ele considera que existe um conjunto S de vértices tal que o menor caminho a partir de u até cada vértice de S é conhecido. Teoria dos Grafos Árvores – Algoritmo de Dijkstra Inicialmente, S={u}, t(u)=0, t(z)=w(u,z) para z u. A cada iteração seleciona-se um vértice e adiciona-o a S. Em seguida, as arestas a partir de v, (v,z), são exploradas e para cada z S, a nova distância aproximada t(z) é atualizada com min{t(z), t(v)+w(v,z)}. O processo continua até S=V(G) ou até t(z)= para todo z S. Teoria dos Grafos Planaridade Existem três companhias que devem abastecer com gás, eletricidade e água três prédios diferentes através de tubulações subterrâneas. Estas tubulações podem estar à mesma profundidade ? Isto corresponde a perguntar: é possível desenhar um grafo bipartido com 2 conjuntos de três elementos cada, onde nenhuma aresta cruze outra. Podemos antecipar a resposta dizendo que é impossível ! Um grafo é planar se ele pode ser desenhado em um plano de tal forma que nenhuma aresta cruze as demais. O desenho deste grafo é chamado realização gráfica planar do grafo, ou simplesmente, realização planar. O estudo da planaridade é importante em diversas aplicações como, por exemplo, no desenvolvimento de circuitos impressos. Teoria dos Grafos Planaridade K5 e K3,3 não podem ser desenhados sem que algumas arestas se cruzem. Prova : Considere o desenho de K5 e K3,3 no plano. Seja C um spanning circle do grafo em questão. Se o desenho não tiver arestas que se cruzem, então C é desenhado como uma curva fechada. As cordas de C devem ser desenhadas dentro ou fora da curva. Uma corda é uma aresta cujos vértices final e inicial situam-se em uma curva C, ou seja, se C é um spanning circle de G então as cordas são as arestas de G que não foram incluidas em C. Duas cordas são conflitantes se elas têm seus pontos finais em uma ordem alternante. Quando este conflito existe, então estas cordas devem ser desenhadas uma dentro de C e a outra fora de C. Quantas cordas conflitantes tem o spanning circle de K3,3 ? Ele tem três cordas conflitantes. Podemos colocar no máximo 1 corda dentro e outra fora de C, então é impossível desenhar K3,3 sem que as cordas se cruzem. Quantas cordas conflitantes tem o spanning circle de K5 ? Ele possui 5 cordas conflitantes. No máximo duas cordas podem ficar dentro ou fora de C. Novamente é impossível desenha-las sem que elas se cruzem. Teoria dos Grafos Planaridade As cordas conflitantes do grafo K3,3 são ilustradas pelas linhas tracejadas. As linhas sólidas indicam o spanning circle. Teoria dos Grafos Planaridade Um grafo planar G divide o plano R2 em um conjunto regiões maximais, conhecidas como as faces de G. A região que engloba o grafo é chamada face ilimitada. As fronteiras destas faces correspondem às arestas de G. d(F1)=4 d(F2)=3 d(F3)=3 d(F1)=6 d(F2)=9 d(F3)=3 Cada aresta de G pertence à fronteira de uma ou duas faces de G. O grau (comprimento), de uma face f de G, representado por d(F) é igual ao número de arestas da fronteira de F. ** Aquelas arestas que fazem fronteira com apenas uma face são contadas duas vezes ** Teoria dos Grafos Planaridade Se d(Fi) corresponde ao grau da face i em um grafo planar G então Teoria dos Grafos Planaridade Um grafo dual G* é um grafo obtido a partir de um grafo G. As faces de G correspondem a vértices em G* e se e é uma aresta de G que situa-se entre as faces X e Y de G então a aresta dual e* será uma aresta que ligará os vértices x e y, correspondentes respectivamente às faces X e Y de G. O grau de uma face em G corresponde ao grau do vértice G* Proposição: todas as faces de um grafo G têm grau par sse o grafo dual G* é euleriano. Teoria dos Grafos Planaridade Um grafo é periplanar(outerplanar) se ele tem uma realização gráfica onde cada vértice do grafo faz fronteira com a face ilimitada. Proposição: os grafos K4 e K2,3 não são periplanares. Prova: Para mostrar que eles não são periplanares, um dos requisitos é mostrar que eles não possuem uma spanning circle. A existência de um spanning circle em um grafo G é condição necessária, mas não suficiente, para que G seja periplanar. Não ! Logo, K2,3 não é um grafo periplanar. O grafo K2,3 possui um spanning circle ? Teoria dos Grafos Planaridade O K4 possui um spanning circle. Entretanto, ele possui duas cordas conflitantes. Isto faz com que ambas as cordas não possam ser desenhadas na parte interna do grafo. Como uma corda é desenhada na parte externa do grafo, um dos vértices de G fica na parte interna de G e por conseguinte não faz fronteira com a face ilimitada O grafo K4 é periplanar ? Teoria dos Grafos Planaridade Teorema de Euler: seja G=(V,A) um grafo planar com |V(G)|=n e |A(G)|=m, p sendo o número de componentes conexos de G e f o número de faces de uma realização planar de G. Logo n-m+f=p+1 Prova: Considere inicialmente p=1. A prova utiliza indução no número de arcos. Para m=0 e um único vértice, n=1, temos apenas 1 face. Portanto, n-m+f=p+1 é igual a 1-0+1=1+1. Suponha que a equação seja verdadeira para um grafo com m-1 arcos, com m 1. Construa a realização planar de G acrescentando arcos incidentes ao subgrafo corrente. Antes da inserção do m-1-ésimo arco, nm-1-mm-1+fm-1=2 Teoria dos Grafos Planaridade Considere a inserção do m-ésimo arco. Este arco pode ser inserido de duas maneiras. 1a) assuma que uma de suas extremidades corresponde a um nó pertencente ao subgrafo existente e a outra extremidade corresponde a um novo nó. Observe que o número de faces não se altera, logo (nm-1+1)-(mm-1+1)+fm-1 =2 nm-mm+fm=2 Novo vértice Teoria dos Grafos Planaridade 2a) considere que as extremidades do m-ésimo arco correspondem aos nós já existentes no grafo em questão Neste caso, as duas extremidades devem estar na fronteira de uma mesma face. Portanto, esta face é dividida em duas pelo m-ésimo arco. Como não criamos nenhum novo vértice, o número de vértices não se altera. Então temos, nm-1-(mm-1+1)+(fm-1+1)=2 nm-mm+fm=2 Teoria dos Grafos Planaridade A prova para p>1 fica como exercício! Teoria dos Grafos Planaridade Seja G=(V,A) um grafo conexo planar, com |V(G)|=n e |A(G)|=m, onde m 2. Então m 3n-6 Usando a fórmula de Euler, temos Cada face de um grafo é delimitada por mínimo três arestas. Logo pois cada aresta é compartilhada por duas faces Teoria dos Grafos Planaridade Corolário k5 não é planar. Para provar que k5 não é planar, basta usar a desigualdade Sabemos que o número de arestas m de k5 é igual a 5.4/2=10 e que ele possui n=5 vértices. m 3n-6 Usando a desigualdade temos 10 3.5-6, vemos que k5 não é planar. Teoria dos Grafos Planaridade Corolário k3,3 não é planar. De forma análoga ao demonstrado anteriormente, agora cada face é delimitada por no mínimo 4 arestas, . Usando o Teorema de Euler, temos Sabemos que k3,3 possui 9 arestas e 6 vértices. Usando a desigualdade acima, vemos que 9 2.6 -4 é falsa. Portanto, k3,3 não é planar. m 3n-6A desigualdade vale quando o grafo é planar e possui triangulos. Se ele não possuir triangulos então devemos usar a seguinte desigualdade para verificar se ele é planar Teoria dos Grafos Planaridade Teorema de Kuratowski: um grafo G é planar sse não contém um subgrafo que é um grafo generalizado de K5 ou K3,3. Um grafo é planar sse não contém um subgrafo o qual por contração chegaria a K5 ou K3,3. O grafo de Petersen é planar ? Não! Pois ele pode ser reduzido ao grafo K5 por arco-contração. Teoria dos Grafos Planaridade O grafo de abaixo é planar ? Não! Pois ele pode ser reduzido ao grafo K3,3 por arco-contração. Teoria dos Grafos Planaridade Dois grafos são homeomorfos se eles podem ser obtidos do mesmo grafo inserindo novos vértices de grau 2 nos arcos. Assim, Teorema: um grafo é planar sse não contém subgrafo homeomorfo a k5 ou k3,3. Considere que existem pessoas que participam dos Comitês: 1 e 2; 1 e 4; 2 e 3; e 3 e 4. Teoria dos Grafos Coloração de Grafos Imagine que devamos reunir pessoas para participarem de um ou mais comitês de avaliação em uma determinada conferência. Qual deve ser o escalonamento de horários de atuações destes comitês para permitir que todos os membros inscritos participem de todas as atividades realizadas por seus respectivos comitês? Este problema é comumente tratado na área de grafos através de técnicas de coloração de grafos. Um grafo é k-colorível se ele tem uma k-coloração própria. Em uma coloração própria, cada classe é um conjunto independente. Portanto, um grafo k-colorível é um grafo k-partido. Teoria dos Grafos Coloração de Grafos Definição: Uma k-coloração de um grafo G é uma uma função de rotulamento f:V(G) S, onde S correspondem a um conjunto de cores e |S|=k. Os vértices associados a uma cor formam uma classe de cores. Uma k-coloração é própria se os vértices adjacentes do grafo têm rótulos (cores) diferentes. O número cromático é o menor k de forma que G seja k-colorível. A coloração de um grafo deve seu nome à aplicação de coloração de mapas. Grafos com loops não são coloríveis. Teoria dos Grafos Coloração de Grafos Um grafo é 2-colorível sse é ele um grafo bipartido. Qual é o número cromático do grafo de Petersen ? O grafo K2 é o único grafo 2-crítico, enquanto que os únicos grafos 3-críticos são os grafos que constituem ciclos ímpares. Teoria dos Grafos Coloração de Grafos Definição: Um grafo G é k-cromático se . Uma k-coloração de um grafo k-cromático é uma coloração ótima. Se para todo então G é k-crítico, ou seja, se G é crítico então Teorema: Para qualquer grafo G, o número cromático é no máximo uma unidade a mais que o maior grau de G, ou seja, Exemplo: Qualquer grafo completo garante e qualquer grafo estrela G com |V(G)|>2 garante Proposição: Considere o tamanho do maior clique de G; e o tamanho do maior conjunto independente de G. Para qualquer grafo G, Teoria dos Grafos Coloração de Grafos Em relação à primeira desigualdade, note que em um clique todos os vértices tem que ter cores distintas. Portanto se o grafo G possui um clique de tamanho máximo então seu número cromático será no mínimo igual a , podendo ser maior. Teoria dos Grafos Coloração de Grafos Em relação à segunda desigualdade, considere um grafo C5. O maior conjunto independente tem tamanho Sabemos que são necessárias 3 cores para colorir C5, então a desigualdade é verdadeira. Teoria dos Grafos Coloração de Grafos O problema das quatro cores. A conjectura de colorir um mapa com no máximo quatro cores foi levantada em 1852 por Francis Guthrie; e provada em 1976 por K. Appel e W. Haken. O teorema de quatro cores afirma que todo mapa desenhado no plano pode ser colorido com no máximo quatro cores, de maneira, que regiões adjacentes tenham cores diferentes. Este problema pode ser reescrito na forma de um grafo e verificada a adjacência de cada vértice. Teoria dos Grafos Coloração de Grafos Teorema : Se um grafo planar admite um circuito hamiltoniano, então suas faces podem ser coloridas com quatro cores. Extraido de “Quatro Cores e Matemática” João Carlos V. Sampaio. Teoria dos Grafos Coloração de Grafos – Polinômio Cromático Dado k N e um grafo G, o valor é o número de maneiras que podemos colorir propriamente G com um conjunto [k]={1,2,…,k} de cores de forma que nem sempre todas as cores sejam usadas. Determine Determine A função também é chamada função cromática ou polinômio cromático de G quando é dado em função de k. Note que então . Se então Teoria dos Grafos Coloração de Grafos – Polinômio Cromático Determine o polinômio cromático dos grafos abaixo Teoria dos Grafos Coloração de Grafos – Polinômio Cromático Qual é o polinômio cromático de uma T com n vértices ? Proposição: Se T é uma árvore com n vértices então Teoria dos Grafos Coloração de Grafos – Polinômio Cromático Teorema: Se G é um grafo simples e então C4 Teoria dos Grafos Coloração de Grafos – Polinômio Cromático K3 Teoria dos Grafos Coloração de Grafos – Polinômio Cromático C4 Teoria dos Grafos/GrafosA11.pdf Teoria dos Grafos Edson Prestes Teoria dos Grafos Planaridade Existem três companhias que devem abastecer com gás, eletricidade e água três prédios diferentes através de tubulações subterrâneas. Estas tubulações podem estar à mesma profundidade ? Isto corresponde a perguntar: é possível desenhar um grafo bipartido com 2 conjuntos de três elementos cada, onde nenhuma aresta cruze outra. Podemos antecipar a resposta dizendo que é impossível ! Um grafo é planar se ele pode ser desenhado em um plano de tal forma que nenhuma aresta cruze as demais. O desenho deste grafo é chamado realização gráfica planar do grafo, ou simplesmente, realização planar. O estudo da planaridade é importante em diversas aplicações como, por exemplo, no desenvolvimento de circuitos impressos. Teoria dos Grafos Planaridade K5 e K3,3 não podem ser desenhados sem que algumas arestas se cruzem. Prova : Considere o desenho de K5 e K3,3 no plano. Seja C um spanning circle do grafo em questão. Se o desenho não tiver arestas que se cruzem, então C é desenhado como uma curva fechada. As cordas de C devem ser desenhadas dentro ou fora da curva. Uma corda é uma aresta cujos vértices final e inicial situam-se em uma curva C, ou seja, se C é um spanning circle de G então as cordas são as arestas de G que não foram incluidas em C. Duas cordas são conflitantes se elas têm seus pontos finais em uma ordem alternante. Quando este conflito existe, então estas cordas devem ser desenhadas uma dentro de C e a outra fora de C. Quantas cordas conflitantes tem o spanning circle de K3,3 ? Ele tem três cordas conflitantes. Podemos colocar no máximo 1 corda dentro e outra fora de C, então é impossível desenhar K3,3 sem que as cordas se cruzem. Quantas cordas conflitantes tem o spanning circle de K5 ? Ele possui 5 cordas conflitantes. No máximo duas cordas podem ficar dentro ou fora de C. Novamente é impossível desenha-las sem que elas se cruzem. Teoria dos Grafos Planaridade As cordas conflitantes do grafo K3,3 são ilustradas pelas linhas tracejadas. As linhas sólidas indicam o spanning circle. Teoria dos Grafos Planaridade Um grafo planar G divide o plano R2 em um conjunto regiões maximais, conhecidas como as faces de G. A região que engloba o grafo é chamada face ilimitada. As fronteiras destas faces correspondem às arestas de G. d(F1)=4 d(F2)=3 d(F3)=3 d(F1)=6 d(F2)=9 d(F3)=3 Cada aresta de G pertence à fronteira de uma ou duas faces de G. O grau (comprimento), de uma face f de G, representado por d(F) é igual ao número de arestas da fronteira de F. ** Aquelas arestas que fazem fronteira com apenas uma face são contadas duas vezes ** Teoria dos Grafos Planaridade Se d(Fi) corresponde ao grau da face i em um grafo planar G então Teoria dos Grafos Planaridade Um grafo dual G* é um grafo obtido a partir de um grafo G. As faces de G correspondem a vértices em G* e se e é uma aresta de G que situa-se entre as faces X e Y de G então a aresta dual e* será uma aresta que ligará os vértices x e y, correspondentes respectivamente às faces X e Y de G. O grau de uma face em G corresponde ao grau do vértice G* Proposição: todas as faces de um grafo G têm grau par sse o grafo dual G* é euleriano. Teoria dos Grafos Planaridade Um grafo é periplanar(outerplanar) se ele tem uma realização gráfica onde cada vértice do grafo faz fronteira com a face ilimitada. Proposição: os grafos K4 e K2,3 não são periplanares. Prova: Para mostrar que eles não são periplanares, um dos requisitos é mostrar que eles não possuem uma spanning circle. A existência de um spanning circle em um grafo G é condição necessária, mas não suficiente, para que G seja periplanar. Não ! Logo, K2,3 não é um grafo periplanar. O grafo K2,3 possui um spanning circle ? Teoria dos Grafos Planaridade O K4 possui um spanning circle. Entretanto, ele possui duas cordas conflitantes. Isto faz com que ambas as cordas não possam ser desenhadas na parte interna do grafo. Como uma corda é desenhada na parte externa do grafo, um dos vértices de G fica na parte interna de G e por conseguinte não faz fronteira com a face ilimitada O grafo K4 é periplanar ? Teoria dos Grafos Planaridade Teorema de Euler: seja G=(V,A) um grafo planar com |V(G)|=n e |A(G)|=m, p sendo o número de componentes conexos de G e f o número de faces de uma realização planar de G. Logo n-m+f=p+1 Prova: Considere inicialmente p=1. A prova utiliza indução no número de arcos. Para m=0 e um único vértice, n=1, temos apenas 1 face. Portanto, n-m+f=p+1 é igual a 1-0+1=1+1. Suponha que a equação seja verdadeira para um grafo com m-1 arcos, com m 1. Construa a realização planar de G acrescentando arcos incidentes ao subgrafo corrente. Antes da inserção do m-1-ésimo arco, nm-1-mm-1+fm-1=2 Teoria dos Grafos Planaridade Considere a inserção do m-ésimo arco. Este arco pode ser inserido de duas maneiras. 1a) assuma que uma de suas extremidades corresponde a um nó pertencente ao subgrafo existente e a outra extremidade corresponde a um novo nó. Observe que o número de faces não se altera, logo (nm-1+1)-(mm-1+1)+fm-1 =2 nm-mm+fm=2 Novo vértice Teoria dos Grafos Planaridade 2a) considere que as extremidades do m-ésimo arco correspondem aos nós já existentes no grafo em questão Neste caso, as duas extremidades devem estar na fronteira de uma mesma face. Portanto, esta face é dividida em duas pelo m-ésimo arco. Como não criamos nenhum novo vértice, o número de vértices não se altera. Então temos, nm-1-(mm-1+1)+(fm-1+1)=2 nm-mm+fm=2 Teoria dos Grafos Planaridade A prova para p>1 fica como exercício! Teoria dos Grafos Planaridade Seja G=(V,A) um grafo conexo planar, com |V(G)|=n e |A(G)|=m, onde m 2. Então m 3n-6 Usando a fórmula de Euler, temos Cada face de um grafo é delimitada por mínimo três arestas. Logo pois cada aresta é compartilhada por duas faces Teoria dos Grafos Planaridade Corolário k5 não é planar. Para provar que k5 não é planar, basta usar a desigualdade Sabemos que o número de arestas m de k5 é igual a 5.4/2=10 e que ele possui n=5 vértices. m 3n-6 Usando a desigualdade temos 10 3.5-6, vemos que k5 não é planar. Teoria dos Grafos Planaridade Corolário k3,3 não é planar. De forma análoga ao demonstrado anteriormente, agora cada face é delimitada por no mínimo 4 arestas, . Usando o Teorema de Euler, temos Sabemos que k3,3 possui 9 arestas e 6 vértices. Usando a desigualdade acima, vemos que 9 2.6 -4 é falsa. Portanto, k3,3 não é planar. m 3n-6A desigualdade vale quando o grafo é planar e possui triangulos. Se ele não possuir triangulos então devemos usar a seguinte desigualdade para verificar se ele é planar Teoria dos Grafos Planaridade Teorema de Kuratowski: um grafo G é planar sse não contém um subgrafo que é um grafo generalizado de K5 ou K3,3. Um grafo é planar sse não contém um subgrafo o qual por contração chegaria a K5 ou K3,3. O grafo de Petersen é planar ? Não! Pois ele pode ser reduzido ao grafo K5 por arco-contração. Teoria dos Grafos Planaridade O grafo de abaixo é planar ? Não! Pois ele pode ser reduzido ao grafo K3,3 por arco-contração. Teoria dos Grafos Planaridade Dois grafos são homeomorfos se eles podem ser obtidos do mesmo grafo inserindo novos vértices de grau 2 nos arcos. Assim, Teorema: um grafo é planar sse não contém subgrafo homeomorfo a k5 ou k3,3. Considere que existem pessoas que participam dos Comitês: 1 e 2; 1 e 4; 2 e 3; e 3 e 4. Teoria dos Grafos Coloração de Grafos Imagine que devamos reunir pessoas para participarem de um ou mais comitês de avaliação em uma determinada conferência. Qual deve ser o escalonamento de horários de atuações destes comitês para permitir que todos os membros inscritos participem de todas as atividades realizadas por seus respectivos comitês? Este problema é comumente tratado na área de grafos através de técnicas de coloração de grafos. Um grafo é k-colorível se ele tem uma k-coloração própria. Em uma coloração própria, cada classe é um conjunto independente. Portanto, um grafo k-colorível é um grafo k-partido. Teoria dos Grafos Coloração de Grafos Definição: Uma k-coloração de um grafo G é uma uma função de rotulamento f:V(G) S, onde S correspondem a um conjunto de cores e |S|=k. Os vértices associados a uma cor formam uma classe de cores. Uma k-coloração é própria se os vértices adjacentes do grafo têm rótulos (cores) diferentes. O número cromático é o menor k de forma que G seja k-colorível. A coloração de um grafo deve seu nome à aplicação de coloração de mapas. Grafos com loops não são coloríveis. Teoria dos Grafos Coloração de Grafos Um grafo é 2-colorível sse é ele um grafo bipartido. Qual é o número cromático do grafo de Petersen ? O grafo K2 é o único grafo 2-crítico, enquanto que os únicos grafos 3-críticos são os grafos que constituem ciclos ímpares. Teoria dos Grafos Coloração de Grafos Definição: Um grafo G é k-cromático se . Uma k-coloração de um grafo k-cromático é uma coloração ótima. Se para todo então G é k-crítico, ou seja, se G é crítico então Teorema: Para qualquer grafo G, o número cromático é no máximo uma unidade a mais que o maior grau de G, ou seja, Exemplo: Qualquer grafo completo garante e qualquer grafo estrela G com |V(G)|>2 garante Proposição: Considere o tamanho do maior clique de G; e o tamanho do maior conjunto independente de G. Para qualquer grafo G, Teoria dos Grafos Coloração de Grafos Em relação à primeira desigualdade, note que em um clique todos os vértices tem que ter cores distintas. Portanto se o grafo G possui um clique de tamanho máximo então seu número cromático será no mínimo igual a , podendo ser maior. Teoria dos Grafos Coloração de Grafos Em relação à segunda desigualdade, considere um grafo C5. O maior conjunto independente tem tamanho Sabemos que são necessárias 3 cores para colorir C5, então a desigualdade é verdadeira. Teoria dos Grafos Coloração de Grafos O problema das quatro cores. A conjectura de colorir um mapa com no máximo quatro cores foi levantada em 1852 por Francis Guthrie; e provada em 1976 por K. Appel e W. Haken. O teorema de quatro cores afirma que todo mapa desenhado no plano pode ser colorido com no máximo quatro cores, de maneira, que regiões adjacentes tenham cores diferentes. Este problema pode ser reescrito na forma de um grafo e verificada a adjacência de cada vértice. Teoria dos Grafos Coloração de Grafos Teorema : Se um grafo planar admite um ciclo hamiltoniano, então suas faces podem ser coloridas com quatro cores. Extraido de “Quatro Cores e Matemática” João Carlos V. Sampaio. Teoria dos Grafos Coloração de Grafos – Polinômio Cromático Dado k N e um grafo G, o valor é o número de maneiras que podemos colorir propriamente G com um conjunto [k]={1,2,…,k} de cores de forma que nem sempre todas as cores sejam usadas. Determine Determine A função também é chamada função cromática ou polinômio cromático de G quando é dado em função de k. Note que então . Se então Teoria dos Grafos Coloração de Grafos – Polinômio Cromático Determine o polinômio cromático dos grafos abaixo Teoria dos Grafos Coloração de Grafos – Polinômio Cromático Qual é o polinômio cromático de uma T com n vértices ? Proposição: Se T é uma árvore com n vértices então Teoria dos Grafos Coloração de Grafos – Polinômio Cromático Teorema: Se G é um grafo simples e então C4 Teoria dos Grafos Coloração de Grafos – Polinômio Cromático K3 Teoria dos Grafos Coloração de Grafos – Polinômio Cromático C4 Teoria dos Grafos/GrafosA2.pdf Teoria dos Grafos Edson Prestes Teoria dos Grafos Um passeio entre os nós i e j é uma seqüência alternada de nós e arestas que começa no nó i e termina no nó j. Introdução Um exemplo de passeio entre os nós 1 e 4 do grafo G1 é (1,(1,3),3,(2,3),2,(1,2),1,(1,4),4). Poderíamos pensar que apenas a ordem dos nós é importante. Entretanto, podemos ter passeios diferentes com a mesma seqüência de nós. G1 G2 Por exemplo, no grafo G2 temos os seguintes passeios entre os nós 3 e 4: (3,d,2,a,4) , (3,c,2,a,4) Teoria dos Grafos Um caminho é um passeio que não contém nós repetidos. Entre os nós 1 e 4 do grafo G1 temos os seguintes caminhos (1,4),(1,2,4),(1,3,2,4). Introdução G1 O comprimento de um caminho entre os vértices u e v é a quantidade de arestas presentes no caminho. Se existirem mais de um caminho de u a v, então o comprimento do caminho de u a v será igual ao menor comprimento dentre todos os caminhos de u a v. Teoria dos Grafos Um circuito é um passeio fechado, ou seja, o nó de partida é igual ao nó de chegada. Um ciclo é um caminho fechado, isto é , um passeio que contém exatamente dois nós iguais: o primeiro e o último. Ciclos de comprimento 1 são laços(loops). Uma característica interessante de um ciclo é que o número de arestas pertencentes a ele é igual a número de vértices. Introdução Teoria dos Grafos Introdução - Subgrafo O grafo H é um subgrafo de G, denotado por se e Se temos , ou seja, H é um subgrafo próprio de G. Um subgrafo gerador de G é um subgrafo H, com V(H)=V(G). Teoria dos Grafos Introdução – Grafo Conexo/Desconexo Um grafo é conexo se existe um caminho entre qualquer par de nós, caso contrário ele é chamado desconexo. Por exemplo, se não existir um caminho entre um nó p e qualquer outro nó do grafo, então este grafo é chamado desconexo. Dois nós estão conectados se existe um caminho entre eles no grafo. p Não, pois ele está contido no subgrafo formado pelos nós u,v,w,x,y e arestas (u,v), (v,w),(w,x),(x,y),(y,u) e (u,x). O grafo possui 2 componentes conexos. O primeiro é formado pelos nós u,v,w,x,y e arestas (u,v),(v,w),(w,x),(x,y),(y,u) e (u,x) e o segundo unicamente formado pelo nó p. Teoria dos Grafos Introdução – Componentes Conexos Os componentes conexos de um grafo são os subgrafos conexos maximais deste grafo, ou seja, são os subgrafos conexos que não estão estritamente contidos em outros subgrafos conexos. p O subgrafo formado pelos vértices u e v juntamente com a aresta (u,v) corresponde a componente conexo ? Teoria dos Grafos Introdução – Componentes Conexos Quantos componentes conexos o grafo abaixo possui ? Dois! Teoria dos Grafos Introdução – Grafo totalmente conexo/desconexo Grafo Totalmente desconexo Um grafo totalmente desconexo tem todos os seus vértices com grau zero. Quantas arestas um grafo completo (Kn) com n vértices possui ? Grafo Completo ou Completamente Conexo Um grafo completo de n vértices, denotado por Kn, possui a característica de que todo vértice do grafo é adjacente aos demais. Ele possui exatamente n(n-1)/2 arestas. Teoria dos Grafos Introdução – Conjunto Independente Um conjunto independente (maximal) em um grafo é um conjunto de vértices não adjacentes entre si que não está estritamente contido em outros conjuntos independentes. O tamanho do maior conjunto independente é chamado número de independência, denotado por α(G) O Grafo abaixo mostra um conjunto independente de tamanho 2 formado pelos vértices {u,w} Existe mais algum ? Teoria dos Grafos Introdução – Conjunto Independente número de independência α(G)=6 outros conjuntos {1,3,5,7}, {4,6} Teoria dos Grafos Introdução – Cliques Um clique (clique maximal) de um grafo é um conjunto de vértices adjacentes entre si que não está estritamente contido em outros cliques (conceito similar para dígrafos). O tamanho do maior clique de (dí)grafo G é chamado número de clique, ω(G). Um clique de G é um subgrafo completo de G. Quantos cliques os grafos abaixo possuem ? 2 cliques, ω(G) = 3 4 cliques, ω(G) = 3 Teoria dos Grafos Introdução – Cliques ω(G) = 4 ω(G) = 4 Teoria dos Grafos Introdução – Grafo Regular Um grafo G=(V,A) é regular se todos os vértices de G possuírem o mesmo grau, i.e., δ(G) =Δ(G)=d(v) ∀ v ∈ V Quantas arestas são necessárias para desenhar um grafo regular de 9 vértices, onde o grau de cada vértice é igual a 3 ? Observe que todo grafo completo é regular de grau n-1, onde n corresponde ao número de vértices Não é possível ! E um grafo com 10 vértices ? Desenhe! Teoria dos Grafos Introdução – Grafo Regular Um grafo regular com 10 vértices, onde cada vértice tem grau 3, também é chamado de 3-regular. Outro exemplo : grafo 2 - regular Teoria dos Grafos Introdução – Grafo Ciclo Um grafo ciclo de n(>2) vértices, Cn, é um grafo simples 2-regular Teoria dos Grafos Introdução – Grafo Roda Um grafo roda Wn, com n>2, e igual ao grafo Cn adicionado de mais um vertice, o qual é adjacente a todos os demais. Um grafo Wn possui n+1 vertices e 2n arestas, onde o vertice adicionado ao Cn possui grau igual a e os demais vertices grau igual a 3. Teoria dos Grafos Introdução – Grafo Bipartido Um grafo G é bipartido se seus vértices podem ser separados em dois conjuntos independentes de tal forma que toda a aresta do grafo liga sempre dois vértices, um de cada conjunto. Neste caso, o conjunto de vértices pode ser dividido em dois conjuntos V1={ y,u,v} e V2={x,z,w}. Teoria dos Grafos Introdução – Grafo Bipartido Considere um grafo bipartido constituído dos conjuntos Vj e Vk. Se todo vértice estiver ligado a todo vértice então temos um grafo bipartido completo G, chamado de biclique e denotado por Kr,s, onde r = |Vj| e s=|Vk|. Quantos vértices e quantas arestas possui um biclique ? Ele possui r+s vértices e r.s arestas. Teoria dos Grafos Introdução – Grafo K-partido Um grafo G é k-partido se ele possuir k conjuntos independentes. Logo, um grafo G bipartido é um grafo com 2 conjuntos independentes, portanto, ele é 2-partido. Um grafo G = (V,A) é chamado k-partido se os seguintes criterios forem obedecidos • for possível particionar o conjunto de vertices em k conjuntos não vazios V1, V2, ... Vk, de forma que eles sejam disjuntos dois a dois e a união dos elementos destes conjuntos seja o conjunto de vertices original. • cada aresta a∈A, tenha extremidades em conjuntos distintos. • k é o menor inteiro que ainda garante os criterios anteriores, caso contrário qualquer grafo com n vertices seria um grafo n partido. Teoria dos Grafos Introdução – Grafo K-partido Teoria dos Grafos/GrafosA3.pdf Teoria dos Grafos Edson Prestes Teoria dos Grafos Introdução – Grafo Estrela Um grafo estrela é um grafo bipartido de n vértices que possui um conjunto independente com um único vértice e o outro com n-1 vértices Quantos grafos estrelas podemos construir com um conjunto de n vértices. Assumindo que todos os vértices têm um rótulo diferente ? n grafos E se considerarmos que todos os vértices são iguais, ou seja, possuem um mesmo rótulo ? 1 grafo. Teoria dos Grafos Introdução – Grafo K-Cubo Um k-cubo,Qk, são grafos bipartidos cujos vértices são k-tuplas de 0's e 1's, onde os vértices adjacentes diferem em exatamente uma coordenada. O grafo abaixo ilustra um 3-cubo. Quantos vértices e quantas arestas possui um k-cubo ? Ele possui 2k vértices e k 2k-1 arestas. Teoria dos Grafos Introdução – Aplicações Redes de Computadores Qual é a melhor maneira de interligarmos um conjunto de computadores de forma a minimizar o tempo de transmissão de dados? Teoria dos Grafos Introdução – Aplicações Atribuição de Tarefas Dado um conjunto de m tarefas e m operários, é possível atribuir exatamente uma tarefa para cada operário de modo que todas as tarefas sejam realizadas? Cada operário tem um conjunto de habilidades {Oi} para realizar um sub conjunto de tarefas. Teoria dos Grafos Introdução – Aplicações Reconhecimento de Gestos Teoria dos Grafos Introdução – Aplicações Decomposição Aproximada Teoria dos Grafos Introdução – Aplicações Decomposição Topológica Teoria dos Grafos Introdução – Aplicações Banco de Dados Teoria dos Grafos Introdução – Aplicações Traçado de um circuito impresso Teoria dos Grafos Introdução – Representação Dado um grafo G=(V,A), a sua matriz de incidência B=[bi,j] é uma matriz |V| x |A| que associa os vértices às arestas de G. Cada entrada bi,j associa o vértice i à aresta j, assumindo os seguintes valores O valor 0 indica que a aresta b não é incidente ao vértice a. O valor 1 informa que o vértice a é incidente à aresta b e que a aresta b Matriz de Incidência Teoria dos Grafos Introdução – Representação A matriz de adjacência M=[mi,j] simétrica n x n que armazena o relacionamento entre os vértices do grafo entre os nós de um grafo. Matriz de Adjacência Teoria dos Grafos Introdução – Representação Uma lista de adjacência armazena o relacionamento entre os vértices de um grafo em uma estrutura de listas. Note que para listar todos os nós adjacentes a um nó ni bastar percorrermos a sua lista encadeada. Se quisermos saber se um nó ni é adjacente ao nó nk, basta realizar uma busca linear na lista associada a ni. |* Teoria dos Grafos Introdução – Representação Mostre que com que n vértices distintos podemos formar grafos simples (aquele que não possui laços ou mais de uma aresta ligando o mesmo par de vértices). Em um grafo simples, cada par de vértices dá origem ou não a uma aresta. Sabemos que um grafo de n vértices possui no máximo arestas. Logo, temos grafos com nenhuma aresta, grafos com 1 aresta,..., grafos com m arestas (grafo completo). Somando estes resultados, Teoria dos Grafos Introdução – Representação Mostre que todo passeio de u até v contém um caminho de u até v. Considere um passeio de comprimento l de u até v. Se l = 0 então temos um passeio sem nenhuma aresta. Isto denota que o caminho entre u e v também tem comprimento igual a 0. Se l > 0, temos que considerar o seguinte. Se o passeio de u a v não possuir nenhum vértice que tenha sido visitado duas vezes, então ele corresponde a um caminho entre u e v. Teoria dos Grafos Introdução – Representação Se existe um vértice w que tenha sido visitado mais que uma vez, podemos remover as arestas e vértices entre as duas aparições de w. Se existirem mais vértices que tenham sido visitados mais que uma vez o processo é repetido. Isto produz um passeio mais curto onde cada vértice é visitado uma única vez. Logo existe nesta situação um caminho entre u e v. Teoria dos Grafos Introdução – Representação Mostre que todo grafo com n vértices e k arestas, onde n > k, tem no mínimo n-k componentes Um grafo com n vértices com nenhuma aresta tem n componentes. Cada aresta reduz a quantidade de componentes em 1 unidade. Então, quando k arestas tiverem sido adicionadas ao grafo, o número de componentes será no mínimo n-k. Teoria dos Grafos/GrafosA4.pdf Teoria dos Grafos Edson Prestes Teoria dos Grafos Introdução – Representação Mostre que todo grafo com n vértices e k arestas, onde n > k, tem no mínimo n-k componentes Um grafo com n vértices com nenhuma aresta tem n componentes. Cada aresta reduz a quantidade de componentes em 1 unidade. Então, quando k arestas tiverem sido adicionadas ao grafo, o número de componentes será no mínimo n-k. Teoria dos Grafos Introdução – Representação Mostre que um grafo G com n vértices e c componentes, tem uma quantidade de arestas k que satisfaz a seguinte desigualdade O limite inferior foi mostrado anteriormente. O limite superior é definido da seguinte maneira. Considere a situação extrema, onde temos (c-1) componentes correspondendo a (c-1) vértices de grau igual a 0; e n-c+1 vértices constituindo um grafo completamente conexo. Este grafo irá possuir Teoria dos Grafos Introdução – Representação Mostre que todo grafo simples com dois ou mais vértices tem pelo menos dois vértices de mesmo grau Considere um grafo com n vértice. Se o grafo é simples então o grau de cada vértice deve variar de 0 a n-1. Se existir um vértice de grau 0 então não existe um vértice de grau n-1, e vice versa. Logo, teremos n-1 valores de graus a associar a n vértices. Usando o principio de Dirichlet, podemos considerar n caixas rotuladas com os valores de graus de 0 a n-1. Porém sabendo que apenas n-1 caixas serão preenchidas. Distribuindo n-1 vértices em cada uma das n-1 caixas de acordo com seu respectivo grau fará com que cada uma das caixas válidas seja preenchida. O n-ésimo vértice será associado a uma caixa que já possui um elemento. Logo, a caixa escolhida terá 2 vértices, indicando que existem dois vértices com mesmo grau. Dois grafos G e G' são isomorfos, ou seja, se eles apresentam as mesmas propriedades estruturais. Teoria dos Grafos Definição: Dois grafos G e G' são isomorfos se existe uma função bijetora tal que G G’ 1 3 2 Introdução – Isomorfismo Os grafos abaixo são isomorfos ? Teoria dos Grafos Sim! Introdução – Isomorfismo Os grafos abaixo são isomorfos ? Teoria dos Grafos Não! O grafo G é bipartido e o G’ não é . G G’ Introdução – Isomorfismo Os grafos abaixo são isomorfos ? Teoria dos Grafos Sim! Introdução – Isomorfismo Os grafos abaixo são isomorfos ? Teoria dos Grafos Não! Introdução – Isomorfismo A relação de isomorfismo é uma relação de equivalência sobre o conjunto de grafos simples. Propriedade reflexiva: uma permutação da identidade dos vértices de G é um isomorfismo de G para si próprio. Teoria dos Grafos Introdução – Isomorfismo Propriedade simétrica: Se é uma função que define o isomorfismo entre G e G', então f -1 é a função que define o isomorfismo entre G' e G. Logo, temos que Propriedade de Transitividade: Suponha que as funções e definam a relação de isomorfismo entre os grafos G e H; e H e M, respectivamente. Teoria dos Grafos Introdução – Isomorfismo Sabemos que e que Como f define uma relação de isomorfismo, se , então existe uma aresta tal que f(u)=x e f(v)=y. Logo, .Portanto, a composicão lof define a relação de isomorfismo entre G e M, ou seja, Uma relação de equivalência divide um conjunto de grafos em classes de equivalência, onde dois grafos pertencem ao mesmo conjunto sse eles são isomorfos. Uma classe isomórfica de grafos é uma classe de equivalência de grafos regida por uma relação de isomorfismo. Um exemplo de classe isomórfica é a classe chamada grafo de petersen. Teoria dos Grafos Introdução – Isomorfismo Um grafo de Petersen é um grafo simples não orientado gerado usando o seguinte conjunto S={1,2,3,4,5}. Seus vértices estão associados a subconjuntos de dois elementos de S. Os vértices formados a partir destes subconjuntos serão conectados por uma aresta se seus subconjuntos correspondentes forem disjuntos. Teoria dos Grafos Introdução – Grafo de Petersen O grafo abaixo é isomórfico ao grafo de Petersen ? Teoria dos Grafos Introdução – Grafo de Petersen Mostre que dois vértices não adjacentes em um grafo de Petersen têm exatamente 1 vizinho em comum. Teoria dos Grafos Introdução – Grafo de Petersen Dois vértices A e B não adjacentes no grafo de Petersen são subconjuntos de 2 elementos que compartilham um único elemento. Um vértice adjacente tanto à A quanto à B tem que ser um subconjunto disjunto dos dois subconjuntos associados à A e à B. Como estes dois vértices são escolhidos a partir do conjunto {1,2,3,4,5}, a quantidade de elementos resultante da união dos subconjuntos associados a eles é igual a 3. Então existe exatamente uma única combinação de 2 elementos para o terceiro vértice de forma que ele seja adjacente tanto ao vértice A quanto ao vértice B. Teoria dos Grafos Introdução – Automorfismo Um automorfismo de um grafo G é um isomorfismo de G para si próprio. Os automorfismos de G são as permutações de V(G) que podem ser aplicadas a ambas as linhas e colunas da matriz de adjacência sem mudar a adjacência entre os vértices de G. Considere um grafo G representado pela matriz de adjacência abaixo Teoria dos Grafos Introdução – Automorfismo G possui 2 automorfismos: ele próprio e a permutação que mapeia o vértice 1 para o vértice 4 e o vértice 2 para o vértice 3. Realizando o mapeamento Re-arranjando linhas e colunas Teoria dos Grafos Introdução – Automorfismo Realizando o mapeamento Re-arranjando linhas e colunas Apenas trocar a identidade do vértice 1 pela identidade do 4 não é um automorfismo de G. Embora este grafo seja isomórfico ao grafo G, ele não é um automorfismo de G. Problema 1 Desenvolver um algoritmo que receba como entrada um grafo G e produza como saída α(G) e ω(G), assim como os conjuntos de vértices que deram origem a estas medidas. A descrição do grafo deve ser feita através de arquivo texto. Entrega 08/06 Teoria dos Grafos Trabalho - Definição Problema 2 Dado um mapa composto por obstáculos, uma posição inicial e uma posição final, construa uma RRT que encontre um caminho livre de obstáculos entre a posição final e a posição inicial. 1 ponto extra se a implementação funcionar no simulador do robô. Links uteis http://msl.cs.uiuc.edu/rrt/about.html http://msl.cs.uiuc.edu/~lavalle/papers/Lav98c.pdf http://www.golems.org/papers/AkgunIROS11-sampling.pdf http://planning.cs.uiuc.edu (temos o livro na biblioteca :) Informações úteis sobre o simulador http://www.inf.ufrgs.br/~prestes/Courses/Robotics/instrucoes.rtf Falar com o Edson ou com membros do grupo de Edson. Entrega 08/06 Teoria dos Grafos Trabalho - Definição Teoria dos Grafos/GrafosA5.pdf Teoria dos Grafos Edson Prestes Teoria dos Grafos Introdução – Automorfismo Um automorfismo de um grafo G é um isomorfismo de G para si próprio. Os automorfismos de G são as permutações de V(G) que podem ser aplicadas a ambas as linhas e colunas da matriz de adjacência sem mudar a adjacência entre os vértices de G. Considere um grafo G representado pela matriz de adjacência abaixo Teoria dos Grafos Introdução – Automorfismo G possui 2 automorfismos: ele próprio e a permutação que mapeia o vértice 1 para o vértice 4 e o vértice 2 para o vértice 3. Realizando o mapeamento Re-arranjando linhas e colunas Teoria dos Grafos Introdução – Automorfismo Realizando o mapeamento Re-arranjando linhas e colunas Apenas trocar a identidade do vértice 1 pela identidade do 4 não é um automorfismo de G. ! Embora este grafo seja isomórfico ao grafo G, ele não é um automorfismo de G. Teoria dos Grafos Introdução – Mais sobre grafos.. Cintura A cintura de um grafo é o comprimento do menor ciclo do grafo. Um grafo sem ciclos tem uma cintura de comprimento infinito. ! Diâmetro de um grafo O diâmetro de um grafo consiste na maior distância entre dois vértices em um grafo. Teoria dos Grafos Introdução – Mais sobre grafos.. Deleções A operação de deleção consiste na retirada de vértices ou de arestas de um grafo. ! Considere um grafo G =(V,A). A retirada de um vértice v, representada por G-v, causa a retirada de todas as arestas incidentes a v. ! Enquanto que a retirada de uma aresta w=(u,v), representada por G-w, leva a quebra da adjacência dos nós u e v, se o grafo for simples. Teoria dos Grafos Introdução – Mais sobre grafos.. Se V1 é um subconjunto de V(G), então G-V1 é o grafo resultante da retirada de todos os vértices e de suas arestas incidentes. ! Esta operação leva ao grafo G', onde Se A1 é um subconjunto de A(G), então G-A1 é o grafo resultante da retirada das arestas . Esta operação leva ao grafo G'', onde V(G'')=V(G) e ! A(G'')=A(G)-A1 {(u,v) 2 A(G) | u, v 2 V(G’)} A operação de arco-contração, denotada por G/a, consiste na retirada da aresta a=(u,v) juntamente com seus vértices u e v, seguida da inserção de um novo vértice w e a re-ligação das arestas incidentes tanto a u quanto a v a este novo vértice. Teoria dos Grafos Introdução – Mais sobre grafos.. Qual é o resultado da execução da seqüência (((((G/a)/b)/c)/d)/e) no grafo G de Petersen ? Teoria dos Grafos Introdução – Mais sobre grafos.. Teoria dos Grafos Introdução – Mais sobre grafos.. Um vértice de corte é um vértice cuja remoção aumenta a quantidade de componentes do grafo. ! Uma aresta de corte, também chamada de ponte, quando removida aumenta a quantidade de componentes conexos do grafo. Um grafo induzido é um grafo obtido através da remoção de um conjunto de vértices. Teoria dos Grafos Introdução – Mais sobre grafos.. Conjunto desconector é o subconjunto de arestas de G cuja retirada torna G desconexo. Conjunto de corte de arestas é qualquer conjunto desconector minimal de G. A conectividade de arco λ(G) é o tamanho do menor conjunto de corte de arestas de G. Um grafo G é k-arco-conexo se λ(G)=k. Por definição λ(G)=0, se o grafo é trivial ou desconexo Conjunto separador é um subconjunto de vértices de G cuja retirada torna G desconexo. ! Conjunto de corte de vértices é qualquer conjunto separador minimal de G. ! A conectividade de vértice κ(G) é o tamanho do menor conjunto corte de vértices de G. Um grafo G é um grafo k-vértice-conexo se κ(G)=k. Por definição κ(G)=0, se G for desconexo ou trivial, e κ(Kn)=n-1. O grafo G1 é 2-arco-conexo(λ(G1)=2) e 1-vértice-conexo (κ(G1)=1). ! O grafo G2 é 1-arco-conexo(λ(G2)=1) e 1-vértice-conexo(κ(G2)=1). Teoria dos Grafos Introdução – Mais sobre grafos.. G1 G2 Determine a conectividade de arestas e vértices dos grafos abaixo Teoria dos Grafos Introdução – Mais sobre grafos.. Mostre que para qualquer G Teoria dos Grafos Mais sobre grafos.. Mostre que um grafo é bipartido sse ele não possuir ciclos de tamanho impar è Seja G um grafo bipartido e V(G) o conjunto de vértices de G correspondente à união de dois subconjuntos disjuntos V1 e V2 de modo que as arestas de G unem apenas vértices de diferentes subconjuntos. Considere um ciclo C em G, onde C é denotado pela seguinte seqüência de vértices v1,v2, v3, ..., vn, v1. Suponha que ,então , , seja uma seqüência alternada entre os dois subconjuntos. Como o ultimo vértice é v1, e a seqüência é alternada entre os subconjuntos V1 e V2. Podemos constatar que o penúltimo vértice vn possui índice n par. Como um caminho com um número par de vértices possui exatamente um número ímpar de arestas. Logo, a adição da aresta de retorno (vn,v1) faz com que este caminho possua um comprimento par, dado pelo número par de arestas. Teoria dos Grafos Mais sobre grafos.. Este ciclo pode ser decomposto em dois subcaminhos, um entre v e u, e outro entre u e v', juntamente com a aresta que liga os vértices v e v'. Como v e v' estão no mesmo conjunto, os caminhos entre v e u e entre v' e u serão ou pares ou impares. ç A prova de que G é bipartido é como segue. Considere um vértice u, e uma função f(v) que retorna o comprimento do menor caminho de u até v. Faça e . Considere uma aresta (v,v'), onde ou , ou seja, uma aresta que liga vértices de um mesmo conjunto. Considere também um ciclo que passa pelo vértice u. Teoria dos Grafos Mais sobre grafos.. Portanto, a soma dos comprimentos destes caminhos resultará em um número par que adicionado de 1, correspondente a aresta (v,v'), leva a um caminho de comprimento impar. Como estamos afirmando que nenhum ciclo de tamanho impar existe, logo a aresta (v,v') não existe. Por conseguinte, tanto X quanto Y são conjuntos independentes, logo o Grafo G é bipartido. ! Obs: para sabermos se um grafo não é bipartido, basta verificarmos se existe algum ciclo de comprimento impar. Teoria dos Grafos União de Grafos A união de dois grafos G1 e G2 é definida como Teoria dos Grafos Complemento de Grafos O complemento de um grafo G, denotado por , é um grafo com e G O complemento de um grafo completo é um grafo nulo. Enquanto que o complemento de um grafo bipartido é a união de dois grafos completos. Teoria dos Grafos Complemento de Grafos Um grafo é autocomplementar se ele for isomorfico ao seu complemento. O grafo abaixo é autocomplementar ? G Sim! Teoria dos Grafos Complemento de Grafos Mostre que para qualquer Grafo G com 6 pontos, G ou possui um triângulo Considere um vértice v de V(G). Sem perda de generalidade, podemos assumir v é adjacente a outros três vértices u1, u2 e u3 em G. Se dois destes vértices forem adjacentes, então existirá um triangulo formado por estes dois e por v. Caso contrário, estes três vértices não serão adjacentes entre si em G, mas serão em Teoria dos Grafos/GrafosA6.pdf Teoria dos Grafos Edson Prestes Teoria dos Grafos Complemento de Grafos Mostre que para qualquer Grafo G com 6 pontos, G ou possui um triângulo Considere um vértice v de V(G). Sem perda de generalidade, podemos assumir v é adjacente a outros três vértices u1, u2 e u3 em G. ! Se dois destes vértices forem adjacentes, então existirá um triangulo formado por estes dois e por v. ! Caso contrário, estes três vértices não serão adjacentes entre si em G, mas serão em Teoria dos Grafos Decomposição Uma decomposição de um grafo é uma lista de subgrafos tal que cada aresta aparece exatamente uma única vez em um único subgrafo. Teoria dos Grafos Matching Um matching em um grafo G é um conjunto de arestas que não formam loops e que não compartilham vértices entre si. ! Um vértice incidente às arestas de um matching M é dito saturado por M. ! Um matching perfeito de G satura todos os vértices de G. Determine um matching para o grafo abaixo É um matching perfeito ? Sim! Teoria dos Grafos Matching O tamanho de um matching M é igual a quantidade de arestas de M. ! Um matching M de um grafo G é maximal se toda aresta que não participa de M é incidente a alguma aresta em M. ! Se M for o matching de maior cardinalidade de G então ele é chamado matching máximo. Teoria dos Grafos Matching Um caminho de alternante em um matching M é um caminho cujas arestas alternam entre aquelas que estão em M e aquelas que não estão em M. ! ! Um caminho alternante, cujos vértices extremos não são saturados por M, é um caminho de aumento de M. ! ! Quando M possuir um caminho de aumento P podemos trocar as arestas deste caminho, substituindo aquelas que não estão M pelas que estão. Isto irá aumentar em uma (1) unidade o tamanho do matching. ! ! Uma observação importante é que o matching máximo é caracterizado pela ausência de caminhos de aumento. Teoria dos Grafos Matching O matching do grafo abaixo, representado pelas arestas sólidas, é um matching maximal ou máximo ? Maximal! Caminho de aumento Teoria dos Grafos Cobertura de Vértices Uma cobertura de vértices de um grafo G é um subconjunto, Q, de vértices de G que contém no mínimo um vértice de cada aresta de G. ! Logo, podemos dizer que os vértices em Q cobrem A(G). Teoria dos Grafos Cobertura de Vértices A relação entre os problemas de matching e da cobertura de vértices corresponde a uma relação min-max, quando tomados sob a mesma instância de um problema. ! ! Quando a resposta para a maximização de um problema é igual a resposta para a minimização do outro sobre a mesma instância do problema então sabemos que o valor encontrado é ótimo. Ou seja, obtendo um matching máximo e uma cobertura mínima de vértices de mesmo tamanho provamos que cada um deles é ótimo. ! ! O teorema que rege esta relação para os problemas de matching e de cobertura é o teorema de König-Egervary. Este teorema afirma que para grafos bipartidos o tamanho do matching máximo é igual ao tamanho da menor cobertura de vértices. Teoria dos Grafos Cobertura de Vértices Na figura abaixo, tanto a cardinalidade do matching (denotado pelas arestas mais escuras) quanto a da cobertura de vértices (ilustrado pelos vértices cinzas) é a mesma e igual a 2. Note que a cardinalidade da cobertura proíbe matching com mais de 2 arestas; e o tamanho do matching proibe coberturas com menos que 2 vértices. Teoria dos Grafos Cobertura de Vértices Encontre a menor cobertura e o maior matching do grafo abaixo ? A cardinalidade da cobertura é igual a 5 enquanto que a cardinalidade do matching igual a 5 vértices. Teoria dos Grafos Grafos Eulerianos O problema das pontes de Königsberg é o primeiro e mais famoso problema em teoria dos grafos resolvido por Euler em 1736. Na cidade de Königsberg existiam sete pontes que cruzavam o rio Pregel estabelecendo ligações entre duas ilhas e entre as ilhas e as margens opostas do rio.! ! ! ! ! ! O problema consiste em determinar se é possível ou não fazer um passeio pela cidade começando e terminando no mesmo lugar, cruzando cada ponte exatamente uma única vez. Se isto for possível o grafo é chamado grafo Euleriano. Teoria dos Grafos Grafos Eulerianos Este problema é similar ao problema do carteiro chinês. Neste último, as arestas correspondem a trechos de ruas que o carteiro deve percorrer para entregar as cartas. ! ! O carteiro deve realizar a entrega das cartas de forma mais eficiente possível, ou seja, percorrendo o menor caminho. Teoria dos Grafos Grafos Eulerianos Se o grafo G é euleriano então qualquer circuito euleriano é ótimo, caso contrário algumas arestas serão percorridas mais de uma vez. ! ! Baseado na segunda situação, busca-se encontrar um percurso de peso mínimo no grafo que modela o problema.! ! Logo o nosso problema consiste em um problema de otimização onde devemos encontrar um circuito que contenha todas as arestas do grafo e cuja distância total seja mínima. Teoria dos Grafos Grafos Eulerianos O teorema de Euler caracteriza uma classe de grafos e ao mesmo tempo mostra como construir um circuito Euleriano.! Teorema: Um grafo conexo G=(V,A) é euleriano, sse, os graus de todos os nós de G são pares. Demonstração: Suponha que o grafo seja euleriano. Então G possui um circuito (passeio fechado) euleriano. Se contarmos para cada nó, a entrada e saída dele, ao final de todo percurso teremos um conjunto de números pares.! Suponha agora que temos um grafo G onde todos os seus nós têm grau par. Escolha um nó i qualquer e comece a percorre-lo sem repetir arestas, até não existirem arestas a serem percorridas, a partir do vértice corrente. ! Como todos os nós têm grau par então o último nó alcançado é o nó i. Se o circuito C contiver todos as arestas de G então a demonstração está concluída. Caso contrário, existirão arestas não percorridas. Teoria dos Grafos Grafos Eulerianos Como o grafo é conexo então existe um caminho entre qualquer par de vértices. Logo, existe algum caminho entre algum vértice do circuito até uma aresta q não incluída em C. ! Imagine que este caminho seja formado pela aresta (j,k), onde j pertence ao circuito C e k pertence a aresta q. ! Se isto ocorrer devemos percorrer o grafo a partir de j visitando todas as novas arestas sem acessar nenhuma aresta em C. Este novo circuito C' pode ser unido ao circuito C formando um único circuito. Agora basta percorrer C a partir de j e quando retornar a j começar a percorrer C‘.! Repetimos este processo até que todas as arestas tenham sido visitadas. No final teremos um único circuito formado pela união de vários circuitos. O circuito resultante é chamado euleriano, assim como o grafo. Teoria dos Grafos Grafos Eulerianos O grafo abaixo é euleriano? Se sim decomponha em ciclos. Teoria dos Grafos Grafos Eulerianos Baseado nesta idéia podemos afirmar que todo grafo par (cujos vértices possui grau par) pode ser decomposto em circuitos. ! Se removermos a condição de que o circuito tem que ser fechado então temos um grafo semi-euleriano. O grafo abaixo é euleriano ? Se sim determine um circuito euleriano. Euleriano Teoria dos Grafos Grafos Eulerianos O grafo abaixo é euleriano ? Se sim determine um circuito euleriano. ! Caso contrário se o grafo for semi-euleriano, determine um passeio que visite ! todos as arestas do grafo Um grafo semi-euleriano possui 2 vértices com grau impar. Um deles é o ponto de partida e o outro é o ponto de chegada. semi-euleriano Teoria dos Grafos Grafos Hamiltonianos Um grafo G é chamado Hamiltoniano quando possui um ciclo que inclui todos ! os vértices de G, ou seja, neste ciclo cada vértice aparece uma única vez, com ! exceção do vértice de partida. O grafo abaixo é hamiltoniano? Se sim, encontre o ciclo hamiltoniano. Teoria dos Grafos Grafos Hamiltonianos O problema do cálculo do ciclo hamiltoniano, embora semelhante ao problema do cálculo do circuito euleriano, é muito mais complexo pois não são conhecidas todas as condições necessárias e suficientes para que um grafo genérico contenha um ciclo hamiltoniano nem tampouco métodos eficientes para construir tal ciclo. ! ! Este problema está intimamente relacionado ao problema do caixeiro viajante, o qual consiste em encontrar um caminho que passe por todas as cidades uma única vez e retorne ao ponto de partida escolhendo para isso um caminho de custo mínimo. ! ! Este caminho consiste em um ciclo hamiltoniano de custo mínimo, onde a soma dos custos das arestas pertencentes ao ciclo é mínima. Teoria dos Grafos Grafos Hamiltonianos Verifique se o grafo abaixo é Hamiltoniano. Se for, mostre um ciclo hamiltoniano. Não é Teoria dos Grafos Grafos Hamiltonianos Verifique se o grafo abaixo é Hamiltoniano. Se for, mostre um ciclo hamiltoniano. Hamiltoniano Teoria dos Grafos Grafos Hamiltonianos Se o grafo não contiver um ciclo hamiltoniano, mas contiver um caminho entre dois vértices de forma que cada vértice do grafo seja visitado uma única vez, então este grafo é chamado semi-hamiltoniano. O grafo abaixo é hamiltoniano ? semi-hamiltoniano, euleriano, semi-euleriano? Hamiltoniano e semi-euleriano semi-hamiltoniano e semi-euleriano Teoria dos Grafos Traga na próxima aula as condições necessárias e suficientes para que um grafo seja hamiltoniano (Olhar livro do Harary ou West).! Grafos Hamiltonianos Teoria dos Grafos/GrafosA7.pdf Teoria dos Grafos Edson Prestes Teoria dos Grafos Dígrafos As arestas possuem a função de indicar o relacionamento(espacial, comportamental, temporal) entre os elementos de um grafo. Em diversas situações esta relação não é simétrica, ou seja, par (a,b) não implica (b,a). Ex: fluxo de carros em uma rodovia de mão única. Esta restrição é indicada no grafo determinando uma direção para cada aresta, a qual agora é chamada de arco. Um dígrafo D=(V,A) é constituído de um conjunto finito de vértices V e um conjunto A de arcos, onde cada arco corresponde a um par ordenado de vértices. Teoria dos Grafos Dígrafos dígrafo Podemos dizer que um arco é incidente do nó i para o nó j, ou divergente do nó i e convergente ao nó j. Um grafo orientado difere de um dígrafo por não possuir pares simétricos de arestas direcionadas. Grafo orientado A Figura abaixo ilustra um dígrafo de 6 vértices. Teoria dos Grafos Dígrafos O grau de entrada de um vértice v, d-(v), é o número de arcos que são convergentes a v. O grau de saída de um vértice v, d+(v) , é o número de arcos que são divergentes de v. Vértice Sumidouro d+(v6)=0 Vértice Fonte d-(v2)=0 Teoria dos Grafos Dígrafos – Matrizes de Adjacência e Incidência Matriz de adjacência Matriz de incidência Quantidade de arcos de w para y Quantidade de arcos de y para w O arco a está convergindo para w O arco e está divergindo de y Teoria dos Grafos Dígrafos - Fluxogramas Teoria dos Grafos Dígrafos - Autômatos Teoria dos Grafos Dígrafos – Redes Neurais O caminho para um dígrafo é constituído de uma seqüência de nós e arcos, sem se importar com a orientação de cada arco. Existem o passeio orientado e o caminho orientado em dígrafos. São similares aos usados em grafos com a diferença de que a orientação dos arcos é levada em consideração . Tanto para o caminho quanto para o passeio orientado, os arcos devem se conectar entre si, ou seja, para cada par de arcos que atuam sobre um vértice, um diverge e o outro obrigatoriamente converge para o vértice, ou vice versa. Teoria dos Grafos Dígrafos Um caminho orientado de 4 a 6 pode ser {4,(4,5),5,(5,3),3,(3,6),6} Um caminho (não orientado) de 6 a 1 pode ser {6,(6,5),5,(5,4),4,(4,1),1}. Teoria dos Grafos Dígrafos A noção de isomorfismo é estendida aos grafos direcionados considerando a orientação dos arcos. O dígrafo A é isomórfico ao dígrafo B? Teoria dos Grafos Dígrafos A B C e ao dígrafo C? Sim! Não! A partir de um dígrafo G podemos encontrar um grafo subjacente G’ substituindo cada arco de G por uma aresta. Teoria dos Grafos Dígrafos Um dígrafo é fracamente conexo se seu grafo subjacente é conexo. Um dígrafo é fortemente conexo ou forte se para cada par de vértices u, v existe um caminho orientado de u para v. Os componentes fortes de um dígrafo são seus subgrafos maximais fortes. Teoria dos Grafos Dígrafos Encontre os componentes fortes do dígrafo abaixo. Teorema: Um grafo G conexo não direcionado pode ser transformado em um dígrafo D fortemente conexo sse G não contém nenhuma ponte. Teoria dos Grafos Dígrafos Prova Ida: Suponha um dígrafo D fortemente conexo cujo grafo G subjacente contém no mínimo uma ponte. Logo, G deve possui no mínimo dois vértices cuja ligação exige passar por essa ponte. Necessariamente essa ponte permite caminhar em uma única direção, por exemplo de um vértice vi para outro vértice vk , mas não permite o retorno de vk para vi. Portanto, D não pode ser fortemente conexo se G possuir uma ponte. Teoria dos Grafos Dígrafos Volta: Como o grafo subjacente G não contém nenhuma ponte, toda aresta faz parte de um ciclo. Suponha um ciclo C1 cujas as arestas são orientadas de tal maneira que seja possível percorrer o ciclo e voltar à origem. Observe que todo vértice em C1 é acessível a partir de qualquer outro. Considere outro ciclo C2 que tem no mínimo um vértice em comum com C1. Se orientarmos os arcos de C2 sem mudarmos a orientação dos arcos em C1, faremos com que qualquer vértice pertencente a união de C1 com C2 possa ser alcançado a partir de qualquer outro desta união, pois teremos um caminho fechado que passa por todos os vértices. Se isso for possível o dígrafo D é fortemente conexo. Teoria dos Grafos Dígrafos Teoria dos Grafos Dígrafos Verifique se o grafo abaixo pode ser transformado em um dígrafo fortemente conexo. Se puder então determine este dígrafo! Teoria dos Grafos Dígrafos Um passeio euleriano em um dígrafo é um passeio contendo todas os arcos do dígrafo. Um circuito euleriano é um passeio fechado. Um dígrafo é euleriano se ele tem um circuito euleriano. Os ciclos Bruijn são dígrafos eulerianos e hamiltonianos. Os vértices são strings de comprimento n formadas a partir de um alfabeto com m simbolos. O exemplo mostra o grafo construido usando um alfabeto binário. Dois vértices a e b estão ligados se os n-1 últimos elementos de a forem iguais aos n-1 primeiros elementos de b. Se isto for verdade então o arco que os conecta terá como rótulo o último elemento de b. 111 Teoria dos Grafos Dígrafos Os grafos de Bruijn podem ser usados para montar
Compartilhar