Teoria dos Grafos - Noções Básicas e Estruturas

Mario Leston Teoria dos Grafos Sumário 1 Noções básicas 5 2 Árvores 27 1 Noções básicas Grafos Um grafo é um objeto constituído de três ingredientes um conjunto de vértices um conjunto de arestas e uma função que leva cada aresta num par de vértices Formalmente um grafo é uma tripla V E ι em que V é um conjunto finito cujos elementos são chamados de vértices E é um conjunto finito cujos elementos são chamados de arestas ι a função de incidência é uma função que leva cada aresta num par não ordenado de vértices isto é ι E V 2 6 TEORIA DOS GRAFOS 3 É claro que tal convenção pode carre gar uma certa ambiguidade quando uma mesma aresta estiver envolvida em mais de um grafo 4 Duas funções f g X Y são iguais se fx gx para cada x X e uv quando ιe u v3 Os vértices u e v são as pontas de e Dizemos também que u e v incidem ou são incidentes em e e que u e v são vizinhos Vamos abusar um pouco da notação e escrever u e em vez de u ιe quando o vértice u é uma das pontas da aresta e v1 v2 v3 v4 v5 e1 e2 e3 e8 e4 e5 e6 e7 Figura 11 A figura exibe um dese nho de um grafo cujo conjunto de vérti ces é v1 v2 v3 v4 v5 e cujo conjunto de arestas é e1 e2 e3 e4 e5 e6 e7 e8 onde e1 v1v4 e2 v3v4 e3 v2v3 e4 v1v2 e5 v1v5 e6 v4v5 e7 v3v5 e8 v2v3 Observe que e3 e e8 têm as mesmas pon tas O corte de v2 v2 é o conjunto e3 e4 e8 A noção de igualdade é fundamental na matemática Não seria en tão diferente aqui Dizemos que os grafos G e H são iguais denotado não surpreendentemente por G H se VG VH EG EH e ιG ιH4 Um momento de reflexão o fará constatar que a noção de igualdade en volvendo grafos é um tanto quanto sem graça No momento apropri ado vamos introduzir a noção de isomorfismo Esta sim muito mais interessante e de fundamental importância uma vez que decidir se dois grafos são isomorfos é um problema ainda não muito bem compreen dido Alguns conceitos envolvendo grafos são extremamente intuitivos e formalizam relações corriqueiras envolvendo entidades da realidade Essa é uma das motivações que tornam o conceito tão atraente e reche ado de aplicações práticas Vamos fixar um grafo G na discussão que segue cujo propósito é o de definir uma série de funções sobre o conjunto dos vértices de um grafo Corte e grau de um vértice Seja u um vértice de G O corte de u denotado Gu é o conjunto das arestas de G que incidem em u Formalmente Gu e E u e A notação Gu é um tanto quanto pesada por isso quando não hou ver possibilidade de confusão e para simplificar vamos escrever u ou ainda mais simplesmente u O tamanho ou a cardinalidade de u denotada du é chamado de grau de u O grau mínimo de G denotado δG é o número mindv v V Exercício 11 Mostre que se G é um grafo e G G 1 então existe u V tal que du 3 Seja X V Cada aresta que possui ambas as pontas em X é dita induzida por X O conjunto das arestas induzidas por X é denotado por EGX ou simplesmente EX isto é EX e E x1 x2 X e x1x2 O subgrafo de G induzido por X denotado GX é o grafo X EX ιEX Seja agora F E O subgrafo de G induzido por F denotado GF é o grafo e F je F ιμF ou seja é o grafo cujo conjunto dos vértices é constituído dos vértices que incidem em alguma aresta de F e cujo conjunto das arestas é F Neste último caso seja conveniente confundir o conjunto de arestas F com o grafo GF hábil este será recorrente durante o texto sempre que não houver possibilidade de confusão e dHv dv para cada v V x y Então dv uV Vxy dv dx dy vV Vxy dHv dHx 1 dHy 1 vV dv 2 2I 2 2I 1 G Exercício 12 Prove o Corolário 11 por indução no número de arestas Solução Seja IG o conjunto dos vértices de grau ímpar de um grafo G Vamos provar por indução em G que se G é um grafo então I é par Seja G um grafo Suponha primeiro que G 0 Então IG onde IG é par Suponha agora que G 1 Escolha uma aresta e x y de G Considero o grafo H G e Como H G então por hipótese da indução IH é par Observe que dHx dGx 1 dHy dGy 1 e dHz dGz para cada z V x y Temos os seguintes casos Caso 1 x y IH Neste caso IG IH 2 e portanto IG é par Caso 2 x y IH Neste caso IG IH x y onde IG IH 2 e portanto IG é par Caso 3 x y IH 1 Ajuste a notação de tal forma que x IH e y IH Então IG IH x y onde IG IH e portanto IG é par os vértices que imediatamente precedem e sucedem a aresta na sequência Formalmente um caminho é uma sequência digamos P v0 e1 v1 ek vk em que k 0 v0 vk V e e1 ek E e ei vi1vi para cada i k Vamos escrever VP ou VP para denotar o conjunto dos vértices de P isto é v0 vk e EP por EP para denotar o conjunto das arestas de P isto é e1 ek Dizemos que P é um gmv0 vkcaminho ou caminho de v0 até vk ou ainda um caminho que inicia em v0 e vk e que v0 é o início ponto inicial de P e vk é o término ou ponto final de P O comprimento de P denotado por ℓP é o número k11 É conveniente muitas vezes confundir um caminho P com o grafo VP EP μP Assim por exemplo se u VP então dPu é o grau de u no grafo P Com esta identificação podemos escrever P em vez de VP e P em vez de EP Às vezes vamos nos interessar tanto somente pelos vértices de um caminho quando então vamos enumerar até somente as arestas de um caminho vamos pois também enumerar as arestas No primeiro caso dizemos que um caminho é um caminho de vértices no segundo um caminho de arestas Muitas vezes vamos nos interessar por certos segmentos de P Assim para 0 i j k escrevemos Pvi vj para denotar a sequência vi ei1 ej vj que constitui um caminho que une os vértices vi e vj Finalmente escrevemos P1 para denotar o reverso de P isto é vk ek e1v0 Prova Para cada inteiro nãonegativo k e cada par x y de vértices seja Pkx y o conjunto dos dycaminhos de G de comprimento k É claro que P0x y x para cada x V e P0x y para cada x y V Além disso para cada inteiro k 0 e cada x y V Pkx y z V Pk1x z z y z E onde Px y z V Pk1x zAcx y A prova é por indução em k O resultado é claro quando k 0 Suponha então que k 0 Por hipótese de indução AkGx y Pk1x y Sejam x y vértices de G Então Pkx y z V Pk1x zAcz y z V Ak1Gx zAcz y AkGx y como queríamos NOÇÕES BÁSICAS 13 Figura 15 A figura ilustra um grafo que é um caminho simples Figura 16 A figura ilustra um grafo que é um ciclo possui pelo menos um ciclo é o comprimento de um ciclo de compri mento mínimo de G Finalmente dizemos que um grafo G é um caminho simples um ci clo se existe um caminho simples um ciclo P em G tal que G VP EP ι Um caminho simples maximal em um grafo G é um caminho sim ples P tal que todo vizinho de cada uma das pontas de P está em P Note que um caminho simples de comprimento máximo é maximal mas nem todo caminho maximal é máximo Exercício 14 Prove que todo caminho simples de comprimento máximo de um grafo é um caminho simples maximal Solução Suponha que P é um caminho simples de comprimento má ximo de um grafo G Sejam x e y a ponta inicial e a ponta final de P Suponha que z V VP Como P tem comprimento máximo não existe aresta de G com pontas x e z e nem com pontas y e z Segue daí que Γx Γy VP Lema 12 Se G é um grafo e δG 2 então G possui ciclo Prova Seja P x0e1x1 ekxk um caminho simples maximal de G A maximalidade de P aliada a δG 2 implica que k 1 Como δG 2 então existe uma aresta digamos f que incide em x0 e que é distinta de e1 A maximalidade de P implica que a outra ponta digamos y de f é um dos vértices de P Portanto existe i tal que 1 i k e xi y Agora x0e1x1 eixifx0 é um ciclo de G Exercício 15 Mostre que se um grafo possui um circuito de com primento ímpar então também possui um ciclo de comprimento ímpar Solução Vamos provar por indução em ℓC que se C é um circuito ímpar de um grafo G então existe um ciclo K de comprimento ímpar de G tal que VK VC e EK EC Seja G um grafo Suponha que C u0e1u1 ekuk é um circuito de comprimento ímpar de G Se C é um ciclo então não há mais nada a provar Suponha que C não é um ciclo Escolha i e j tais que i j ui uj e Cui uj1 é um caminho simples Ora K uiei1ui1 ejuj é um ciclo Se ℓK é ímpar então não há mais nada a provar Suponha que ℓK é par Segue daí que C u0e1u1 eiuiej1uj1 ekuk é um circuito ímpar Além disso ℓC ℓC Assim por hipótese de indução existe um ciclo K de comprimento ímpar tal que VK VC e EK EC donde VK VC e EK EC como queríamos 14 TEORIA DOS GRAFOS 14 Lembrese que dada uma coleção não vazia X de subconjuntos de um certo conjunto dizemos que um elemento X X é maximal se Y X Y X para cada Y X 15 Ou ainda GY não é conexo sempre que Y V é tal que Y X Figura 17 A figura ilustra um grafo co nexo Figura 18 Um grafo e suas duas compo nentes conexas Uma partição de um conjunto U é um conjunto de partes nãovazias e duas a duas disjuntas de U cuja união é igual a U Por exemplo 1 4 2 5 3 6 7 é uma partição do conjunto 7 κG Componentes conexas Um grafo G é conexo se para cada u v V existe um caminho que une u e v Uma componente conexa ou simplesmente componente de um grafo G é uma parte maximal14X V tal que o grafo GX é co nexo isto é é uma parte X V tal que GX é conexo e se Y V é tal que Y X e GY é conexo então Y X15 Observe que se X é uma componente de um grafo nãovazio G então X uma vez que Gv é obviamente conexo para cada vértice v de G É conveni ente muitas vezes confundir uma componente conexa X de um grafo G com o grafo GX Como de costume tal convenção será utilizada sempre que não houver possibilidade de confusão Lema 13 Seja G um grafo e X1 X2 V Se GX1 e GX2 são conexos e X1 X2 então GX1 X2 também é conexo Prova É suficiente mostrar que existe um caminho de x1 até x2 para cada x1 X1 e cada x2 X2 Sendo assim seja x1 X1 e x2 X2 Seja também x X1 X2 Como GX1 é conexo e x x1 estão em X1 então existe um caminho P1 de x1 até x De forma similar existe um caminho P2 de x até x2 Segue daí que P1 P2 é um caminho de x1 até x2 Concluímos assim que GX1 X2 é conexo Corolário 12 Se X1 e X2 são componentes conexas de um grafo G então X1 X2 ou X1 X2 Prova Suponha que X1 X2 Pelo Lema 13 GX1 X2 é conexo A maximalidade de X1 implica que X1 X1 X2 A maximalidade de X2 implica que X2 X1 X2 Logo X1 X2 Corolário 13 O conjunto das componentes conexas de um grafo não vazio G é uma partição de V O número de componentes conexas de um grafo nãovazio G é de notado por κG Todo vértice de um grafo pertence a uma e só uma componente conexa do grafo a componente conexa que contém um certo vértice x é chamada de território de x Exercício 16 Suponha que um grafo G tem exatamente dois vér tices digamos u e v de grau ímpar Mostre que existe um caminho em G que une os vértices u e v Solução Suponha que G é um grafo com exatamente dois vértices di gamos u e v de grau ímpar Como todo grafo tem um número par de vértices de grau ímpar então u e v estão numa mesma componente de G e portanto há um caminho de u até v em G NOÇÕES BÁSICAS 15 X 16 Note que Xc também é uma margem de K X X Xc Figura 19 As arestas de cor azul consti tuem um corte X As margens do corte são os conjuntos X e Xc É claro que X Xc Note que todo caminho de X até Xc usa uma aresta de X Proposição 11 Se G é um grafo conexo e e E então κG e 2 Prova Suponha que G é um grafo conexo e e xy é uma das arestas de G Seja X o território de x em Ge e Y o território de y em Ge Os grafos G eX e G eY são conexos Logo é suficiente mostrar que V X Y Suponha que v V Como G é conexo então existe um caminho simples P de v até x em G Se e EP então P é um caminho de v até x em G e donde v X Se e EP então e é a última aresta de P uma vez que P é simples Assim Pv y é um caminho de v até y em G e donde v Y Corolário 14 Se G é um grafo e e E então κG e κG 1 Corolário 15 Se G é um grafo nãovazio então κG G G Prova Vamos provar por indução em G que se G é nãovazio então κG G G Suponha que G é um grafo nãovazio Se G 0 então κG G e não há mais nada a provar Suponha G 1 Escolha uma aresta e E Por hipótese de indução κG e G e G e Segue daí que κG κG e 1 G e G e 1 G G 1 1 G G Corte de um conjunto de vértices Seja G um grafo e X V O conjunto das arestas que têm uma ponta em X e a outra em Xc é denotado por X É evidente que X Xc Uma parte K de E é um corte se K X para algum X V e neste caso X é uma16 margem de K Um corte é dito trivial se uma de suas margens é vazia Para cada X V a cardinalidade de X X é denotada por dGX ou como de hábito simplesmente dX Considere um grafo G e dois de seus vértices digamos s e t Dizemos que uma parte S de V é um stconjunto se s S e t Sc Suponha que 16 TEORIA DOS GRAFOS Figura 110 A remoção das arestas de cor azul desconecta o grafo No entanto tais arestas não constituem um corte 17 Tal notação é uma abreviatura para as afirmações v0v1v2 vk é um caminho e x v0 e y vk P v0e1v1 ekvk é um stcaminho de G Então v0 s e vk t Tome o maior i 0 k tal que vi S A escolha de i implica que vi1 Sc donde ei1 EP S e portanto EP S Proposição 12 Se P é um caminho que une dois vértices s e t de um grafo G e S é um stconjunto então EP X Corolário 16 Se X é uma componente de um grafo G então X Prova Suponha que X é uma componente de um grafo X e que e E é uma aresta com uma das pontas digamos x em X Seja y a outra ponta de e Então x y Y para algum componente conexo Y de G No entanto pelo Corolário 12 X Y donde e tem ambas as pontas em X Segue daí que X Teorema 12 Um grafo G é conexo se e só se X sempre que X V Prova Suponha que G é conexo e que X V Tome um vértice x X e um vértice y Xc Como G é conexo então existe um caminho 17 x v0e1v1 ekvk y tal que k 0 Tome o maior i 0 k tal que vi X De v0 X e vk Xc vem que 0 i k Ademais a maximalidade de i implica que vi1 Xc donde ei1 X e portanto X Suponha agora que X sempre que X V Seja X o território de x Pelo Lema 16 X donde X ou X V Ora x está em X e assim X V Logo existe um xycaminho em G e portanto G é conexo O próximo lema exibe uma condição suficiente que garante a cone xidade de um grafo Proposição 13 Se G é um grafo simples e γv G2 para cada v V então G é conexo Prova Suponha que G é um grafo simples e γv G2 para cada v V Suponha que X V Observe que X Xc Renomeie X se necessário de tal forma que X Xc Neste caso X G2 Tome x X Como γx G2 então x tem ao menos um vizinho em Xc donde X Portanto G é conexo NOÇÕES BÁSICAS 17 Para um grafo conexo G dizemos que um conjunto de arestas F E desconecta G se o grafo G F não é conexo Um conjunto minimal de arestas que desconecta G é uma parte F de E tal que F desconecta G e se F F então G F é conexo O próximo lema estabelece que um tal conjunto F nada mais é que um corte de G Note entretanto que a recíproca não é verdadeira ou seja não é verdade que todo corte é um conjunto minimal de arestas que desconecta G salvo se as margens do corte induzirem subgrafos conexos como mostra a próxima proposição Proposição 14 Seja G um grafo conexo Uma parte F de E é um conjunto minimal de arestas que desconecta G se e só se existe X V tal que X F e os grafos GX e GXc são ambos conexos Prova Suponha que F é um conjunto minimal de arestas que des conecta um grafo conexo G Seja X uma componente conexa de G F De GF não conexo vem que X V Vamos provar que F X Suponha que f é uma aresta em F Como X é uma componente de G F então GF X A minimalidade de F implica que o grafo H G F f é conexo donde HX o que combinado com GF X HX f implica que HX f Mas HX X Segue daí que f X e portanto F X Por outro lado GF X implica que X F Logo X F como queríamos Vamos provar a contrapositiva se X V é tal que GX ou GXc não é conexo então X não é um conjunto minimal de arestas que desconecta G Ajuste a notação de tal forma que H GX não é conexo Pelo Teorema 12 existe Y1 X tal que HY1 Ponha Y2 X Y1 Segue daí que não existe aresta de G com uma ponta em Y1 e a outra em Y2 o que por sua vez implica que X Y1 Y2 Por hipótese G é conexo donde Y1 e Y2 Logo Y1 X e Y2 X Segue daí que existem partes próprias de X que desconectam G Portanto X não é um conjunto minimal de arestas que desconecta G Exercício 17 Suponha que G é um grafo conexo e X é uma parte própria e nãovazia de V tal que GX e GXc são ambos conexos Mostre que se Z é uma parte própria e nãovazia de V tal que Z X então Z X ou Z Xc Solução Considere um tal Z Então ZX X ou ZXc Xc Suponha Z X X A conexidade de GX implica que GXZ X Mas GXZ X Z e GXZ XX Portanto Z X 18 TEORIA DOS GRAFOS 18 Isto quer dizer que não existe X V tal que X L X Xc Figura 111 A figura ilustra um grafo bi partido G com bipartição X Xc Note que toda aresta tem exatamente uma das pontas no conjunto X assim não há arestas com ambas as pontas em X ou com ambas as pontas em Xc Um corte K E em um grafo G é minimal se L não é um corte para cada L K 18 O próximo lema caracteriza quando um corte é minimal em um grafo conexo Corolário 17 Seja G um grafo conexo e X uma parte própria e não vazia de V Então X é um corte minimal se e só se GX e GXc são conexos Exercício 18 Seja G um grafo Mostre que se X é uma parte mini mal e nãovazia de V que é Γfechada então X é uma componente conexa de G Solução Primeiro note que se M e N são conjuntos Γfechados então M N também é Γfechado De fato suponha que x M N Então Γx M e Γ N donde Γx M N e portanto M N é Γ Tanto X quanto C são Γfechado e assim X C também é Γfechado A minimalidade de X implica que X X C donde X C Como X é Γfechado então X Ademais GC conexo implica que U para cada U C Isto combinado com X C e X acarreta X C como queriamos Grafos bipartidos Um grafo G é bipartido se existe X V tal que toda aresta tem uma ponta em X e a outra em Xc o par X Xc é chamado de bipartição de G e X e Xc são os lados da bipartição No entanto vamos abreviar e dizer simplesmente que X é uma bipartição de G uma vez que o outro participante da bipartição o conjunto Xc pode ficar subentendido Dizemos que um ciclo C em um grafo D é ímpar se o seu compri mento ℓC é ímpar O próximo teorema caracteriza grafos biparti dos Teorema 13 Um grafo G é bipartido se e só se G é livre de ciclos ímpares Prova Suponha que X é uma bipartição de G Note que se P é uma trilha que começa e termina num mesmo lado da bipartição então P tem comprimento par De fato suponha que P v0v1 vk é tal que v0 X vk X Então vi1 X vi Xc para cada i k o que implica que k é par Portanto se G tem um ciclo então tal ciclo tem comprimento par NOÇÕES BÁSICAS 19 C Xc C X Cc X Cc Xc C e Figura 112 Toda aresta exceto e tem uma ponta em X e a outra em Xc As sim Y C X Cc Xc é uma bipartição de G Vamos mostrar por indução em G que se G é um grafo livre de ciclos ímpares então G é bipartido O grafo vazio é bipartido Suponha então que G é um grafo livre de ciclos ímpares e que G 1 Seja e xy uma aresta de G e considere o grafo H G e É claro que H é livre de ciclos ímpares e H G Assim por hipótese de indução H é bipartido Seja X uma biparti ção de H e suponha que x X Se y Xc então X é uma bipartição de G e não há mais nada a provar Suponha então que y X Note que todo caminho simples cuja origem e destino está num mesmo lado da bipartição tem comprimento par Isso aliado a e E implica que não existe um caminho de x até y em G Seja C a componente de G e que contém x Então y Cc Considere o conjunto Y C XCc Xc Então Y c C XcCcX Vamos mostrar que Y é uma bipartição de G Note primeiro que a ponta x de e está em C X e a ponta y de e está Cc X donde x Y e y Y c Suponha que f E e Temos dois casos Suponha primeiro que f é uma aresta de GC Como X é uma bipartição de G então f tem uma de suas pontas digamos u em X e a outra digamos v em Xc Mas u v C donde u C X e v C Xc e portanto u Y e v Y c Suponha que f é uma aresta de GCc Como X é bipartição de G então f tem uma de suas pontas digamos u em Xc e a outra digamos v em X Mas u v Cc donde u Cc Xc e v Cc X e portanto u Y e v Y c Logo Y é uma bipartição de G Vamos exibir uma prova alternativa da recíproca Suponha então que G é um grafo nãovazio livre de ciclos ímpares Podemos supor que G é conexo uma vez que o argumento que segue pode ser aplicado a cada uma das componentes de G quando G é desconexo Seja s V e dists x minℓP P é um sxcaminho em G para cada x V e X x V dists x é par Vamos mostrar que X é uma bipartição de G Para isso é suficiente mostrar que não há arestas com ambas as pontas em X ou ambas as pontas em Xc Suponha que x1 x2 são vértices de G tais que x1 x2 X ou x1 x2 Xc Vamos mostrar que G não possui uma aresta com pontas x1 e x2 Seja Pi um sxicaminho simples de comprimento mí nimo de s até xi para i 1 2 Escreva P1 s v0v1v2 vk x1 Seja i 0 1 k o maior índice tal que vi P2 A escolha de i implica P1vi x1 P2vi x2 vi A minimalidade de P1 im plica que ℓP1s viℓP1vi x1 ℓP2s viℓP1vi x1 donde 20 TEORIA DOS GRAFOS X G GX s1 s2 s3 s4 s5 t1 t2 t3 t4 t5 t6 s1 X s5 t1 t2 t3 t4 t5 t6 Figura 113 A figura ilustra um grafo G e o grafo obtido de G através da con tração de uma parte nãovazia X de V Note que as arestas de GX são aquelas cujas pontas estão ambas em Xc junta mente com aquelas que têm exatamente uma ponta em X e a outra em Xc Desta forma arestas com ambas as pontas em X não estão presentes no grafo GX ℓP1s vi ℓP2s vi De forma similar a minimalidade de P2 im plica que ℓP2s vi ℓP1s vi Assim ℓP1s vi ℓP2s vi Ora como ℓP1 e ℓP2 têm a mesma paridade então as paridades de ℓP1vi x1 e ℓP2vi x2 também são iguais Isto combinado com a ausência de ciclos ímpares em G implica que não há aresta em G com pontas x1 e x2 Contração de um conjunto de vértices Seja G um grafo e X V Daqui para frente vamos sempre admitir que X V O grafo obtido de G pela contração de X denotado por GX é o grafo cujo conjunto dos vértices é Xc X cujo conjunto das arestas é EGX E e E ιe X e cuja função de incidência ιGX é tal que ιGXe ιe se ιe Xc e X y se ιe xy com x X e y Xc para cada e EGX Vamos retomar o Teorema 13 e provar mais uma vez que grafos li vres de ciclos ímpares são bipartidos Desta vez vamos usar a noção de contração de um conjunto de vértices recém definida A prova é tam bém por indução no número de arestas Suponha que G é um grafo livre de ciclos ímpares Suponha ademais que G 0 Seja x um vértice incidente em alguma aresta de G e X x Γx Considere o grafo H GX Observe que H é livre de ciclos ímpares se C é um ciclo de H então ou C é um ciclo de G e em tal caso é par ou então um dos vértices de C é X Neste último caso considere as ares tas e1 e2 que incidem em X no grafo H As pontas de tais arestas em G são elementos digamos x1 x2 de Γx tais que x1 x2 Assim C é um caminho simples de G Segue daí que C e1 e2 é um ciclo de G e consequentemente tem comprimento par donde C tem também comprimento par Logo por hipótese de indução H é bipartido Seja Z a bipartição de H que contém X Fica como exercício para o leitor verificar que Z X Γx é uma bipartição de G Proposição 15 Para todo grafo G existe subgrafo bipartido e gerador H tal que H G Prova Para cada X V seja EX o conjunto das arestas de G que têm uma ponta em X e a outra em Xc e HX o subgrafo de G cujo conjunto dos vértices é V e cujo conjunto das arestas é EX Assim HX é um subgrafo bipartido e gerador de G Escolha X V tal que EX é máximo Afirmações como dHX v dv2 para cada v V Suponha que x V Ajuste a notação do forma que x X Seja Y X x Note que EY EX HXx HYx A escolha de X implica que EX EY Segue daí que EX EX HXx HYx onde dHXx HYx dHYx Mas e portanto dHX dHX dHY Teorema 14 Mantel Se G é um grafo simples livre de triângulos então G G²4 Primeira prova A prova depende do seguinte lema Lema 14 Para todo natural n maxknk k 0 n n²4 Prova O resultado é óbvio se n 1 Assim vamos supor que n 2 É evidente que existe a 0 n tal que ana maxknk k 0 n É fácil ver que n 2 implica 0 a n Note que a1nna anna²12a ana² 2a n1 onde a n 1 2 e Lema 11 implica que 2E v V dHX v G NOÇÕES BÁSICAS 23 20 Considere o conjunto C cujos elemen tos são os grafos simples G tais que G G 4 e G não possui dois ciclos disjuntos nas arestas Queremos mostrar que C Para isso vamos admitir que C Considere o conjunto Z G G G C Como C é nãovazio então Z é um conjunto nãovazio de in teiros nãonegativos e portanto possui um menor elemento digamos m Seja então G C tal que G G m Este é o tal contraexemplo minimal Ob serve que se H é um grafo simples tal que H H m então H C donde H possui dois ciclos disjuntos nas arestas 21 Lembrese que a cintura de um grafo que contém ciclos é o comprimento de um menor ciclo Caso 1 G G24 Por hipótese de indução G tem um triangulo e tal triângulo é tam bém um triângulo de G pois G é subgrafo de G Caso 2 G G24 Seja n G Note que G G n2 4 n 22 4 n 1 Então existem pelo menos n 1 arestas com uma das pontas em x y e a outra em V x y Mas V x y n 2 donde pelo Princípio da Casa de Pombos existe z V x y tal que z Γx Γy Portanto Gx y z é um triângulo Lema 15 Se G é um grafo simples e G G então G possui ciclo Prova Vamos provar por indução em G que se G G então G possui um ciclo Seja então G um grafo tal que G G Se δG 2 então pelo Lema 12 G possui um ciclo Assim suponha que δG 2 Seja x um vértice de G com dx 1 e considere o grafo H G x Então H G 1 G 1 H Sendo assim por hipótese de indução H possui um ciclo C Como H é um subgrafo de G segue que C também é um ciclo de G Isto finaliza a prova do lema Proposição 16 Se G é um grafo simples e G G 4 então G possui dois ciclos disjuntos nas arestas Prova A prova é por contradição Seja G um contraexemplo para o lema com G G mínimo20 Observe primeiro que G 5 11 uma vez que nenhum grafo com menos de 5 vértices satisfaz a hipótese da proposição Afirmamos que G G 4 12 Suponha que G G 4 Seja e uma aresta de G e H o grafo G e Então H H 4 O grafo H não pode ser um contraexemplo pois H H G G Assim H satisfaz o lema ou seja H possui dois ciclos disjuntos nas arestas Mas H é um subgrafo de G donde tais ciclos também são ciclos de G Esta contradição prova 12 24 TEORIA DOS GRAFOS x y z y z Figura 116 A figura ilustra a operação envolvida na construção de H quando dx 2 Agora mostraremos21 que a cintura de G é pelo menos 5 13 Suponha que G possua um ciclo C tal que C 4 Considere o grafo H G EC Temos que H G 4 G H Logo pelo Lema 15 H possui um ciclo C Portanto C e C são ciclos disjuntos nas arestas de G Esta contradição prova 13 Temos também que δG 3 14 Suponha que δG 2 Seja x um vértice de G com dx 2 Suponha inicialmente que dx 1 O grafo H G x é tal que H G 1 G 4 1 H 4 Logo H satisfaz as condições do lema Como H tem menos vértices que G segue que H possui dois ciclos digamos C e C disjuntos nas arestas No entanto H é um subgrafo de G donde C e C são ciclos de G uma contradição Suponha agora que dx 2 Denote por y e z os vizinhos de x Note que em virtude de 13 yz não é uma aresta de G O grafo H G x yz é tal que H G 1 G 4 1 H 4 Assim H satisfaz a hipótese do lema e H é menor que G Vem daí que H possui ciclos C C disjuntos nas arestas Se tanto C quanto C não incluem a aresta yz então C e C também são ciclos disjuntos de G o que é uma contradição Suponha pois que um dos ciclos digamos C inclua yz Então tro que na sequência que determina C o segmento yz pelo segmento yxz e seja C o ciclo assim obtido Com isto temos que C e C são ciclos disjuntos nas arestas de G Novamente uma contradição Isto completa a prova de 14 Afirmamos que G 8 15 De fato Suponha que G 9 Como G G 4 vem que dG 2G G 2G 4 G 2 8 G Agora G 9 implica dG 3 donde δG 2 No entanto isto contraria 14 Isto prova 15 Para completar a prova do lema basta mostrar que não existe ne nhum grafo G satisfazendo simultaneamente as seguintes proprieda des G G 4 cintura de pelo menos 5 δG 3 e 5 G 8 A prova disto é deixada para o leitor Exercício 19 Mostre que se G é um grafo simples e G possui k componentes conexas então G G k 1 2 Figura 21 A figura ilustra uma árvore 1 Isto é arestas distintas que possuem as mesmas pontas 2 Árvores Um grafo é dito acíclico ou uma floresta se não possui ciclos Não é difícil ver que se um grafo G é acíclico então existe no máximo um ca minhos simples unindo dois vértices arbitrários de G De fato suponha que existem dois caminho simples distintos unindo um par de vértices de G Vamos mostrar que G possui um ciclo Seja x y um par de vérti ces de G para o qual i existem dois caminhos simples distintos diga mos P1 e P2 de x até y e ii ℓP1 ℓP2 é mínimo Podemos supor que P1 e P2 não possuem arestas paralelas1 Escreva P1 v0v1 vk com k 1 A escolha de P1 e P2 implica que v1 P2 Seja i o menor inteiro em 1 k tal que vi P2 Então P1v0 vi P 1 2 vi v0 é um ciclo como queríamos Logo se um grafo G é acíclico então existe no máximo um caminho um caminho simples unindo cada par de vértices de G Os grafos conexos e acíclicos têm um papel fundamental na Teoria dos Grafos e por isso recebem um nome especial árvores Em virtude da discussão acima em uma árvore existe exatamente um caminho sim ples unindo cada par de vértices A recíproca ou seja que em um grafo no qual cada par de vértices é unido por exatamente um caminho sim ples é uma árvore também é verdadeira o fato de existir um caminho entre cada par de vértices implica que o grafo é conexo o fato de exis tir exatamente um implica que o grafo é acíclico Portanto o grafo é uma árvore As verificações formais desses fatos são bem simples e por isso são deixadas para o leitor Vamos entretanto destacar este último resultado Teorema 21 Um grafo é uma árvore se e só se cada par de vértices é unido por exatamente um único caminho simples Corolário 21 Se T é uma árvore e e ET então cT e 2 Prova Suponha que T é uma árvore e e xy ET Ora xey é um caminho simples de x até y em T e portanto é único Segue daí que 28 TEORIA DOS GRAFOS 2 Justifique T e não contém nenhum caminho de x até y donde cT e 2 No entanto a Proposição 11 implica que cT 2 2 e portanto cT e 2 Exercício 21 Mostre que se G é nãovazio e G é uma floresta então κG G G Solução Vamos mostrar por indução em G que se G é uma floresta então κG G G Seja G uma floresta Se G 0 então κG G donde κG G G Suponha então que G 1 Seja e uma aresta de G e seja H G e É claro que H é uma floresta Por hipótese de indução κH H H O corolário anterior implica que κH κG 1 Logo κG κH 1 H H 1 G G 1 1 G G como queríamos O seguinte exercício será útil para o próximo teorema Exercício 22 Se C é um ciclo e K é um corte de um grafo G então EC K mod 2 0 Solução Seja X V Vamos provar por indução em ℓC que se C é um x1x2caminho tal que x1 x2 X então EC X mod 2 0 Seja C um x1x2caminho tal que x1 x2 X Se VC Xc então EC X 0 Suponha então que VC Xc Seja y VC Xc tal que ℓCx1 y é mínimo Seja x3 VC X tal que ℓCy x3 é mínimo Como ℓCx3 x2 ℓC então por hipótese de indução ECx3x2 X mod 2 0 Mas EP x1x3 X 2 e portanto EC X mod 2 0 Finalmente como K é um corte então existe X V tal que X K Segue daí que se C é um ciclo então EC K mod 2 0 Teorema 22 Um grafo conexo T é uma árvore se e só se T e não é conexo para cada e ET Prova Suponha que T é uma árvore e e ET O Corolário 21 implica que T e não é conexo Suponha agora que T é um grafo conexo para o qual T e não é conexo para cada e ET Vamos provar por indução em T que T é uma árvore Se T 1 o resultado segue por vacuidade Suponha então que T 2 Como T é conexo então ET Tome assim uma aresta e ET e considere o grafo T e Ora a conexidade de T e a Teorema 23 Um grafo T é uma árvore nãovazia se e só se T é conexo e T T 1 Exercício 23 Primeiro você vai provar que se T é uma árvore e T 2 então T possui uma folha Sugestão escolha um caminho simples de comprimento máximo de T e observe suas pontas Agora você pode tentar provar o Teorema 23 Sugestão faça uma prova por indução em T no qual o passo da indução consiste em remover uma folha de T Exercício 24 Prove que um grafo nãovazio T é uma árvore se e só se T E 1 Solução Se T é uma árvore então por definição T é acíclico Além disso T V 1 Suponha que T é acíclico e T V 1 Sejam C₁ Cₖ as componentes conexas de T Vamos mostrar que k 1 Seja i k Ora TCᵢ TCₖ 1 Segue daí que T ᵢk TCᵢ ᵢk TCᵢ 1 T k e portanto k 1 32 TEORIA DOS GRAFOS as pontas de e digamos x e y estão em Ci para algum i donde x e y são comparáveis em Ti ti e assim x e y também são comparáveis em T r ou ii uma das pontas de e é r e neste caso evidentemente r e s são comparáveis em T r onde s é a outra ponta de e Portanto T é uma árvore de busca em profundidade de G com raiz r Transversal de um conjunto Vamos definir a noção de transversal de um conjunto Este será o primeiro contato com esta noção que terá um pa pel fundamental nos capítulos futuros Suponha que U é um conjunto e que X 2U Dizemos que T U é uma transversal de X se T X para cada X X Uma transversal T de X é dita minimal se U não é transversal de X para cada U T Exemplo 1 Considere o conjunto U 1 2 3 4 e X 1 2 1 3 2 3 4 2U Os conjuntos 1 2 e 1 4 são exemplos de transversais minimais de X Note que qualquer superconjunto de uma transversal é tam bém uma transversal Observe que o Teorema 12 implica que o conjunto das arestas de grafo conexo G é uma transversal do conjunto X X V Suponha que T é uma árvore geradora de um grafo G Se X V então a conexidade de T implica que ET X Portanto as arestas de uma árvore geradora de G constituem uma transversal do conjunto X X V Exercício 25 Seja G um grafo conexo e x y vértices de G Mostre que se P é um caminho de G que une x e y então as arestas de P são uma transversal do conjunto X X V x X y Xc Note no enunciado do próximo teorema a identificação de um con junto de arestas com o grafo induzido por este conjunto de arestas Teorema 26 Seja G um grafo conexo e C X X V Uma parte T de E é uma árvore geradora de G se e só se T é uma transversal minimal de C Prova Suponha que T é uma árvore geradora de G e que e T Então pelo Teorema 22 T e não é conexo donde existe X V tal que T e X Assim T é uma transversal minimal de C ÁRVORES 33 Suponha que T é uma transversal minimal de C O resultado é claro se G 1 Logo vamos supor que G 2 Vamos mostrar que T é um subgrafo conexo e gerador de G Para isso tome X V Como T é uma transversal de C então T X mas T X T X donde pelo Teorema 12 T é conexo Além disso T é gerador De fato T VT donde VT ou VT V É claro que VT Assim VT V e consequentemente T é gerador Concluímos assim que T é um subgrafo gerador e conexo de G Seja e uma aresta de T Como T é uma transversal minimal de C então T e não é uma transversal Logo existe X V tal que T eX T e X donde T e não é conexo Concluímos assim que T é conexo e T e não é conexo para cada e T o que de acordo com o Teorema 22 implica que T é uma árvore Exercício 26 Seja G um grafo conexo e x y vértices de G Mostre que o conjunto das arestas de um caminho P de G que une x e y é uma transversal minimal de C X X V x X y Xc se e só se P é simples Exercício 27 Seja T uma árvore Uma sacola de subárvores de T é uma coleção C 2V T tal que C e TC é uma subárvore de T para cada C C ou seja uma sacola de subárvores de T é uma co leção cada um de cujos elementos é o conjunto dos vértices de su bárvores nãovazias de T Exiba um algoritmo que encontra uma transversal de tamanho mínimo de uma sacola de subárvores de uma árvore T Solução A solução segue na próxima seção Transversal de uma sacola de subárvores Seja T uma árvore Uma sacola de subárvores de T é uma coleção C 2V T tal que C e TC é uma subárvore de T Teorema 27 Se T é uma árvore e C é uma sacola de subgrafos de T então minX X TE maxD D é uma parte disjunta de C onde E denota o conjunto das transversais de C Prova Suponha que X TE e D é uma parte disjunta de C Então X X UD U D DD X D DD 1 D onde minX X TE maxD D é uma parte disjunta de C Corolário 22 Se T é uma árvore e e é uma sacola nãovazia de subárvores de T tal que C1 C2 0 para cada C1 C2 E então E Proposição 21 Suponha que T é uma árvore geradora de um grafo G e e T é E T São equivalentes i e T está no ciclo fundamental de G em relação a T f ii e T não está no corte fundamental de G em relação a T e e iii T e f é uma árvore geradora de G ÁRVORES 37 Árvore geradora de custo mínimo O problema da árvore geradora de custo mínimo consiste em dado um grafo ponderado e conexo G c encontrar uma árvore geradora T de G tal que cT é mínimo Uma tal árvore é chamada de árvore geradora de custo mínimo de G A condição do ciclo Suponha que T é uma árvore geradora de custo mínimo de um grafo ponderado G c e que e é uma aresta de G fora de T Considere uma aresta f no ciclo fundamental de G em relação a T e A propriedade da troca garante que T f e é uma árvore geradora de G Ade mais a minimalidade do custo de T implica que cT cTfe e portanto cf ce O Teorema a seguir mostra que essa condição é também suficiente Teorema 29 Uma árvore geradora T de um grafo ponderado G c é de custo mínimo se e só se cf ce para cada e xy E T e cada f ETx y Prova Suponha que T é uma árvore geradora de custo mínimo de um grafo G Suponha que e xy E T e f ETx y Pela Proposi ção 21 T f e é uma árvore geradora de G Todavia T tem custo mínimo donde cT cT f e cT cf ce e portanto cf ce Suponha agora que T é uma árvore geradora de um grafo G tal que cf ce para cada e xy E T e cada f ETx y Vamos mostrar por indução em T T que se T é uma árvore geradora de custo mínimo de G então cT cT Seja T uma árvore geradora de custo mínimo de G Se T T então T T e não há mais nada para provar Suponha que T T Seja e xy T T Considere o corte fundamental K de G em relação a T e Então Tx y contém pelo menos uma aresta digamos f em K Pela Proposição 21 T T ef é uma árvore geradora de G Por hipótese cf ce donde cT cT Logo T é uma árvore geradora de custo mínimo de G Como T T T T 1 então por hipótese de indução cT cT donde cT cT como queríamos A condição do corte Suponha agora que T é uma árvore geradora de custo mínimo de um grafo ponderado G c e que e é uma aresta de T Considere uma aresta f no corte fundamental de G em relação a T e A propriedade da troca garante que T e f é uma árvore geradora de G A minimalidade do custo de T implica que cT cT e f e portanto ce cf O Teorema a seguir estabelece que essa condição é também suficiente 38 TEORIA DOS GRAFOS Teorema 210 Uma árvore geradora T de um grafo G é de custo mí nimo se e só se ce cf para cada e T e cada aresta f no corte fundamental de G em relação a T e Prova Suponha que T é uma árvore geradora de um grafo G tal que ce cf para cada e T e cada aresta f no corte fundamental de G em relação a T e Vamos mostrar por indução em T T que se T é uma árvore geradora de custo mínimo de G então cT cT Se T T então T T e portanto cT cT Suponha então que T T Seja e xy T T Então T x y contém pelo menos uma aresta digamos f no corte fundamental de G em relação a T e Por hipótese ce cf Assim pela Proposição 21 T T f e é uma árvore geradora de G Ademais cT cT donde T é de custo mínimo Como T T T T 1 então por hipótese de indução cT cT e portanto cT cT como queríamos Algoritmos Há diversos algoritmos gulosos para resolver o problema da árvore geradora de custo mínimo O cerne da correção destes métodos reside nos fatos que seguem Proposição 22 Se T é uma árvore geradora de um grafo ponderado G c e e é uma aresta de custo mínimo em um corte K de G então existe uma aresta f em K T tal que T f e é uma árvore geradora de G e cT f e cT Prova Se e T então tome f e e não há nada a provar Suponha que e T Sejam x e y as pontas de e Ora K ETx y Selecione uma aresta f K ETx y Como f está no ciclo fundamental de G em relação a T e então T f e é uma árvore geradora de G A escolha de e implica que ce cf donde cT f e cT Dizemos que uma floresta F de um grafo ponderado G c é boa se existe uma árvore geradora T de custo mínimo de G tal que F T Teorema 211 Se F é uma floresta boa de um grafo ponderado G c e e é uma aresta de custo mínimo em um corte K de G tal que K F então F e também é uma floresta boa de G c Prova Suponha que F é uma floresta boa de G c e e é uma aresta de custo mínimo em um corte K de G tal que KF Seja T uma árvore geradora de custo mínimo de G tal que F T Pela Proposição 22 Algoritmo de Prim O leitor atento notará que a proposição acima sugere um algoritmo para produzir uma árvore geradora de custo mínimo em um grafo ponderado e conexo G c O algoritmo de Prim é uma instância desse algoritmo no qual a cada iteração F é uma árvore de G 40 TEORIA DOS GRAFOS class WEdge def initself cost one other selfcost cost selfone one selfother other def iotaself return selfone selfother def costself return selfcost def ltself edge return selfcost edgecost def reprself return fselfcostselfoneselfother Assim para construir uma aresta com pontas x e y e custo c escre vemos WEdgec x y Se e WEdge e então ecost é o custo de e eone é uma das pontas de e e eother é a outra ponta de e Como é de se esperar eiota é um par cujo primeiro componente é eone e cujo segundo componente é eother Finalmente o método lt estabelece como comparar duas arestas Assm se e f WEdge então e f se ecost fcost A próxima classe captura a noção de um grafo ponderado class WGraph def initself V E selfV setV selfE tupleWEdgec x y for c x y in E selfG x for x in V for e in selfE selfGeoneappende selfGeotherappende def getitemself v return selfGv def lenself return lenselfG Para construir um grafo ponderafo escrevemos WGraphV E onde V é uma sequência que contém os vértices do grafo ponderado e E é uma sequência de triplas da forma c x y onde c é o custo de uma aresta cujas pontas são x e y Note que x e y devem ser elementos ÁRVORES 41 11 Um invariante é uma propriedade que vale no início de cada iteração de um laço imediatamente antes da condição que estabelece se haverá ou não uma nova iteração 12 A função de incidência é a restrição da função de incidência de G aos elementos de F 13 O algoritmo de Kruskal está intima mente relacionado com o algoritmo gu loso que constrói uma base de custo mí nimo em um objeto combinatório cha mado de matróide 14 Note que de G quer dizer que F além de ser uma floresta é um subgrafo de G de V O método getitem tem como propósito definir o operador Para cada vértice x em V Gx é uma sequência cada um de cujos elementos é uma WEdge os elementos de tal sequência são as arestas do corte de x Ademais se GWGraph então lenG é o número de vértices de G Eis finalmente a implementação do algoritmo de Prim def primdijstraG s X F K s for e in Gs heappushK e while lenF lenG 1 e heappopK if eone and eother in X continue y eone if eone not in X else eother Fappende Xaddy for a in Gy heappushK a return F São invariantes11 do laço do algoritmo acima i o grafo12 X F é uma árvore de G ii F é boa iii K contém o corte de X e iv se e está em K então uma das pontas de e está em X Exercício 28 Mostre que o número de iterações do algoritmo de Prim quando submetido a um grafo ponderado e conexo G c é no máximo 2G Exercício 29 Um conector de um grafo conexo G é um subgrafo conexo de G Observe que uma árvore geradora de G é um co nector mas nem todo conector é uma árvore geradora de G Con sidere o problema do conector de custo mínimo dado um grafo ponderado e conexo G c determinar um conector de G de custo mínimo onde como de costume o custo de um conector é a soma dos custos das arestas do conector Algoritmo de Kruskal Vimos que a ideia central do algoritmo de Prim consiste em estender uma árvore boa O algoritmo de Kruskal por outro lado consiste em estender uma floresta boa Na verdade é possível como vamos fazer mostrar que o algoritmo de Kruskal13 estende um floresta com uma propriedade mais forte que vamos chamar de extrema Floresta extrema Dizemos que uma floresta F de14 um grafo ponde rado G c é extrema se cF cF para cada florestas F tal que F F Considerar um conjunto finito e nãovazio V de elementos chamados documentos Suponha que a cada par u v de elementos de V está associado um número real nãonegativo du v denominado de dissimilaridade entre u e v tal que i du v 0 para cada u v V ii du v 0 para cada u v V e iii du v dv u para cada u v V Queremos agrupar os elementos de V em um certo número inteiro k tal que 1 k V de conjuntos nãovazios dois a dois disjuntos cuja união é V de forma que documentos semelhantes são depositados em um mesmo conjunto e documentos dissimilares são depositados em conjuntos distintos Vamos atribuir um valor chamado de medida a cada uma das partições de V com k elementos Suponha que é uma partição de V com k elementos A medida de é a menor dissimilaridade entre documentos que residem em conjuntos distintos de O problema do agrupamento ótimos de documentos consiste em encontrar uma partição de V cuja medida seja máxima Se F é uma floresta extrema de um grafo ponderado G c e e é uma aresta unindo diferentes componentes conexas de V F então ce cF para cada f F Se F é uma floresta extrema de um grafo ponderado G c e e é uma aresta unindo componentes conexas de V F e uma kV Fpartição ótima de V Segue daí que cT sume in ET cuw sumu in V sumv in Z chi2uchi2v sumZ in mathcalC sume in Ew in ET chi2uchi2v sumZ in mathcalC TZ sumZ in mathcalC Z kappaTZ