Teoria dos Grafos: Estruturas e Conceitos Fundamentais

Mario Leston Teoria dos Grafos Sumário 1 Noções básicas 5 2 Árvores 27 3 Caminhos mínimos com custos nãonegativos 47 4 Caminhos mínimos com custos arbitrários 63 5 Emparelhamentos em Grafos Bipartidos 69 6 Caminhos Disjuntos 81 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ãoordenado 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 Os dois próximos fatos costumam ser os primeiros destacados em introduções à Teoria dos Grafos Vamos então manter a tradição No entanto vamos aproveitar a oportunidade para introduzir uma notação que será útil Seja U um conjunto universo e X uma parte de U ou seja X U A função característica de X em relação a U é a função χX U U 0 1 tal que χX U u 1 se u X 0 se u X para cada u U Observe que X uU χX U u O gosto pela brevidade nos faz escrever χX Exercício 11 Mostre que se G é um grafo e G G 1 então existe v V tal que dv 3 Solução Vamos equivalentemente provar que se dv 2 para cada vértice v de um grafo G então G G Seja G um grafo e suponha que dv 2 para cada v V Então 2G vV dv vV 2 2G 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 e dHv dv para cada v V x y Então Exercício 12 Prove o Corolário 11 por indução no número de arestas 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 Ademais para cada inteiro k 0 e cada x y V Pkx y z V P Pk1x z e z y 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 Ak1Gz y Akcx 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 Para cada X V seja EX o conjunto das arestas de G que têm uma ponta em X e a outra em Xᶜ 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 E é máximo Afirmamos que dHx dv2 para cada v V Suponha que x V Ajuste a notação do fato 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 EY HXx HYx onde dHx HYx dHYx Mas e portanto dHx dHXx dHYx 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 a1na1 ana anna²12a ana² 2a n1 onde a n 12 n2 Além disso a 1na 1 ana 2a n1 onde a n12 n12 n²4 Logo a n2 ou a n12 Finalmente como queríamos 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 conexos 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 as 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 Solução Suponha que T é uma árvore e T 2 Seja P um caminho simples e maximal de T Seja x a ponta inicial de P A maximalidade de P implica que Γx V Isto combinado com a hipótese de T ser uma árvore implica que dx 1 Logo x é uma folha de T Vamos agora provar por indução em T que se T é uma árvore nãovazia então T T 1 Seja T uma árvore nãovazia O resultado é imediato se T 1 Suponha então que T 2 Seja x uma folha de T e considere o grafo J T x Como dx 1 então J é uma árvore Por hipótese de indução J T 1 Segue daí que T J 1 T 1 1 J 1 1 como queríamos Exercise 24 Prove que um grafo nãovazio T é uma árvore se e só se T T 1 Solução Se T é uma árvore então por definição T é acíclico Além disso T T 1 Suponha que T é acíclico e T T 1 Sejam C1 Ck as componentes conexas de T Vamos mostrar que k 1 Seja i k Ora TCi TCi 1 Segue daí que T 1 ik TCi ik TCi 1 T k e portanto k 1 Árvores geradoras Lembrese que um subgrafo H de um grafo G é dito gerador se VH VG Dizemos que um grafo T é uma árvore geradora de um grafo G se T é uma árvore e T é um subgrafo gerador de G Observe que se T é uma árvore geradora de G então a conectividade T implica na conectividade de G Não é difícil intuir que todo grafo conexo possui uma árvore geradora Teorema 24 Um grafo G possui uma árvore geradora se e só se G é conexo Prova A discussão precedente mostra que se G possui uma árvore geradora então G é conexo Vamos então provar a recíproca Suponha que G é conexo Admita que X V e tal que GX possui uma árvore geradora Um tal X evidentemente existe uma vez que Gv é uma árvore para cada v V Suponha ademais que X V Seja T uma árvore geradora de GX Como G é conexo então X Seja e X V e considere o subgrafo U GEΓT e Seja a ponta de e em X e y a ponta de e em Xe Vamos mostrar que U é uma árvore geradora de GX y Ora U é um grafo conexo Para verificar isso basta provar que existe um caminho em U que une t e y para cada t VTr Por hipótese existe um caminho P que une t e x em T e todo P xey é um caminho de e até y em U Logo U é conexo Além disso U é acíclico uma vez que T é acíclico e dy 1 Portanto U é uma árvore geradora de GX y Assim se X é uma parte maximal de V tal que GX possui uma árvore geradora então X V como queríamos 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 de busca em profundidade Seja T uma árvore nãovazia e r um de seus vértices Como de costume para simplificar vamos confundir uma árvore com o seu conjunto de arestas Vamos mostrar que T possui uma árvore de busca em profundidade a partir de r Para cada x y VTr dizemos que x e y são comparáveis em T r se x VTr y ou seja se x está no caminho de r até y em T Seja T uma árvore geradora de um grafo G V E Dizemos que T é uma árvore de busca em profundidade com raiz r se x e y são comparáveis em T r sem que e E T Teorema 25 Se G é um grafo conexo e r V então G possui uma árvore de busca em profundidade com raiz r Prova A prova é por indução em G Suponha que C é um grafo conexo e r V Se G 1 então G é uma árvore de busca em profundidade com raiz r Suponha então que G 2 Sejam C1 Ck com k 1 as componentes conexas de G r Para cada i k seja t um vizinho de r em Ci e uma aresta com pontas r e ti Por hipótese de indução existe uma árvore de busca em profundidade Ti de GC com raiz ti para cada i k É claro que T ei i k ik Ti é uma árvore de busca em profundidade Note que não há arestas cujas pontas estão em diferentes componentes de G r Seja e E T Então i ou ambas Á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 se y C1 C2 para algum C1 C2 ℐ então C1 y ℬ Corolário 22 Se T é uma árvore e ℐ é uma sacola nãovazia de subárvores de T tal que C1 C2 para cada C1 C2 ℐ então E Á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 def primG x F X x while F G 1 e argmincf f X F F e X X Ue return F Á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 gerador e conexo de G Observe que uma árvore geradora de G é um conector mas nem todo conector é uma árvore geradora de G Considere 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 6 cF para cada florestas F tal que F F Considerar um conjunto fino 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 desigualdade entre u e v tal que i du v 0 para cada u V ii du v 0 para cada u v V e 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 6 k 6 V de conjuntos nãovazios dois a dois distintos cuja união é V de forma que documentos similares sejam depositados em um mesmo conjunto e documentos dissimilares sejam depositados em conjuntos distintos Vamos atribuir um valor chamado de medida a cada uma das partitions de V com k elementos Suponha que P é uma partição de V com k elementos A medida de P é a menor dissimilaridade entre documentos que residem em conjuntos distintos de P O problema do agrupamento ótimo de documentos consiste em encontrar uma partição de V cuja medida seja máxima Note que X para cada X P De fato suponha que X P Então X Como k 2 então X Finalmente a conectividade de G implica que X Logo mP está bem definido O problema do agrupamento ótimo consiste em encontrar uma kpartição de V cuja medida seja máxima Os dois próximos resultados estabelecem que as componentes conexas de uma floresta extrema com k componentes é uma solução Segue daí que cT sume in ET cuw sumu in mathcalZ sumv in mathcalZ chi2u chi2v sume in E sumu in ET chi2u chi2v sumZ in mathcalZ TZ sumZ in mathcalZ Z kappaTZ Teorema 215 Seja mathcalH um hipergrafo e Gc o grafo ponderado associado a mathcalH Então mathcalH é árvore se e só se toda árvore geradora de custo máximo de Gc é básica a a 1 Esta notação será utilizada quando não houver possibilidade de confusão Tipi camente este será o caso quando houver somente um digrafo no contexto da dis cussão Assim U é o conjunto dos ar cos cuja ponta inicial está em U e cuja ponta final está fora de U 3 Caminhos mínimos com custos nãonegativos Vamos recapitular algumas definições Um digrafo D é uma tripla V A ι em que V é um conjunto finito de vértices A é um conjunto finito de arcos V A e ι A V V v v v V é a função de incidência de D Assim ιa é um par ordenado digamos u v ou mais brevemente uv de vértices com u v Os vértices u e v são as pontas de a u é a ponta inicial de a e v é a ponta final de a A ponta inicial de a é também denotada por a e a ponta final é denotada por a Por brevidade escrevemos a uv em vez de ιa uv Para cada k 0 dizemos que uma sequência P u0 a1 u1 ak uk é um u0ukcaminho orientado ou um caminho orientado de u0 até uk se i VP u0 u1 uk V ii AP a1 ak A e iii ai ui1ui para cada i 1 k O comprimento de P denotado ℓP é o número k Dizemos que P é simples se ℓP VP 1 ou seja P não repete vértices e evidente mente também não repete arcos Para cada i j 0 k a sequência ui ai1 aj1 uj denotada por Pui uj é um uiujcaminho ori entado Se P u0e1 ekvk é um stcaminho ou seja s u0 e t uk e Q w0f1 ejwj é um tucaminho então a concatenação de P e Q denotada P Q é o sucaminho orientado u0e1 ekvkf1 ejwj Corte de saída e de entrada Lembrese que para cada subconjunto U de vértices de um digrafo D o corte de saída corte de entrada de U deno tado U U ou mais simplesmente U U 1 denota o conjunto dos arcos a A tais que a U a U e a U c a U c neste caso dizemos que a sai entra de em U É conveniente abreviar Agora seja T uma árvore geradora de custo máximo de Gc Então sumZ in mathcalZ Z1 cB leq cT sumZ in mathcalE TZ sumZ in mathcalE Z kappaTZ leq sumZ in mathcalE Z 1 e portanto vale a igualdade em todas as desigualdades o que por sua vez implica que TZ Z 1 para cada Z in mathcalE Concluímos assim que T é uma árvore básica CAMINHOS MÍNIMOS COM CUSTOS NÃONEGATIVOS 49 s b c d e f g h S Figura 32 A figura ilustra o território S s b c d e f do vértice s Note que nenhum arco sai de S existe um stcaminho orientado digamos P Suponha que a t e seja u a ponta final de a Então P tau é um sucaminho orientado donde u S Assim todo arco que tem ponta inicial em S tem também a sua ponta final em S donde S Proposição 31 Uma parte X de V é o território de um vértice s de um digrafo D se e só se para cada x X existe um sxcaminho orientado em D e X O antiterritório de um vértice s é o conjunto dos vértices t de um digrafo D que são origens de caminhos orientados cujo término é s ou seja t está no antiterritório de s se e só se existe um tscaminho orientado em D Por um argumento similar ao exibido acima é fácil concluir que se X é o antiterritório de s então X Proposição 32 Uma parte X de V é o antiterritório de um vértice s de um digrafo D se e só se para cada x X existe um xscaminho orientado em D e X Lema 32 Seja D um digrafo e s t V D Então existe um stcaminho orientado se e só se S para cada stconjunto S Prova O lema é evidente se s t Logo vamos admitir que s t no que segue Suponha que P é um stcaminho orientado e que S é um stconjunto Pelo Lema 31 existe um arco a AP tal que a S ou seja S Suponha agora que S para cada stconjunto S Seja X o territó rio de s em D É evidente que s X Ademais X donde X não é um stconjunto o que aliado a s X implica que t X e portanto D possui um stcaminho orientado Caminho orientado ℓmínimo Seja D um digrafo Suponha que s é um vértice de D e t é um vér tice no território de s Um stcaminho orientado P é ℓmínimo ou de comprimento mínimo se ℓP ℓQ para cada stcaminho orientado Q É fácil constatar que se P u0a1u1 akuk é um u0ukcaminho orientado ℓmínimo então Pui uj é um uiuj caminho orientado ℓmínimo cada 0 i j k De fato supo nha que 0 i j k e Q é um uiujcaminho orientado Então R Pu0 uiQPuj uk é um u0ukcaminho orientado Como P tem comprimento mínimo então ℓP ℓR donde ℓPui uj ℓQ Portanto Pui uj é um uiujcaminho orientado ℓmínimo Lemma 31 Dado um dígrafo D se s e t são vértices de D Se P é um stcaminho orientado é S um stconjunto então existe a in AP tal que a in S Busca em largura O propósito desta seção é de discutir e analisar o algoritmo de busca em largura que determina caminhos de comprimento mínimo em um digrafo sarborescência e sarborescência ℓmínima Seja D um digrafo e s V Uma subádrica T de D é uma sarborescência de D se e s Vₜ nenhum arco de T entra em s e T possui um único scaminho orientado para cada x Vₜ um tal scaminho é denotado por Ts x Se além disso Ts x é um scaminho orientado de comprimento mínimo para cada x Vₜ então dizemos que T é uma sarborescência ℓmínima Vamos por simplicidade confundir uma sarborescência com o seu conjunto de arcos É fácil verificar que se a Eₕ então T a também é uma sarborescência de D Antes de exibir a forma tradicional do algoritmo de busca em largura vamos apresentar uma versão preliminar Seja D um digrafo e s um de seus vértices Seja x um vértice no território de s Vamos denotar por dists x ou simplesmente distsx a distância de s até x ou seja o comprimento de um scaminho orientado ℓmínimo Seja Vi x V distx i para cada i ℕ Seja k ℕ e suponha que X ₕ₀Vi Vamos mostrar que Vi1 ΓVk Xᶜ Suponha que v Vk1 Então existe um scaminho orientado P de comprimento mínimo tal que ℓP k 1 Seja u o vértice que precede v no caminho P É evidente que ℓPs u k No entanto todo subcaminho de um caminho de comprimento mínimo também é de comprimento mínimo e assim ℓPs u distu Segue daí que u Vk Por hipótese v X Concluímos assim que v ΓVk Xᶜ Suponha agora que v ΓVk X Como v é vértice de Xᶜ então distv k 1 Todavia v é também um sucessor de um vértice u Vk Logo existe u vw E Seja P um scaminho de comprimento mínimo Então ℓP vw k 1 donde distv k 1 Portanto distv k 1 e v Vk1 como queríamos Implementação Eis as estruturas de dados para a representação de um digrafo Cada a Arc representa um arco de um digrafo atail é a pontial inicial de a e ahead é a ponta final de a CAMINHOS MÍNIMOS COM CUSTOS NÃONEGATIVOS 51 def iotaself return selftail selfhead def costself return selfcost class Digraph def initself V A selfV setV selfA tupleArcx y for x y in A selfout x for x in selfV for a in selfA selfoutatailappenda def getitemself X if isinstanceX Iterable return a for a in selfA if atail in X and ahead not in X return selfoutX def lenself return lenselfV A discussão acima inspira a seguinte implementação A função re cebe uma representação D de um digrafo V A tal que Dx é o con junto dos arcos que saem de X e devolve uma lista L tal que Li Vi para cada índice i de L e cujo comprimento é maxdistℓs x x está no território de s As seguintes propriedades são válidas no início de cada iteração X v V distℓs x k e R Vk Observe que S Vk1 def bfsD s X s V s R X k 0 while True S ahead for x in R for a in Dx if ahead not in X if not S break V appendS XupdateS R S k 1 return V 52 TEORIA DOS GRAFOS 3 Esta é a versão popular 4 Para conjuntos X e Y uma função par cial de X em Y é parte digamos f de X Y tal que x y1 x y2 f y1 y2 para cada x X e cada y1 y2 Y O domínio de f denotado domf é o con junto x X y Y x y f enquanto que a imagem de f denotada imf é o conjunto y Y x X x y f Uma outra versão Vamos agora analisar uma versão alternativa3 do algoritmo de busca em largura Seja D um digrafo e s V π uma função parcial de V s em A4 Se π é tal que a tripla Dπ domπ s imπ ι imπ é um subdigrafo de D que é ademais uma sarborescência então di zemos que π induz uma sarborescência Neste caso para abreviar di zemos simplesmente que Dπ é uma sarborescência Não é difícil veri ficar se Dπ é uma sarborescência e a V Dπ então Dπ a a também é uma sarborescência Suponha que F é uma parte nãovazia de V Vamos escrever xF e yF para denotar os vértices de F tais que distℓs xF distℓs z distℓs yF para cada z F ou seja xF é o vértice de F mais próximo de s e yF é o vértice de F mais distante de s Sejam π uma função parcial de V s em A e F um subconjunto de VDπ tais que i Dπ é uma sarborescência de caminhos mínimos ii se x VDπ F então Γ x VDπ e iii se F então distℓyF distℓxF 1 Dizemos como de costume que um par π F nessas condições é bom Agora suponha que π F é bom e F Vamos mostrar que o par π F também é bom onde π π a a a V Dπ x F e F F xF a a V Dπ x F Para isso precisamos mostrar que estão satisfeitas as condições i ii e iii com π no lugar de π e F no lugar de F Suponha que a V Dπ x F Seja v a ponta final de a Escreva para abreviar T Dπ Por hipótese ℓTs xF distℓxF donde ℓTs v distℓxF 1 distℓv Vamos agora mostrar que distℓv distℓxF 1 Seja P um svcaminho orientado Como v VT então AP V T Seja b AP V T Em virtude de ii a ponta inicial de b está em F donde b z para algum z F Assim ℓP ℓPs z ℓPz v distℓz 1 distℓxF 1 como queríamos Portanto ℓTs v distℓv distℓxF 1 Su ponha que F Note que distℓxF distℓxF e distℓyF distℓv donde distℓyF distℓv distℓxF 1 distℓxF 1 Teorema 31 Se D é um digrafo s t V e t está no território de s então o comprimento de um scaminho orientado ℓmínimo é igual ao número máximo de um stcortes dois a dois disjuntos isto é minℓP P 𝒫 maxX K é uma parte disjunta de C onde 𝒫 denota o conjunto dos stcaminhos orientados em D e C denota a coleção dos stcortes de D Prova Suponha que D é um digrafo s t são vértices de D e que t está no território de s Suponha que K é uma coleção disjunta de stcortes e que P é um scaminho orientado Então K K implica que Aₚ Aₚ U KK Aₚ U KK Aₚ K KK 1 X agora ℓP Aₚ Aₚ U KK Aₚ U KK Aₚ K KK 1 X onde ℓP X 54 TEORIA DOS GRAFOS 5 Uma argumentação mais simples é a se guinte Suponha que 0 i j distℓt e U i U j Seja então a xy U i U j Então distℓx i e distℓy j 1 Como distℓx i então existe um caminho orientado P de s até x tal que ℓP i Assim Q P xay é um caminho de s até y com ℓQ i 1 o que por sua vez implica que distℓy i 1 Segue daí que j i Esta contradição estabe lece que U i U j onde a terceira igualdade vale pois K é disjunta Portanto o compri mento de qualquer stcaminho orientado é pelo menos o tamanho de qualquer coleção disjunta de stcortes Vamos então provar que vale a igualdade Seja U o território de s em D Lembrese que distℓx denota o com primento de um sxcaminho orientado ℓmínimo para cada x em U Para cada i 0 1 distℓt 1 seja Ui x U distℓx i Vamos primeiro estabelecer que distℓa i e distℓa i 1 para cada i 0 1 distℓt 1 e a U i Seja i 0 distℓt e suponha que a xy U i A definição de Ui implica que distℓx i e distℓy i 1 Vamos mostrar inicialmente que distℓx i Para isso seja P um sxcaminho É claro que Q P xay é um sy caminho Como distℓy i 1 segue que ℓQ i 1 o que por sua vez implica que ℓP i Logo distℓx i o que combinado com distℓx i fornece distℓx i Agora vamos mostrar que distℓy i 1 Note que distℓx i implica que existe um sx caminho digamos P para o qual ℓP i Entretanto Q P xay é um sycaminho com ℓQ i 1 Isto estabelece que distℓy i 1 o que juntamente com distℓy i 1 acarreta distℓy i 1 A afirmação acima implica que se 0 i j distℓt então U i U j De fato se a sai de Ui então distℓa i 1 j Logo a está em Uj e daí a U j Por outro lado se a sai de Uj então distℓa j i Portanto a não está em Ui e assim a U i Consequentemente U i U j Concluímos portanto que U i i 0 distℓt é uma coleção disjunta de stcortes de tamanho distℓt como quería mos 5 Caminho mínimos com custos nãonegativos Vamos agora lidar com uma generalização do problema do caminho de comprimento mínimo Vamos associar um custo a cada arco de um digrafo O custo de um caminho neste caso é soma dos custos dos arcos que fazem parte do caminho O problema em que estamos inte ressados consiste em dado um digrafo com custos nos arcos e um de seus vértices digamos s encontrar um caminho de custo mínimo de s até cada um dos vértices no território de s 56 TEORIA DOS GRAFOS Ora como P começa em s VT e termina em y VT então existe um arco e AP tal que e V T Assim cP cPs e ce cPe y cTs e ce cPe y cTs e ce cTs a ca cTs x xay onde a primeira desigualdade segue pois T é cmínima a segunda de c 0 e a última da escolha de a Logo Ts x xay é um sycaminho cmínimo e consequentemente T a é cmínima Teorema 32 Se D c 0 é um digrafo ponderado e s V então existe uma sarborescência cmínima T tal que o conjunto dos vértices de T é o território de s em D Prova Escolha uma sarborescência cmínima tal que VT é máximo A Proposição 33 implica que V T e portanto VT é o território de s Algoritmo A discussão precedente sugere o seguinte algoritmo Antes entretanto vamos introduzir a seguinte definição Para cada x no terri tório de s seja distcs x ou simplesmente distcx o custo de um sxcaminho orientado cmínimo O algoritmo mantém a cada iteração uma função parcial π de V s em A e uma função parcial d de V em R tais que i Dπ é uma sarborescência cmínima e ii domd VDπ e dx distcx para cada x VDπ A primeira iteração começa com π e d s 0 Cada iteração consiste no seguinte Se domd então Dπ é uma sarborescência cmínima cujos vértices são o território de s e neste caso o algoritmo devolve Dπ e para Suponha que domd Selecione a domd tal que da ca de ce para cada e domd e comece nova iteração com π a a e d a da ca nos papéis de π e d Note que pela Proposição 33 Dπ a a é uma sarborescência cmínima O algoritmo para De fato seja S o território de S em D Observe que a cada iteração S domd diminui Portanto o número de iterações está limitado pelo tamanho de S Digrafo ponderado A ideia agora consiste em generalizar esses resultados quando estão envolvidos custos nãonegativos nos arcos do digrafo Para isso vamos precisar das seguintes definições Seja D um digrafo e c A ℝ uma função custo que leva cada arco a A de um digrafo D em um número real ca chamado de custo de a O par Dc é denominado de digrafo ponderado Seja P u₀e₁eₖuk um caminho orientado de D O custo de P é o número cP i0k cei Vamos por enquanto lidar com custos nãonegativos Para vértices s t de D dizemos que um stcaminho orientado P é cmínimo se cP cQ para cada stcaminho orientado Q Escrevemos c 0 quando ca 0 para cada arco a de D Escrevemos também Dc 0 para denotar um grafo ponderado Dc para o qual c 0 CAMINHOS MÍNIMOS COM CUSTOS NÃONEGATIVOS 57 6 Vale destacar que esta forma de des crever um algoritmo na qual as propri edades invariantes aquelas que são vá lidas no ínico de cada iteração têm um destaque especial é de autoria do Profes sor Paulo Feofiloff A ideia consiste em exibir os objetos matemáticos que o al goritmo manipula e mostrar como tais objetos se transformam a cada iteração Fica por conta do leitor identificar que de fato é possível mapear tais objetos e as operações que os manipulam em enti dades computacionais Implementação class WArc def initself cost tail head selfcost cost selftail tail selfhead head def iotaself return selftail selfhead def costself return selfcost def reprself return fselfcostselftailselfhead class WDigraph def initself V A selfV setV selfA tupleWArcc x y for c x y in A selfout x for x in selfV for a in selfA selfoutatailappenda def getitemself X if isinstanceX Iterable return a for a in selfA if atail in X and ahead not in X return selfoutX def lenself return lenselfV def naivemcpD s π d s None s 0 while True K Ddkeys if not K break a minK keylambda e detail ecost dahead datail acost πahead a return π d Versão preguiçosa do algoritmo de Dijkstra Não é difícil extrair da Proposição 33 um algoritmo eficiente para determinar uma arborescência de caminhos de custo mínimo em um digrafo6 58 TEORIA DOS GRAFOS Algoritmo A versão preguiçosa do algoritmo de Dijkstra mantém a cada iteração uma função parcial π de V s em A uma função parcial d de V em R e um conjunto K de arcos tais que i Dπ é uma sarborescência cmímima ii domd VDπ e dx distcx para cada x VDπ e iii V Dπ K A primeira iteração começa com π d s 0 e K s Cada ite ração consiste no seguinte Se K então Dπ é uma sarborescência cmínima cujos vértices são o território de s e neste caso o algoritmo devolve Dπ e para Suponha que K Selecione uma aresta a K tal que da ca de ce para cada e K Se a domd então comece nova iteração com π d e K a nos papéis de π d e K respectivamente Se a domd então a V Dπ Note que neste caso Dπa a de acordo com a Proposição 33 é uma sarborescência cmínima Comece nova iteração com π a a d a da ca e K a e a e domd nos papéis de π d e K respectivamente É fácil verificar que as demais propriedades destacadas em i ii e iii estão satisfeitas no início da próxima iteração Para provar que o algoritmo termina é conveniente acrescentar um novo objeto a cada iteração que corresponde ao con junto dos arcos que foram removidos de K Cada iteração então man tém também um conjunto R A primeira iteração começa com R e uma nova iteração começa com R a no lugar de R Não é difí cil constatar que R K e R K A Como R aumenta a cada iteração então o número de iterações está limitado por A Implementação da versão preguiçosa from heapq import heappush heappop class CostTo def initself pathcost arc selfpathcost pathcost selfarc arc def ltself other return selfpathcost otherpathcost def dijkstraD s π d s None s 0 Um teorema mínimo Sejam s e t vértices de um digrafo ponderado D c O par K y onde K é uma coleção de stcortes e y K R é 7 cdisjunto se K K yKa ca para cada a A O número K for a in Ds heappushK CostToacost a while K cost heappopK a costarc if ahead in d continue dahead τahead costpathcost a for e in Dahead if ehead in d continue heapushK CostTodetail ecost e return π d onde a última desigualdade segue de a AP XKa 1 uma vez que K é um stcorte e P é um stcaminho orientado Logo mincP P P max K K yK K y Λ 4 Caminhos mínimos com custos arbitrários Neste capítulo vamos estudar o problema do caminho de custo mí nimo envolvendo custos arbitrários Assim podem haver arcos com custo negativo É importante ressaltar que encontrar um caminho sim ples de custo mínimo sem restrições no custo é um problema NP difícil Um objeto importante na discussão que segue são os ciclos orienta dos de um digrafo Lembrese que um ciclo orientando de um digrafo é um caminho orientado u0a1 akuk tal que k 2 u0 uk e os vértices u0 u1 uk1 são dois a dois distintos Um ciclo orientado K em um digrafo ponderado D c é cnegativo se cK 0 A existência de ci clos orientados cnegativos é o que coloca o problema de encontrar um caminho simples cmínimo no universo dos problemas NPdifíceis Digrafo ponderado conservativo Um digrafo ponderado D c é dito conservativo se cK 0 para cada ciclo K de D ou seja D c é livre de ciclos cnegativos O próximo lema mostra que em digrafos ponderados e conservativos se um vértice t está no território de s então existe um stcaminho orien tado cmínimo que é simples Lema 41 Se D c é um digrafo ponderado e conservativo s e t são vértices de D e P é um stcaminho orientado de D então existe um st caminho orientado e simples Q de D tal que VQ VP AQ AP e cQ cP Prova Seja D c um digrafo ponderado e suponha que D c é con servativo Suponha que s e t são vértices de D Vamos mostrar por indução em VP que se P é um stcaminho orientado de D então existe um stcaminho orientado e simples Q de D tal que VQ VP AQ AP e cQ cP Seja P u0e1u1 ekuk é um stcaminho orientado Se ui uj para cada 0 i j k então P é simples e não há nada a Se D c é um dígrafo ponderado e conservativo e s t são vértices de D Se p V ℝ é um potencial e P P um stcaminho orientado então cP k i1 cαi k i1 pui pui1 puk pu0 pt ps Suponha agora que D c é conservativo Para cada par s t V seja Ps t o conjunto dos stcaminhos orientados de D Seja p V ℝ tal que pt é o custo de um caminho orientado de custo mínimo dentre aqueles que terminam em t ou seja pt mincP P sV Ps t Suponha que p V R e xy A é tal que cpa 0 Há dois casos a considerar Caso 1 x Xy Neste caso seja P u₁e₁ uₖeₖ um yxcaminho cada uma de cujas arestas e tem custo preduzido nãopositivo ie cpei 0 Seja K P y e ponha ei1 a Observe que cpei 0 para cada i k e cpei1 0 Mas 0 k1 i1 cpei k1 i1 cei pei pei k1 i1 cei cK e portanto K tem custo negativo Caso 2 x Xy Note que se e Xy então cpe 0 Tome ε minca a Icpa cpe e Xy e seja p V R tal que pu pu ε se u X pu caso contrário para cada a V Observe que para arco e A se e Xy então cpe cpe se e Xy então cpe ce pe pe ce pe ε pe cpe ε cpe onde a última desigualdade segue de ε 0 suponha primeiro que ε cpa Por conseguinte cpa 0 Segue daí que σcp σcp a o que completa a prova neste caso Suponha agora que ε cpa Então ε cpe para algum arco e Xy onde cpe 0 Ora neste caso σcp σcp CAMINHOS MÍNIMOS COM CUSTOS ARBITRÁRIOS 67 cpa 0 e Xy p Xy p e assim por hipótese de indução ou i existe um ciclo K que contém a e cK 0 ou ii existe q V R tal que σcq σcp a e assim σcq σcp a Isto completa a prova da afirmação Vamos provar por indução em A σcp que para cada p V R ou existe um potencial q de D c tal que σcq σcp ou existe um ciclo K de custo negativo em D c Seja p V R uma função ar bitrária Se A σcp 0 então então cpa 0 para cada a A ou equivalentemente pa pa ca para cada a A donde p é um potencial o que completa a prova neste caso Suponha então que A σcp 0 Então existe a xy A tal que cpa 0 Pelo fato acima ou i existe um ciclo K que contém a tal que cK 0 ou ii existe uma função p V R tal que σc p σcp a Ora se vale i não há mais nada a provar Suponha que vale ii Neste caso A σcp A σcp donde por hipótese de indução ou existe um potencial q de D c tal que σcq σcp e portanto σcq σcp ou existe um ciclo K de custo negativo em D c Isto completa a prova Algoritmo de BellmanFord Vamos precisar das seguintes definições Seja D c um digrafo pon derado s um dos vértices de D e k um inteiro nãonegativo Para cada t V seja Pkt o conjunto dos stcaminhos orientados P tais que ℓP k e dkt mincP P Pkt Vamos admitir que min r e r para cada real r Note que d0s 0 e d0t para cada t V s Vamos agora mostrar que dkt mindk1t dk1a ca a t para cada t V e cada inteiro k 0 Seja então t V e k 0 Suponha ademais que dkt do contrário não há nada a provar Vamos primeiro estabelecer que dkt mindk1t dk1a ca a t Note que Pk1t Pkt donde dkt dk1t Suponha que a t e seja P Pk1u tal que cP dk1u ca onde u a Ora 68 TEORIA DOS GRAFOS ℓP k 1 e assim ℓP uat k donde dkt dk1u ca como queríamos Vamos agora verificar que dkt mindk1t dk1a ca a t Seja P Pkt tal que cP dkt e a rt o último arco de P Então P Q rat para algum srcaminho orientado Se ℓP k 1 então P Pk1t donde dkt dk1t Suponha então que ℓP k Então Q Pk1r o que implica que dk1r cQ e portanto dkt cP cQ ca dk1r ca como queríamos Ciclos negativos Ponha n V Afirmamos que dn dn1 se e só se o subdigrafo induzido pelo território de s possui um ciclo orientado c negativo De fato suponha primeiro que que dn dn1 Então existe t V tal que dnt dn1t Assim existe um stcaminho orientado P tal que ℓP n e cP dnt Como ℓP n então P possui um ciclo orientado K Sejam P e P caminhos orientados tais que P P K P Note que Q P P é um stcaminho orientado tal que Q Pn1t donde dn1t cQ Logo dn1t dnt cP cQ cK dn1t cK e consequentemente cK 0 Suponha agora que dn dn1 Suponha que a xy é um arco de D cujas pontas estão no território de s Como dny dn1y então dn1y dn1x ca donde dn1 é um potencial no subdigrafo de D induzido pelo território de s e portanto o subdigrafo induzido pelo território de s é livre de ciclos orientados cnegativos 5 Emparelhamentos em Grafos Bipartidos Este capítulo estuda o problema do emparelhamento máximo e da cobertura mínima em grafos bipartidos Para este par de problemas é irrelevante a presença de mais de uma aresta com um mesmo par de pontas Por isso vamos lidar com grafos simples Lembrese que um grafo simples G é um par V E em que V é um conjunto finito e nãovazio e E V 2 Como de costume neste caso escrevemos zy ou xy quando x y é uma aresta de G A outra hipótese fundamental do capítulo é a de um grafo bipartido Um grafo é 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 Emparelhamentos Seja G um grafo Um emparelhamento de G é um subconjunto de arestas que adiciona a duas disjuntas Mais formalmente M E é um emparelhamento de G se2 e f M e f Para um emparelhamento M de G dizemos que um vértice x de G é Msaturado ou saturado por M se x é ponta de uma das arestas em M ou seja se x U M caso contrário dizemos também que uma parte S de V é Mexposto ou exposto por M Dizemos também que M parte S de V é Msaturada se M saturada cada vértice de S O Teorema de König O Teorema de König é um exemplo de uma relação mínima na Teoria dos Grafos Ele relaciona dois conceitos o de cobertura de vértices e o de emparelhamento e estabelece que o tamanho de um emparelhamento máximo coincide com o tamanho da cobertura mínima de vértices Suponha que C é uma cobertura de vértices de um grafo G e M é um emparelhamento de G Como C é cobert então toda aresta de M tem ao menos uma de suas pontas em C No entanto as arestas de uma de M são disjuntas onde C M Eis uma prova mais formal deste fato C C U M e M C e e M C e e M M Observe que a igualdade segue uma vez que M é um emparelhamento e consequentemente C e C f para cada e f M É claro que a desigualdade 51 implica que minC C C maxM M M 52 e τG νG dizemos que cobertura de vértices C de G é mínima se C τG e um emparelhamento M de G é máximo se M νG Assim τG é o tamanho de uma cobertura mínima de vértices de G e νG é o tamanho de um emparelhamento máximo de G Com esta notação podemos escrever a desigualdade acima de uma forma mais compacta τG νG Prova Sejam G um grafo M um emparelhamento de G e C uma cobertura de vértices de G tais que M C Sejam M e C um emparelhamento e uma cobertura de vértices de G respectivamente Em virtude da desigualdade 51 temos que M C M Logo M é um emparelhamento máximo De forma similar a desigualdade 51 implica que C M C Assim C é uma cobertura mínima de vértices Isto estabelece i Note que C e 1 para cada aresta e de G Por conseguinte M C C M eM C ne eM C ne eM Isto dado desigualdade vale com igualdade Assim C C M C C M onde C C M o que estabelece ii Ademais C e 1 para cada e M e eM C e eM 1 M implicam que C ne 1 para cada e M o que valida iii Vamos agora enunciar o célebre Teorema de Kónig e a seguir diversas provas do mesmo 72 TEORIA DOS GRAFOS 3 C1 contém uma das pontas da aresta uv2 mas C1 não contém u donde v2 C1 4 A soma simétrica de conjuntos X e Y de notada X Y é o conjunto X Y Y X Note que X Y X Y X Y Lembrese que X Y X Y X Y donde X Y X Y 2X Y C1 C2 u v2 v1 Figura 54 Ilustração das coberturas C1 de G1 e C2 de G2 τG De forma similar suponha que e v1 v2 C1 ou v1 v2 C2 Ajuste a notação de tal forma que v1 v2 C1 Então C1 é uma cobertura de vértices de G donde τG1 τG Suponha agora que u C1 C2 e v1 v2 C1 e v1 v2 C2 Então3 v2 C1 v1 C1 e v1 C2 v2 C2 Ajuste a notação se necessário de tal forma que τG1 τG2 Con sidere o grafo H Gu C1 C2 Observe que4 u C1 C2 1 τG1 τG2 2C1 C2 1 2τG1 C1 C2 Seja C uma cobertura mínima de vértices de H Como cada um dos lados de qualquer bipartição de H é uma cobertura de vértices de H então C τG1 C1 C2 Vamos mostrar que C C1 C2 é uma cobertura de G Suponha que a é uma aresta de G Se a uv1 ou a uv2 então C cobre a uma vez que neste caso a é uma aresta de H Se a uv1 e a uv2 então C1 cobre a e C2 também cobre a Segue daí que ou a tem uma ponta em C1 C2 ou a tem uma ponta em C1 C2 e a outra em C2 C1 e neste último caso a é uma aresta de H e portanto coberta por C Concluímos assim que C C1 C2 é uma cobertura de G Ora τG C C1 C2 τG1 C1 C2 C1 C2 τG1 τG Portanto vale igualdade em todas as passagens e assim τG1 τG como queríamos Com este lema podemos partir agora para a prova Seja G um grafo bipartido A prova é por indução em E Suponha primeiro que du 1 para cada u V Então E é um emparelhamento e neste caso τG νG Suponha então que existe u V tal que du 2 Pelo Lema 52 existe uma aresta e u tal que τG e τG Por hipótese de indução τG e νG e Assim νG νG e τG e τG νG e portanto τG νG como queríamos EMPARELHAMENTOS EM GRAFOS BIPARTIDOS 73 P Figura 55 A figura ilustra um caminho P que é Maumentador As arestas de cor vermelha fazem parte do emparelha mento M Os vértices de cor vermelha são Msaturados O primeiro e o último vértice são Mexpostos Note que M P é um emparelhamento maior que M s1 s2 t1 t2 Z Zc Figura 56 A figura ilustra o Caso 2 Os arcos azuis são do emparelhamento Os vértices verdes são os vértices de T en quanto que os demais são de S Aqui RS s1 s2 RT t1 t2 Nenhum arco sai de Z uma vez que Z é o territó rio de RS Todo arco que entra em Z tem uma ponta inicial em S Zc e ponta final em T Z Note que T Z S Zc é uma cobertura de vértices Caminhos aumentadores Para a próxima prova vamos precisar do con ceito de caminho aumentador conceito este de fundamental importân cia no estudo de emparelhamentos em grafos Seja G um grafo e M um emparelhamento em G Um caminho simples v0e1v1e2 e2k1v2k1 com k 0 é Maumentador se as arestas de índice ímpar e1 e3 e2k1 não estão em M as arestas de índice par e2 e4 e2k estão em M e os vértices v0 e v2k1 são Mexpostos Ora se P é um caminho simples Maumentador então M EP é um emparelhamento e M EP M 1 e portanto M não é máximo Prova via Algoritmo Húngaro Seja G um grafo bipartido com bipartição S T isto é T Sc Seja M um emparelhamento de G Vamos mostrar que ou i existe um emparelhamento maior que M ou ii existe uma cobertura de vértices de G de tamanho M Seja D o digrafo simples tal que VD VG e AD AT S AST onde AT S t s t T s S ts M e AST s t s S t T st EG M ou seja cada aresta de M é orientada de T para S enquanto que as de mais arestas são orientadas de S para T No que segue é conveniente confundir os arcos de D com as arestas de G uma vez que há uma bije ção natural envolvendo tais conjuntos Observe que se t T e M cobre t então d Dt 1 e se s S e M cobre s então d Ds 1 Seja RS o conjunto dos vértices Mexpostos que estão em S e RT o conjunto dos vértices Mexpostos que estão em T Seja Z o território de RS em D Note que DZ Ademais se P é um caminho simples em DZ que começa em algum vértice de RS então P alterna arcos de AD M e arcos de M Em particular se o término de P é um vértice de RT então P é um caminho simples Maumentador Há dois casos a considerar Caso 1 RT Z Tome um caminho simples P em D com início em RS e término em RT Neste caso M EP é um emparelhamento maior que M Caso 2 RT Z Vamos mostrar que T Z S Zc é uma cobertura de vértices de G Para isso vamos primeiro estabelecer que T Z cobre toda aresta com pelo menos uma ponta em Z De fato observe primeiro que se t T Z então t é Msaturado se s S Z RS então d Ds 1 finalmente se s RS então d Ds 0 Seja a um arco de D com pelo menos uma das pontas em Z Se a tem exatamente uma Prova de DeCaris Seja G um grafo bipartido O teorema é trivial se G não tem arestas Assim vamos supor que G tem pelo menos uma aresta Afirmamos que para cada aresta de G uma de suas pontas é saturada por todo emparelhamento máximo em G ou mais formalmente 54 y E M M x U M M y U onde M é o conjunto dos emparelhamentos máximos de G Eis a prova da afirmação Seja qualquer aresta de G Não há nada a provar se todo emparelhamento máximo saturar x Assim suponha que existe um emparelhamento máximo M que não satura x Vamos mostrar que N é um emparelhamento e N não satura y então N não é máximo Admita então que N é um emparelhamento e N não satura y Se N não satura x então N xy é um emparelhamento onde N não é máximo Suponha que N satura x Ora M é máximo e M não satura x assim M satura y Seja P a componente conexa de GM N que contém x É claro que x tem grau um em GM N assim P é um caminho que conecta um de suas pontas e outra x seja z a outra ponta do P A maximalidade de M implica que P tem comprimento par Como G é bipartido então x z onde z y Ora y também tem grau um em GM N onde y não é um dos vértices de P Isto implica que y P é um caminho Naumentador e portanto N não é máximo Isto estabelece 54 EMPARELHAMENTOS EM GRAFOS BIPARTIDOS 75 u v w z Figura 58 A figura ilustra o vértice u tal que du 3 A aresta vermelha poderia ser uma aresta em M X ΓX s1 s2 s3 s4 s5 t1 t2 t3 t4 t5 t6 Figura 59 A figura ilustra um conjunto X e sua vizinhança ΓX Prova de Rizzi Seja G um grafo bipartido A prova é por indução em V E Suponha primeiro que du 2 para cada vértice u de G Neste caso cada componente conexo de G é um caminho ou um ciclo de comprimento par É fácil verificar que diante disso νG τG Suponha agora que existe um vértice u de G tal que du 3 Seja v um vizinho de u e considere o grafo G G v Por hipótese de indução νG τG É evidente que νG 1 νG νG O restante da prova é dividida em dois casos Admita primeiro que νG νG 1 Seja C uma cobertura mí nima de vértices de G isto é C τG νG Então C v é uma cobertura de vértices de G e ademais C v νG e assim pelo Lema 51i C v é uma cobertura mínima de vértices de G Logo τG νG como queríamos Suponha agora que νG νG Isto implica que existe um em parelhamento máximo M de G que não satura v Como du 3 existe uma aresta f uw E M tal que w v Considere o grafo G G f É claro que νG νG já que f não está em M Por indução νG τG Seja C uma cobertura mínima de vértices de G Note que C M O Lema 51iii implica que v C Mas uv EG e como C é uma cobertura de vértices de G então u C Segue daí que C é uma cobertura de vértices de G No entanto C M e pelo Lema 51i νG τG Isto completa a prova do Teorema de Konig Teorema de Hall O propósito desta seção é apresentar o Teorema de Hall e suas apli cações Por ser um teorema fundamental vamos exibir diversas provas do mesmo cada uma ilustrativa a sua maneira É conveniente retomar algumas definições Para um grafo G e um conjunto de vértices X V a vizinhança de X ΓX é o conjunto dos vértices y Xc que possuem pelo menos um vizinho em X e o tamanho de ΓX é escrito γX ΓX Para um vértice v V escrevemos Γv e γv nos lugares de Γv e γv respectivamente Se G é bipartido e X está contido em um dos lados de uma bipartição de G então ΓX é o conjunto dos vértices y que estão do outro lado da bipartição que têm algum vizinho em X Condição de Hall Seja G um grafo e S uma parte de V Dizemos que G satisfaz a condição de Hall em relação a S se 76 TEORIA DOS GRAFOS Um emparelhamento satura um conjunto S de vértices se cada vértice em S é saturado pelo em parelhamento γX X para cada X S Teorema 52 Hall Seja G um grafo bipartido com bipartição S T Então existe um emparelhamento que satura S se e só se G satisfaz a condição de Hall em relação a S Primeira prova É evidente que se G possui um emparelhamento que satura S então γX X para cada X S Vamos então provar que se G satisfaz a condição de Hall em relação a S então G possui um emparelhamento que satura S A prova é por indução em S Se S 1 então o resultado é evidente Suponha que S 2 Temos dois casos a considerar Caso 1 γX X para cada X S Tome s S Como γs 0 então escolha uma aresta e incidente em s e seja t a outra ponta de e Seja G G s t e ponha γ γG e Γ ΓG Então G tem bipartição S S s T T t Seja X S Observe que ΓX Γ X t Segue daí que γX 1 γX X 1 donde γX X Assim G satisfaz a condição de Hall em relação a S e daí por hipótese de indução existe um emparelhamento M de G que satura S Logo M e é um emparelhamento de G que satura S Caso 2 γX X para algum X S X ΓX G G S X T ΓX Figura 510 A figura ilustra o Caso 2 As linhas pontilhadas em azul são possíveis aresta de G em verde de G e final mente as arestas vermelhas são arestas de G que não são arestas de G e nem de G Seja G GX ΓX com bipartição X ΓX e ponha γ γG e Γ ΓG Seja G GSXT ΓX com bipartição SX T ΓX e ponha γ γG e Γ ΓG Note que se Y X então Γ X ΓX Portanto G satisfaz a condição de Hall em relação a X Logo por hipótese de indução existe um emparelhamento M que satura X em G Vamos verificar que G satisfaz a condição de Hall em relação a S X Ora se Y S X então ΓX Y ΓX Γ Y Segue Prova do Algoritmo Húngaro Vamos provar que G não possui um emparelhamento máximo saturando S Se não existe X S tal que γX X Para isso suponha que G não possui um emparelhamento que satura S Considere um emparelhamento máximo M de G Sejam R S e Z como na página 73 ou seja R S é o conjunto dos vértices de S que são Mexpostos e Z é o território de R S a figura 5 ilustra a prova Observe que S Z T Z uma vez que todo vértice de T Z é ponta inicial da orientação de uma aresta de M e R S e ΓS Z T Z Portanto γS Z T Z M como queríamos para cada X Y e S Suponha que t T é tal que χXYt 1 ou χXYt 1 EMPARELHAMENTOS EM GRAFOS BIPARTIDOS 79 e portanto γs 1 como queríamos Resta verificar que γt 1 para cada t T Suponha s1 s2 S Então 2 γs1 γs2 γs1 s2 2 donde Γs1 Γs2 ou seja nenhum par de vértices distintos de S compartilha algum vizinho em T Portanto γt 1 para cada t T Corolário 51 Seja G um grafo bipartido com bipartição S T Existe um emparelhamento perfeito de G se e só se S T e G satisfaz a condição de Hall em relação a S Corolário 52 Seja G um grafo bipartido com bipartição S T Existe um emparelhamento perfeito em G se e só se G satisfaz a condição de Hall em relação a S e em relação a T Lema 54 Seja G é um grafo bipartido com bipartição S T k ℓ inteiros positivos tais que k ℓ Se ds k para todo s S e dt ℓ para todo t T então G possui um emparelhamento que satura S Prova A prova é uma aplicação do Teorema de Hall Seja X S Então kX ℓγX kγX Logo X γX Assim pelo Teorema de Hall G possui um emparelhamento que satura S A prova dá por indução em E O resultado é evidente se E 1 De fato se u S T então a sequência u é STcaminho e portanto deve con ter um vértice de um STseparador C Logo u C 6 Caminhos Disjuntos Teoremas de Menger Há diversas formas do Teorema de Menger A primeira que vamos exibir relaciona dois caminhos disjuntos nos vértices entre dois vértices e conjuntos de vértices que tocam todo caminho entre tais vértices A prova do Teorema requer em virtude da indução usada uma genera lização que depende da noção de caminhos que começam e terminam em certos subconjuntos de vértices e de conjuntos que desconectam tais subconjuntos de vértices Coleção disjunta nos vértices de caminhos Seja D um digrafo Uma cole ção P de caminhos é disjunta nos vértices se cada par de caminhos dis tintos não possui vértices em comum ou seja P Q P VP VQ É claro que em tal caso nenhum par de caminhos distintos possui um arco em comum STcaminho Seja S T V Um STcaminho é um caminho cujo iní cio está em S e cujo término está em T Um STcaminho simples é um STcaminho P tal que todo vértice distinto do início e do término de P está em S Tc O primeiro ingrediente da generalização são cole ções disjuntas nos vértices de STcaminhos simples o segundo são os conjuntos que desconectam S de T STseparador Um conjunto C V é um STseparador se todo ST caminho contém um vértice de C ou seja se P é um STcaminho então VP C 61 Note que se C é um STseparador então S T C1 A seguinte desi Teorema 61 Seja D um dígrafo e S T partes de V Então o tamanho de uma coleção disjunta nos vértices de STcaminhos é igual ao tamanho de um STseparador de tamanho mínimo CAMINHOS DISJUNTOS 83 x y S C T Figura 61 A figura ilustra a composição das coleções P e Q para formar uma co leção disjunta nos vértices de tamanho k de STcaminhos 5 Suponha que VPu VQv contém algum vértice digamos z de Cc Seja s a ponta inicial de Pu e t a ponta final de Qv Ora u v é término início de Pu Qv e é ademais o único vértice de C x C y em VPu VQv Note que se s C então u s donde Pu s uma vez que Pu é simples o que por sua vez contraria z VPu Concluímos assim que s Cc De forma similar t Cc Se u x então Pus z não contém nenhum vértice de C Suponha que u x Neste caso u C donde z u Como u é o único vértice de C em Pu e z u então Pus z não con tém nenhum vértice de C De forma si milar Qvz t não contém nenhum vér tice de C Assim Ps z Qz t é um STcaminho em D a que não contém vértices em C o que é uma contradição pois C é um STseparador em D a consequentemente Z k donde kD a S C x k4 Ora C x é um S Cxseparador em Da e assim kDa S Cx k Por hipótese de indução existe uma coleção P disjunta nos vértices de tamanho k de S Cxcaminhos em Da os quais sem perda de generalidade podemos admitir que são caminhos simples Assim cada u em C x é término de exatamente um caminho simples digamos Pu em P ademais Pu u C x P Um argumento similar garante que existe uma coleção Q disjunta nos vértices de tamanho k de C y Tcaminhos simples em D a Assim cada u em C y é início de exatamente um caminho simples digamos Qu em Q ademais Qu u C y Q É claro que se u C x e v C y então VPu VQv C5 e por conseguinte VPu VQv u se u v e se u v Logo Pu Qu é um STcaminho simples em D para cada u C e Px xay Qy é um STcaminho simples em D Portanto Px xay Qy Pu Qu u C é um coleção disjunta nos vértices de tamanho k de STcaminhos em D como queríamos