Teoria dos Grafos: Noções Básicas e Estruturas de 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 Mario Leston Teoria dos Grafos 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 Além disso V e E são conjuntos disjuntos ou seja V E Vamos ter que observar comentários sobre a notação que às vezes pode ser torna uma chateação por diversos motivos inclusive o estético Um grafo G é uma tripla Logo é conveniente definir uma notação para extrair cada componente da tripla Escrevemos assim VG para denotar o conjunto dos vértices de G De forma similar escrevemos EG e ιG para denotar o conjunto das arestas de G e a função de incidência de G Às vezes por uma questão puramente estética vamos alternativamente escrever VG EG e ιG em vez de V G EG e ιG respectivamente Esta convenção será utilizada com frequência para outras funções que vamos definir Além disso quando houver um único grafo no contexto da discussão evidentemente vamos simplesmente escrever V E e ι em vez de suas versões mais longas O número de vértices de G V G é denotado mais simplesmente por G o número de arestas EG por E Para cada aresta e ιe é um objeto da forma u v em que u e v são vértices distintos de V Por brevidade escrevemos 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 denotado 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 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 u 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 Subgrafo induzido 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 f F jf 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 acaba sendo conveniente confundir o conjunto de arestas F como o grafo GF hábito este que será recorrente durante o texto sempre que não houver possibilidade de confusão Remoção de vértices e arestas Para um conjunto de vértices X V denotamos por G X o grafo induzido por T e isto é GX e dizemos que G X é o grafo obtido através da remoção dos vértices em X Para um vértice v G escrevemos G v no lugar de G v De forma similar para cada F E denotamos por G F o grafo V E F μEF e dizemos que G F é o grafo obtido de G através da remoção das arestas em F Para uma aresta e de G escrevemos por simplicidade G e em vez de G e Como ilustração vamos provar por indução em G que se G é um grafo finito então v V dv 2G Suponha que G é um grafo então G é 0 então v V dv 0 e não há mais nada a verificar Suponha então que G 1 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 IG é par Seja G um grafo Suponha primeiro que G 0 Então IG onde IG é par Supõe agora que G 1 Escolha uma aresta e e G Considere o grafo H G e Como H G então por hipótese de indução H G 1 Assim por hipótese de indução H v H dHv Ora dHx dx 1 dHy dy 1 e dHz dz 1 para cada z V x y Temos os seguintes casos Caso 1 x y IH Neste caso IG IH x y onde 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 Caminhos e outros animais A noção de grafo e sua representação gráfica sugerem imediatamente a noção de caminho Vamos lidar com diversas variantes desta noção Seja G um grafo Um caminho em G é uma sequência que alterna vértices e arestas de tal forma que as pontas de cada aresta na sequência são 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 para denotar o conjunto dos vértices de P isto é v0 vk e EP para denotar o conjunto das arestas de P isto é e1 ek Dizemos que P é um g0 kcaminho ou um caminho de v0 até vk sendo um caminho que inicia 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 k É conveniente muitas vezes confundir um caminho P com o grafo VP EP μIP Assim por exemplo se v VP então dP é o grau de v no grafo P Com esta identificação podemos escrever P em vez de VP e P em vez de EP As vezes vamos nos interessar tanto somente pelos vértices de um caminho quando então vamos enumerar isto somente pelas arestas de um caminho vamos pois então somente 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 vi1ei1 ejvj 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 Caminhos são sequências finitas e estas podem ser concatenadas A concatenação dos caminhos P1 v0e1v1 ekvk e P2 w0f1 fmwm tais que vk w0 denotada P1 P2 é o caminho que v0e1v1 ekf1 fmwm Seja G um grafo e considere a matriz AG V V ℤ tal que AGx y é o número de arestas de G cujo comprimento é k para cada k ℕ e x y V Teorema 11 Se G é um grafo então AGkx y é o número de xycaminhos de G cujo comprimento é k para cada k ℕ e x y V 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 Prova Para cada inteiro nãonegativo k cada par x y de vértices seja Pkx y o conjunto dos k caminhos de G de comprimento k É claro que P0x x x para cada x in V Ademais para cada inteiro k 0 e cada x y in V Pkx y bigcupz in V Pk1x z cdot Acx 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 Ak1Gx y Pk1x y Sejam x y vértices de G Então Pkx y sumz in V Pk1x zAcz y sumz in V Ak1Gx z AkGz y Acx y 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 subset V seja EX o conjunto das arestas de G que tem 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 subset V tal que EX é máximo Afirmaremos que dHv geq dv2 para cada v in V Suponha que x in V Ajuste a notação de tal forma que x in X Seja Y X x Note que EY EX abla HXx cup abla HYx A escolha de X implica que EX geq EY Segue daí que EX geq EY HYx conforme definido onde dHXx geq HYx equiv dHYx Mas dx dHXx dHYx Portanto dHX geq dX2 Lemma 11 implica que 2E leq sumv in V dHv geq sumv in V dv2 G e por conseguinte G geq G2 como queríamos 19 Grafos simples Teorema 14 Mantel Se G é um grafo simples livre de triângulos então G leq G24 Primeira prova A prova depende do seguinte lema Lema 14 Para todo natural n maxknk k in 0 n leq n24 Prova O resultado é óbvio se n 1 Assim vamos supor que n geq 2 É evidente que existe a in 0 n tal que ana maxknk k in 0 n É fácil ver que n 2 implica 0 a n Note que a1na1 leq ana Leftrightarrow ann2a22a leq ana2 Leftrightarrow 2a leq n1 onde a leq fracn 12 Além disso a 1na 1 leq ana Leftrightarrow 2a n 1 onde a fracn 12 leq fracn24 logo a left lfloor fracn2 right rfloor ou a left lceil fracn2 right rceil Finalmente 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 Há uma relação simples envolvendo o número de vértices e o número de arestas de uma árvore 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 VP 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 J 1 Seja T uma árvore nãovazia O resultado é necessário 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 J 1 1 J 1 1 T 1 como queríamos Exercício 24 Prove que um grafo nãovazio T é uma árvore se e só se T é acíclico e T I 1 Solução Se T é uma árvore então por definição T é acíclico Além disso T I 1 Suponha que T é acíclico e T I 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₁ 1 T 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 GX é 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 e considere o subgrafo U GET e Seja z a ponta de e em X e y a ponta de e em Xₑ 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 VT Por hipótese existe um caminho P que une t e x em T onde P xy é um caminho de t até y em U Logo U é conexo Além disso U é acíclico uma vez que T é acíclico de 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 Suponha x y VT então x e y são comparáveis em T r se x VTr y ou seja se x está no caminho de r até x em T Seja T uma árvore geradora de um grafo G e V Dizemos que T é uma árvore de busca em profundidade com raiz r se x e y são comparáveis em T r sempre que e ET T Teorema 25 Se G é um grafo conexo e r V então G possui uma árvore de busca em profundidade com raiz r Á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 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 C₁ Cₖ com k 1 as componentes conexas de G r Para cada i k seja ti um vizinho de r em Cᵢ e uma aresta com pontas r e tᵢ Por hipótese de indução existe uma árvore de busca em profundidade Tᵢ de GCᵢ com raiz tᵢ para cada i k É claro que Tᵢ eᵢ i k kTᵢ é uma árvore geradora de G Vamos mostrar que T r é uma árvore de busca em profundidade Note que não há arestas cujas pontas estão em diferentes componentes de G r Seja e EG T Então ambas são arestas pretas em G e tₘ também está em T sv C1 C2 para algum C1 C2 E então C1 y C2 y B Proposição 21 Suponha que T é uma árvore geradora de um gráfico G e e T é E E T São equivalentes Á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 exist e K T tal que T f e é uma árvore geradora de G que ademais tem custo mínimo pois cT f e cT Note que f F pois F K donde F e T f e e portanto F e é também uma floresta boa de G como queríamos 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 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 Gc é extrema se cF cF Considerar um conjunto finito e nãovazio V de elementos chamados documentos Suponha que a cada par uv de elementos de V está associado um número real nãonegativo duv denominado de dissimilaridade entre u e v e tal que i duu 0 para cada u V ii duv 0 para cada u v V e iii duv dvu para cada uv V Queremos agrupar os elementos de V em um certo número inteiro k tal que 1 k V de conjuntos nãovazios dos a dois disjuntos cuja união é V de tal forma que documentos similares 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 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 Se F é uma floresta extrema de um grafo ponderado Gc e e é uma aresta unindo diferentes componentes conexas de VF então ce cF para cada f F Se F é uma floresta extrema de um grafo ponderado Gc e e é uma aresta unindo duas componentes conexas de VF e é uma kpartição ótima de V Segue daí que cT sume in ET cuw sumu in I sumv in J x2ux2v sume in E left TZ right sume in E Z kappaTZ Teorema 215 Seja mathcalH um hipergrafo e Gc o grafo ponderado associado a G 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 Sucessores e antecessores Seja x um vértice de D Um vértice y é sucessor antecessor de x se existe um arco em D tal que a simeq y a simeq x O conjunto dos sucessores antecessores de x é denotado por Rx Rx isto é Rx a a in x e Rx a a in x 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 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 subdivisão T de D é uma sarborescência de D se e se VT nenhum arco de E entra em s e T possui um único sxcaminho orientado para cada x VT um tal sxcaminho é denotado por Ts x Se além disso Ts x é um sxcaminho orientado de comprimento mínimo para cada x VT 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 V 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 visã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 distx a distância de s até x ou seja o comprimento de um sxcaminho orientado ℓmínimo Seja Vi x V distx i para cada i N Seja k N e suponha que X i 0 k Vi Vamos mostrar que Vk1 ΓVk X c Suponha que v Vk1 Então existe um sxcaminho 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 ΓVk X c Suponha agora que v ΓVk X c Como v é vértice de X c então distv k 1 Todavia v é também um sucessor de um vértice u Vk Logo existe u v Seja P um sucaminho de comprimento mínimo Então ℓP u k 1 onde distv k 1 Portanto distv k 1 e v Vk1 como queríamos Implementação Essas estruturas de dados para a representação de um digrafo Cada a Arc representa um arco de um digrafo a tail é a ponta inicial de a e a head é 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 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 R 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 0 e 1 e k u k um caminho orientado de D O custo de P é o número cP i 0k ce i 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 D c 0 para denotar um grafo ponderado Dc para o qual c 0 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 Teorema 31 Se D é um digrafo s t V e t está no território de s então o comprimento de um stcaminho orientado ℓmínimo é igual ao número máximo de stcortes dois a dois disjuntos isto é minℓP P P maxX K é uma parte disjunta de C onde P 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 e 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 stcaminho orientado Então K K implica que K AP Agora ℓP AP AP X k X AP X K K AP K k K X 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 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 K Um teorema mínimo Finalmente i0k yU i i0k distc i1 distc i distc k distcl 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 Dc é um dígrafo ponderado e conservativo e st são vértices de D Se p V R é um potencial e P é um stcaminho orientado então cP pt ps Suponha agora que Dc é conservativo Para cada par st V seja Pst o conjunto dos stcaminhos orientados de D Seja p V R 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 Pst 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 yzcaminho cada uma de cujas arestas e tem custo preduzido nãopositivo ie cpei 0 Seja K P y axe ponha ei1 a Observe que cpei 0 para cada i k e cpeₖ₁ 0 Mas 0 Σₖ₁ⁱ₁ cpei Σₖⁱ₁ cei pei peiₖ₁ cK e portanto K tem custo negativo Caso 2 x XY Note que se e XY então cpe 0 Tome ε minca a cₚ cpe e Xₚ e seja p V R tal que p pu ε se u X pu caso contrário para cada a V Observe que para arco e A se e X então cpe cpe se e XY então cpe ce pe pe ce pe ε pe cpe ε cpe onde a última desigualdade segue de ε cpe 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 que G é 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 duas a duas disjuntas Mais formalmente M E é um emparelhamento de G se e 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 duas arestas em M ou seja se x U M caso contrário dizemos que x é Mexposto ou exposto por M Dizemos também que uma parte S de V é Msaturada se M satura 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 de uma 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 é cobertura então toda aresta de M tem ao menos uma de suas pontas em C No entanto as arestas de M são disjuntas portanto C M Eis uma prova mais formal deste fato C C U M eM C e Σ eM C e Σ eM 1 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 e maxM M M 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 e eM C e eM 1 M donde toda desigualdade vale com igualdade Assim C C M onde C M o que estabelece ii Ademais C e 1 para cada e M e eM C e eM 1 M implicam que C e 1 para cada e M o que valida iii 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 DeCeren 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 y G 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 satura x Assim suponha que existe um emparelhamento máximo M que não satura x Vamos mostrar que x é 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 N assim M satura x 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 contém uma de suas pontas o vértice y seja z a outra ponta de P A maximalidade de M implica que P tem comprimento par Como G é bipartido então x z onde z y 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 Observe primeiro que γX γY X Y X Y ΓX Y X Y onde γY Y Consequentemente G satisfaz Hall em relação a S X onde por hipótese de indução G possui um emparelhamento M que satura S X Conclusões assim que M M é um emparelhamento de G que satura S como queríamos Prova do Algoritmo Húngaro Vamos provar que G não possui um emparelhamento que não satura S então existe X S tal que γX X Para nós suponha que G não possui um emparelhamento que satura S Observe que S Z T Z uma vez que todo vértice de TZ é ponta inicial da orientação de uma aresta de M RS e ΓS Z T Z Portanto γS Z T Z M como queríamos para cada X Y S Suponha que t T e tal que χRX Y t 1 ou χRX Y t 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 maxP P é uma coleção disjunta nos vértices de STcaminhos 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 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 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