Noções Básicas de Teoria dos Grafos

Sumário 1 Noções básicas 5 Mario Leston Teoria dos 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 1 de vértices isto é ι E V 2 Além disso V e E são conjuntos disjuntos ou seja V E Vamos ter alguns comentários sobre a notação que às vezes pode se tornar uma chacaregaçã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 VG 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 E E e ι em vez de suas versões mais longas O número de vértices de G VG é denotado mais simplesmente por G o número de arestas EG por G Para cada aresta e ιe é um objeto da forma u v em que u e v são vértices distintos de V Para menos na notação vamos adotar a seguinte convenção 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 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 8 TEORIA DOS GRAFOS u v1 v2 v3 Figura 13 A figura ilustra o vértice u com Γu v1 v2 v3 donde γu 3 5 Note que aqui mais uma vez estamos fazendo uso da convenção implícita agora não mais implícita de omitir o nome do grafo e os parênteses na nota ção convenção esta que permeará este texto sempre que não houver possibili dade de confusão 6 Uma função f X Y pode ser en carada como um conjunto de pares da forma x fx para cada x X f x fx x X Desta forma para funções f e g estamos autorizados a escrever f g uma vez que f e g são conjuntos Para uma função f X Y e uma parte Z de X fZ Z Y é a restrição de f aos elementos de Z fZ z fz z Z Exercício 11 Mostre que se G é um grafo e E V 1 então existe v V tal que dv 3 Vizinhança de um vértice Seja u um vértice de G Um vértice v de G é vizinho de u se uma das arestas de G tem pontas u e v Vamos coletar esses elementos em um conjunto denotado por ΓGu e chamálo de vizinhança ou de conjunto dos vizinhos de u Mais formalmente ΓGu v V e E e uv Reiterando para tornar a notação mais leve vamos escrever Γu sempre que possível e esteticamente agradável A função ΓG é cha mada de função de vizinhança de G O número de vizinhos de u denotado por γu é o tamanho ou a cardinalidade do conjunto Γu Assim γu Γu para cada u V 5 Convém observar que em geral γ d Subgrafos Sejam G e H grafos Dizemos que H é um subgrafo de G escrito H G se 6 VH VG EH EG e ιH ιG Em palavras um grafo H é subgrafo de um grafo G se as seguintes condições são satisfeitas todo vértice de H é vértice de G e se e é uma aresta de H com pontas x e y então e é uma aresta de G e suas pontas são também x e y Um subgrafo H de G é dito gerador se V H V G 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 fF f F μP ou seja é o grafo cujo conjunto dos vértices é constituído dos vértices que estão em alguma aresta de F e cujo conjunto das arestas é F Neste último caso costumase conveniente confundir o conjunto de arestas F com o grafo GF hábito este que será recorrente durante o texto sempre que não houver possibilidade de confusão 10 TEORIA DOS GRAFOS P Figura 14 A figura ilustra um caminho simples 8 Para um inteiro nãonegativo k k 1 2 k Além disso para inteiros ℓ k escreve mos ℓ k para denotar o conjunto i Z ℓ i k Observe que 0 9 Com frequência quando não houver possibilidade de confusão vamos escre ver v0vkcaminho 10 Ou ainda outras variantes linguísticas equivalentes 11 Note que ℓP é em geral diferente de EP salvo se P for uma trilha 12 Assim por exemplo vamos escrever v0v1 vk para destacar a sequência de vértices de um caminho de v0 até vk Pvi vj P1 P2 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érti ces e arestas de tal forma que as pontas de cada aresta na sequência são os vértices que imediatamente precedem e sucedem a aresta na sequên cia Formalmente um caminho é uma sequência digamos P v0e1v1 ekvk em que8 k 0 v0 vk V e1 ek E e ei vi1vi para cada i k Vamos escrever V P ou VP para denotar o conjunto dos vértices de P isto é v0 vk e EP ou EP para denotar o conjunto das ares tas de P isto é e1 ek Dizemos que P é um9 v0 vkcaminho ou um caminho de v0 até vk ou ainda um caminho que une v0 e vk10 e que v0 é o início ou a ponta inicial de P e vk é o término ou a ponta final de P O comprimento de P denotado por ℓP é o número k11 É conveni ente muitas vezes confundir um caminho P com o grafo VP EP ιEP Assim por exemplo se u VP então dP u é o grau de u no grafo P Com esta identificação podemos escrever P em vez de V P e P em vez de EP Às vezes vamos nos interessar tão somente pelos vértices de um caminho quando então vamos enumerar tão somente os vértices12 De forma similar quando o interesse residir somente nas arestas de um caminho vamos pois tão somente enumerar as arestas No primeiro caso dizemos que um tal 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 viei1vi1 ejvj que constitui um caminho que une os vértices vi e vj Caminhos são sequências finitas e estas podem ser concatenadas A concatenação dos caminhos P1 v0e1v1 ekvk e P2 w0f1w1 flwl tais que vk w0 denotada P1 P2 é o caminho v0e1v1 ekvkf1w1 flwl Trilhas e caminhos simples Dizemos que P é uma trilha se não repete arestas ou seja P k ℓP Dizemos que P é um caminho sim ples se não repete vértices ou seja P k 1 Naturalmente se P é um caminho simples então P é uma trilha mas evidentemente a re cíproca não é em geral verdadeira A mesma nomenclatura usada para NOÇÕES BÁSICAS 11 Figura 15 A figura ilustra um grafo que é um caminho simples Figura 16 A figura ilustra um grafo que é um ciclo 13 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 14 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 caminhos é estendida para trilhas e caminhos simples É conveniente como já fizemos anteriormente identificar uma trilha P com o grafo VP EP ιEP Exercício 13 Seja G um grafo e u v V Se P é um uvcaminho então existe um uvcaminho simples Q tal que VQ VP e EQ EP Circuitos e ciclos Uma trilha P é um circuito se ℓP 2 e o início e o fim de P coincidem Um ciclo é um circuito no qual exceto pelo início e pelo fim nenhum outro vértice se repete na sequência As sim o circuito v0e1v1 ekvk donde k 2 e v0 vk é um ciclo se v0e1 ek1vk1 é um caminho simples A cintura de um grafo G que 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 ι Exercício 14 Mostre que se um grafo possui um circuito de com primento ímpar então também possui um ciclo de comprimento ímpar 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 maximal13X 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 X14 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 12 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 12 TEORIA DOS GRAFOS 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 cG 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 12 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 G é uma partição de V O número de componentes conexas de um grafo G é denotado por cG 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 15 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 Proposição 1 Se G é um grafo conexo e e E então cG 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 cG e cG 1 Corolário 15 Se G é um grafo nãovazio então cG G G Prova Vamos provar por indução em G que se G é nãovazio então cG G G Suponha que G é um grafo nãovazio Se G 0 então cG G e não há mais nada a provar Suponha G 1 NOÇÕES BÁSICAS 13 X 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 Figura 110 A remoção das arestas de cor azul desconecta o grafo No entanto tais arestas não constituem um corte 15 Tal notação é uma abreviatura para as afirmações v0v1v2 vk é um caminho e x v0 e y vk Escolha uma aresta e E Por hipótese de indução cG e G e G e Segue daí que cG cG 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 Os conjuntos X e Xc são margens de X Uma parte K de E é um corte se K X para algum X V 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 É claro que todo caminho que leva de um vértice x X até um vértice y Xc usa uma aresta de X Logo se G é conexo e X então G X não é conexo Note entretanto que não é verdade que num grafo conexo G se G K não é conexo para algum K E então K é um corte Lema 13 Se X é o território de um vértice s em um grafo G então X Prova Suponha que X é o território de s e que x X Então existe um sxcaminho de vértices digamos P em G Admita que e x e seja y a ponta de e distinta de x Ora P xy é um sycaminho em G donde y X e portanto e X Concluímos assim que X Teorema 11 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 15 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 14 TEORIA DOS GRAFOS Suponha agora que X sempre que X V Seja X o território de x Pelo Lema 13 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 2 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 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 3 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 GX ou GXc não é co nexo então X não é um conjunto minimal de arestas que desco necta G Ajuste a notação de tal forma que H GX não é conexo NOÇÕES BÁSICAS 15 16 Isto quer dizer que não existe X V tal que X L bom 17 Verifique 18 Verifique F R Figura 111 A figura ilustra um par bom S F Se um vértice está em S F en tão todos os seus vizinhos estão em S Pelo Lema 11 existe Y1 X tal que HY1 Ponha Y2 XY1 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 Por tanto X não é um conjunto minimal de arestas que desconecta G Exercício 16 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 Um corte K E em um grafo G é minimal se L não é um corte para cada L K 16 O próximo lema caracteriza quando um corte é minimal em um grafo conexo Corolário 16 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 17 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 Algoritmo de busca O propósito agora é exibir um algoritmo que determina o território de um vértice de um grafo e consequentemente uma das componentes conexas de tal grafo Vamos admitir que um grafo G é dado pela sua função de vizinhança Γ Seja s um dos vértices de G A correção do algoritmo depende da seguinte noção Dizemos que um par S F é bom se s S e S é uma parte do território de s em G F S e Γx S para cada x S F Note que s s é um par bom Suponha que S F é bom Admita primeiro que F Neste caso Γx S para cada x V donde S Como S é uma parte do território de s e S então S é uma componente conexa de G Admita agora que F Seja x F Há duas possibilidades Se Γx R então R F x é também bom17 Se Γx R então selecione y Γx R e note que o par S y F y também é bom18 16 TEORIA DOS GRAFOS X Xc Figura 112 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 C Xc C X Cc X Cc Xc C e Figura 113 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 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 digrafo D é ímpar se o seu compri mento ℓC é ímpar O próximo teorema caracteriza grafos biparti dos Teorema 12 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 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 NOÇÕES BÁSICAS 17 Figura 114 A figura ilustra uma árvore 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 ℓ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 Á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 único caminho simples unindo dois vértices arbitrários de G De fato suponha que x y são vértices de G e que P1 e P2 são dois caminhos simples distintos unindo x e y Observe que neste caso ℓP1 1 e ℓP2 1 Escreva P1 v0v1 vk com k 1 e 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 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 18 TEORIA DOS GRAFOS 19 Justifique 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 existir exatamente um implica que o grafo é acíclico Portanto é 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 resul tado Teorema 13 Um grafo é uma árvore se e só se cada par de vértices é unido por exatamente um único caminho simples Corolário 17 Se T é uma árvore e e ET então T e não é conexo 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 T e não contém nenhum caminho de x até y donde T e não é conexo O seguinte exercício será útil para o próximo teorema Exercício 18 Se C é um ciclo e K é um corte de um grafo G então EC K mod 2 0 Teorema 14 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 17 implica que se T e não é conexo como queríamos 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 desconexidade de T e implicam que cT e 2 Sejam pois T1 e T2 as componentes conexas de T e Agora para cada i 1 2 e para cada aresta f ETi o grafo Ti f não é conexo19 Assim por hipótese de indução T1 e T2 são árvores o que por sua vez implica que T é uma árvore De fato suponha por um momento que C é um ciclo de T Como T1 e T2 são árvores então C não é um ciclo de T1 e nem de T2 Logo C deve usar a aresta e No entanto EC VT1 e o que contraria o exercício anterior Portanto T é uma árvore Há uma relação simples envolvendo o número de vértices e o nú mero de arestas de uma árvore Teorema 15 Um grafo T é uma árvore nãovazia se e só se T é conexo e E V 1 Prova Vamos provar por indução em T que se T é uma árvore nãovazia então T E1 Seja T uma árvore nãovazia Se T 1 então E 0 portanto T E 1 Suponha então que T 2 Como T tem pelo menos dois vértices e T é conexo então ET Selecione uma aresta e ET Ora o grafo T e não é conexo Pelo Lema 14 cT e 2 Cada uma das componentes de T e digamos T1 e T2 é acíclica pois T é acíclico Além disso tanto T1 quanto T2 são conexos Logo T1 e T2 são árvores e portanto por hipótese de indução T1 E1 T1 1 Agora T T1 T2 1 T1 1 T2 1 1 T 1 como queríamos Vamos provar por indução em T que se T é conexo e T 1 então T é uma árvore O resultado vale quando T 1 Suponha que T 1 Como T é conexo então δT 1 Vamos mostrar que se um grafo G é T e que δG 2 então G T De fato 2G vG dv 2G e portanto G G como queríamos Ora T T 1 logo pela também é conexo e T x T onde T x por hipótese de indução é uma árvore o que para vexe afirma que T é também uma árvore 20 TEORIA DOS GRAFOS 22 Uma vez que se t1 t2 VT então existe um caminho de T de t1 até t2 tal caminho é também um caminho de U 23 Poderíamos argumentar de uma forma menos construtiva A prova é por indu ção no número de ciclos de G Se G não possui ciclos então G é uma árvore gera dora e não há mais nada a provar Supo nha então que G possui ao menos um ciclo e seja e uma aresta em um de tais ciclos Você agora deve verificar que o grafo Ge é conexo donde por hipótese de indução possui uma árvore geradora T é claro que T é também uma árvore geradora de G Isto completa a prova r t1 t2 C1 C2 Figura 116 As arestas pretas são arestas de T as vermelhas de EG T T é uma árvore e T é um subgrafo gerador de G Observe que se T é uma árvore geradora de G então a conexidade T implica na conexidade de G Não é difícil intuir que todo grafo conexo possui uma árvore geradora Teorema 16 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 ge radora então G é conexo Vamos então provar a recíproca Suponha que G é conexo Admita que X V é 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 e considere o subgrafo U GET e Seja x a ponta de e em X e y a ponta de e em Xc Vamos mostrar que U é uma ár vore geradora de GX y Ora U é um grafo conexo Para verificar isso basta provar22 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 donde P xey é um caminho de t até y em U Logo U é conexo Além disso U é acíclico uma vez que T é acíclico e dUy 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íamos23 Árvores de busca em profundidade Seja T uma árvore nãovazia e r um de seus vértices Como de cos tume para simplificar vamos confundir uma árvore com o seu con junto de arestas Podemos definir uma ordem parcial sobre os vértices de T da seguinte forma Para cada x y VT dizemos que x e y são comparáveis em T r se x V Tr y ou seja se x está no caminho de r até y em T ou y V Tr x ou seja se y está no caminho de r até x em T Seja T uma árvore geradora de um grafo G e r 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 xy E T Teorema 17 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 G é um grafo co nexo e r V Se G 1 então G é uma árvore de busca em profundi dade 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 ti um vizinho de r em Ci e uma aresta com pontos r e ti Por hipótese de indução existe uma árvore de busca em profundidade Ti de GCi com raiz ti para cada i k É claro que T ti i k ik Ti é 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 EC T Então i ou ambas as pontas de e digamos x e y estão em Ci para algum i onde x e y são comparáveis em Ti r 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 são uma transversal do conjunto X X X y Xc Note no enunciado do próximo teorema a identificação de um conjunto de arestas com o grafo induzido por este conjunto de arestas Teorema 18 Seja G um grafo conexo e e X X V Uma parte T de E é uma árvore geradora de G se e só se T é uma transversal minimal de e Prova O resultado é claro se G 1 Logo vamos supor que G 2 Suponha que T é uma transversal minimal de e Vamos mostrar que T é um subgrafo conexo e gerador de G Para isso tomo X V Como T é uma transversal de e então T X mas T X TX onde pelo Lema 11 T é conexo Além disso a escolha de X como uma parte própria e nãovazia de V implica que T é gerador Logo T é um subgrafo gerador de G Seja e uma aresta de T Como T é uma transversal minimal de e então T e não é uma transversal Logo existe X V tal que TeX dono T e não é conexo Conclusões assim que T é conexo e T e não é conexo para cada e T o que de acordo com o Teorema 14 implica que T é uma árvore Exercício 112 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 X X V x X y Xc e e só se P é simples Grafo simples Um grafo G é simples se para cada e f E se e f então ie if ou seja não existem duas arestas com as mesmas pontas Neste caso por simplicidade convém dispensar a função de incidência e considerar um grafo simples como um par V E tal que V é como de costume um conjunto finito e E V 2 Assim cada aresta é um par nãoordenado de vértices distintos Cliques e conjuntos independentes Seja G um grafo e X V Dizemos que X é um kclique se GX é completo ou seja se para cada x1 x2 X se x1 x2 então existe e E tal que e x1x2 Para cada k ℕ uma parte X de V é um kclique se X k Um 3clique é também chamado de triângulo Dizemos que uma parte X de V é um conjunto independente se EGX ou seja se não existe aresta de G com ambas as pontas em X Por outro lado dizemos que um conjunto C de vértices de G é uma cobertura de vértices se toda aresta de G tem ao menos uma de suas pontas em C Assim se X é independente então toda aresta de G tem ou as duas pontas em Xc ou exatamente uma ponta em Xc e portanto Xc é uma cobertura de vértices Usualmente escrevemos K n para denotar um grafo simples e completo com n vértices Teorema 19 Mantel Se G é um grafo simples livre de triângulos então G G24 Primeira prova O resultado é óbvio se n 1 Assim vamos supor que n 2 É evidente que existe a e 0 n tal que an a maxkn k k 0 n É fácil ver que n 2 implica 0 a n Note que a 1n a 1 an n a2 1 2a an a2 2a n 1 onde que n 1 2 n2 n2 Além disso a 1n a 1 an a 2a n 1 onde an 1 2 n2 Logo a n2 ou a n2 n2 Como queríamos Suponha que G é um grafo simples livre de triângulos Seja v um vértice de grau mínimo de G digamos k Como G é livre de triângulos então G G2 G24 O resultado segue imediatamente se G 2 em virtude da ausência de grafos com não mais que dois vértices satisfazendo a hipótese do teorema Suponha então que G 3 É claro que neste caso E Seja então uma aresta de G e G G x y Temos dois casos Caso 1 G G24 Por hipótese de indução G tem um triângulo e tal triângulo é também um triângulo de G pois G é subgrafo de G Caso 2 Seja n G Note que G G n24 n 224 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 onde pelo Princípio da Casa de Pombos existe z V x y tal que z Γx Γy Portanto x y z é um triângulo Lema 15 Se G é um grafo simples e δG 2 então G possui ciclo Prova Seja P x0x1 xk um caminho maximal de G Como δG 2 vem que ux0 2 ou seja x0 possui um vizinho distinto de x1 Além disso todo vizinho de x0 está em P caso contrário poderíamos extender P contrariando assim a maximalidade de P Portanto existe i tal que 2 i k e xi é vizinho de x0 Agora x0x1 xix0 é um ciclo de G NOÇÕES BÁSICAS 25 25 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 26 Lembrese que a cintura de um grafo que contém ciclos é o comprimento de um menor ciclo Lema 16 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 15 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 4 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ínimo25 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 Agora mostraremos26 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 16 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 26 TEORIA DOS GRAFOS x y z y z Figura 118 A figura ilustra a operação envolvida na construção de H quando dx 2 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 113 Mostre que se G é um grafo simples e G possui k componentes conexos então G G k 1G k 2