G20paGrafos - Uma introdu c aoSamuel JurkiewiczSobre o autor.Samuel Jurkiewicz carioca e Doutor em Matemtica pelaUniversidade Pierre et Marie, emParis. Atualmenteprofessor daEscoladeEngenharia da UFRJ.J atuou como docente em todos os nveis, inclusive no prescolar. Alm do ensino de graduao e ps-graduao, tem desenvolvido atividades junto a professores e alunos do Ensino Mdio atravs de oficinas de Matemtica Discreta.G20paSum ario1 Introdu c ao 12 O que e um grafo ? 52.1 Primeiras noc oes . . . . . . . . . . . . . . . . . . . . . . . 52.2 Grau de um v ertice . . . . . . . . . . . . . . . . . . . . . . 72.3 Nosso primeiro resultado . . . . . . . . . . . . . . . . . . 92.4 Alguns problemas com as denic oes . . . . . . . . . . . . 92.5 Isomorsmo . . . . . . . . . . . . . . . . . . . . . . . . . . 112.6 Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.7 Outras denic oes . . . . . . . . . . . . . . . . . . . . . . . 142.8 Tipos especiais de grafos . . . . . . . . . . . . . . . . . . . 152.9 Exerccio . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152.10Representac ao por matrizes . . . . . . . . . . . . . . . . . 202.11Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 Ciclos e caminhos 253.1 Conexidade outra vez . . . . . . . . . . . . . . . . . . . . 253.2 O problema do menor caminho . . . . . . . . . . . . . . . 273.3 Qual o menor caminho at e a Escola ?. . . . . . . . . . . . 284 Mais ciclos e mais caminhos 394.1 Euler e as pontes de K oenisberg. . . . . . . . . . . . . . . 394.2 Esse problema e importante ? . . . . . . . . . . . . . . . . 404.3 Estrutura de dados . . . . . . . . . . . . . . . . . . . . . . 41iG20paii SUM ARIO4.4 Grafos eulerianos . . . . . . . . . . . . . . . . . . . . . . . 444.5 O problema chin es do carteiro. . . . . . . . . . . . . . . . 484.6 Grafos e ciclos hamiltonianos . . . . . . . . . . . . . . . . 484.7 O problema do caixeiro viajante- PCV . . . . . . . . . . . 504.8 Uma palavra sobre complexidade . . . . . . . . . . . . . . 524.9 Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . 535Arvores 575.1 Denic oes e caracterizac oes . . . . . . . . . . . . . . . . . 575.2Arvores geradoras . . . . . . . . . . . . . . . . . . . . . . 595.3 Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . 616 Subconjuntos especiais de um grafo 636.1 Conjuntos independentes . . . . . . . . . . . . . . . . . . 636.2 Colorac ao . . . . . . . . . . . . . . . . . . . . . . . . . . . 646.3 Cliques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 656.4 Acoplamentos . . . . . . . . . . . . . . . . . . . . . . . . . 656.5 Acoplamentos em grafos bipartidos . . . . . . . . . . . . 676.6 Outros subconjuntos . . . . . . . . . . . . . . . . . . . . . 676.7 Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . 687 Grafos planares 717.1 Denic oes e resultados simples . . . . . . . . . . . . . . . 717.2 Teorema de Kuratowski . . . . . . . . . . . . . . . . . . . 747.3 Dualidade . . . . . . . . . . . . . . . . . . . . . . . . . . . 757.4 O problema das 4 cores. . . . . . . . . . . . . . . . . . . . 767.5 Exerccios . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77Indice 83G20paCaptulo 1Introdu c aoOleitor seriacapazdedesenharagura1.1 abaixosemtirarol apisdo papel ? Temque ir de ponto a ponto e n ao pode passar pela mesmalinha duas vezes.ABCDEFigura 1.1: O problema da casinha1G20pa2 CAPITULO 1. INTRODUCAOFoi f acil ? Experimente agora comecar pelo ponto B.Bem, esseproblema eimportante? Pensemosnumapequenaci-dade, compequenoorcamento. Oservicoderecolhimentodelixo efeito por umpequeno caminh ao. Queremos evitar o desperdcio; umaboa id eia seria fazer o caminh ao passar uma unica vez por cada rua eretornar ao ponto de partida. Na verdade, e o mesmo problema.Um outro problema que propomos ` as criancas para que se aquietem e o seguinte:temos que ligar Luz, G as e Telefone a tr es casas semqueas linhas se cruzem. Voc e j a tentou ? (veja a gura 1.2)casa 1casa 2casa 3LGTFigura 1.2: O problema das 3 casasOutravez, cabeapegunta: esseproblema eimportante? Pensemosent ao numa f abrica de placas de circuito integrado. Encontar esquemasde ligac ao que evitemcruzamento e crucial para baratear os custos demanufatura; quanto menos camadas, mais r apido e rent avel se torna oservico.Nos dois casos s o nos interessou considerar um conjunto de pontose um conjunto de ligac oes entre eles.E a essa estrutura que chamamosgrafo.Estas notas tratam da Teoria dos Grafos - uma modesta introduc ao.Desdeos eculoXVIII at enossos diasessateoriatemconhecidoex-traordin ariodesenvolvimentote oricoeaplicado. Adotamosent aoaG20pa3pr aticadeintroduzir algunstemasgeraisquedessemumapequenaid eiadavariedade de abordagens e problemas que elapode oferecer.Certamente, muitocouparadepois. Oqueesperamos equeao-nal o leitor tenha se convencido da utilidade dos conceitos e processosapresentados, mas guardamos o secreto desejo de que o aspecto l udicodos grafos o contaminem com o que costumamos chamar de graphicaldesease, ou melhor traduzindo, a febre dos grafos.Umaobservac ao: sendoumaprimeiraabordagemdateoriadosgrafos, tratamos apenas de grafos semorientac ao. Aintenc ao foiapresentarosconceitosdaformamaissimplicadapossvel. Paraoleitor interessado, a bibliograa contempla grafos com orientac ao.Cada captulo e acompanhado de exerccios, semasoluc ao; prefe-rimos deixaroprazer desta tarefa ao leitor. Abibliograaaomdasnotas e mais do que suciente para umconhecimento razo avel de teo-ria dos grafos, e inclui trabalhos de nvel diversicado.Enm, deve haver erros; as crticas (construtivas, por favor) s ao bemvindas.Esperamos que apreciem estas notas.Samuel JurkiewiczEscola de Engenharia/ UFRJ - Departamento de Engenharia Indus-trialCOPPE/ UFRJ - Programa de Engenharia de Produc aojurki@pep.ufrj.brG20pa4 CAPITULO 1. INTRODUCAOG20paCaptulo 2O que e um grafo ?2.1 Primeiras no c oesNuma escola algumas turmas resolveram realizar umtorneio de v olei.Participam do torneio as turmas 6A, 6B, 7A, 7B, 8A e 8B. Alguns jogosforam realizados at e agora:6A jogoucom 7A, 7B, 8B6B jogoucom 7A, 8A, 8B7A jogoucom 6A, 6B7B jogoucom 6A, 8A, 8B8A jogoucom 6B, 7B, 8B8B jogoucom 6A, 6B, 7B, 8AMas ser aque istoest acorreto ? Pode terhavido umerro nalista-gem. Uma maneira de representar a situac ao atrav es de uma gura asturmas ser ao representadas por pontos e os jogos ser ao representadospor linhas.N ao e difcil agora constatar a consist enciadas informac oes. A es-trutura que acabamos de conhecer e um grafo. Apresentamos duas for-mas de representar esta estruturaPor uma lista, dizendo quem se relaciona com quem.5G20pa6 CAPITULO 2. O QUEE UM GRAFO ?6A6B7A7B8A8BFigura 2.1: Grafo do Campeonato de V oleiPor um desenho, isto e, uma representac ao gr aca.Qual e a forma correta? As duas s ao corretas. Aestruturagrafoadmite v ariasmaneirasdeser representada. Isson ao enovi-dade: apalvradoiseosmbolo2representamomesmoconceitomatem atico.Para que um grafo que bem denido temos que ter dois conjuntos:OconjuntoV , dosv ertices- nonossoexemplo, oconjuntodasturmas.O conjunto A, das arestas - no nosso exemplo, os jogos realizados.Em outra palavras, o que nos interessa num grafo e:Quem s ao os v ertices.Que pares de v ertices est ao ligados e quais n ao est ao (isto e, quems ao as arestas).Quando existe uma aresta ligando dois v ertices dizemos que os v erticess ao adjacentes e que a aresta e incidente aos v ertices. No nosso exem-plo podemos representar o grafo de forma sucinta como:V= 6A; 6B; 7A; 7B; 8A; 8BG20pa2.2. GRAU DE UM V ERTICE 7A = (6A; 7A); (6A; 7B); (6A; 8B); (6B; 7A); (6B; 8A); (6B; 8B); (7B; 8A);(7B; 8B); (8A; 8B)Observe que n ao precisamos colocar (8A; 7B) no conjunto de arestaspois j a tnhamos colocado (7B; 8A).O n umero de v ertices ser a simbolizado por [V [ ou pela letra n.O n umero de arestas ser a simbolizado por [A[ ou pela letra m.No nosso exemplo n = 6 e m = 9.2.2 Grau de um v erticeNo nosso exemplo vimos que cada turma jogouumn umero diferentede jogos:6A jogou 3 jogos6B jogou 3 jogos7A jogou 2 jogos7B jogou 3 jogos8A jogou 3 jogos8B jogou 4 jogosPor isso, no nosso desenho, o v ertice 6A tem 3 arestas ligadas a ele,o v ertice A7 tem 2 arestas ligadas a ele e assim por diante.Dizemos queestasarestass aoincidentesaov ertice. On umerodevezes que as arestas incidemsobreov ertice v e chamadograudov erticev, simbolizadopor d(v). Nonossoexemplo, d(6A) =3;d(7A) = 2.Exerc cio:1. Usando o grafo do campeonato:(a) D e o grau de cada um dos v ertices(b) Qual a soma de todos os graus ?(c) Qual o n umero de arestas ?(d) O que voc e observou ? Ser a coincid encia ?2. Faca o mesmo exerccio anterior usando os grafos da gura 2.2:G20pa8 CAPITULO 2. O QUEE UM GRAFO ? Figura 2.2:G20pa2.3. NOSSO PRIMEIRO RESULTADO 92.3 Nosso primeiro resultadoNo exerccio anterior voce deve ter observado que a soma dos graus deumgrafo e sempre o dobro do n umero de arestas (e isso n ao deve sercoincid encia...). Isso pode ser escrito em linguagem matem atica.Para isso, denotaremos um grafo pela letra G e representaremos porV (G) e A(G), respectivamente, os conjuntos de v ertices e das arestas deG.Teorema: Para todo grafo G

vV (G)d(v) = 2mIsto e: A soma dos graus dos v ertices de um grafo e sempre o dobrodo n umero de arestas.Demonstra c ao: Quandocontamososgraus dosv erticesestamoscontando as extremidades das arestas uma vez. Como cada aresta temduas extremidades, cada aresta foi contada duas vezes.Corol ario: Todo grafo Gpossui um n umero par de v ertices de graumpar.Demonstra c ao: Setiv essemosumn umerompar dev erticesdegraumparasomados graus seria mpar. Mas asomados graus e odobro do n umero de arestas e, portanto, e um n umero par.2.4 Alguns problemas com as deni c oesAlgumas perguntas acerca das denic oes podem nos deixar atrapalha-dos. Vamos examinar algumas.Uma aresta pode ligar um v ertice a ele mesmo ?Pode; e oquechamamosde la co(veja gura2.3). Porexemplo,vamos construir o grafo emqueV= 2, 3, 4, 5, 6 e dois v erticesser ao ligados quando tiverem um divisor comum (diferente de 1).Pela denic ao do grafo vemos que o 5 n ao est a ligado a nenhumoutro v ertice mas tem um laco (como ali as todos os outros v erticesG20pa10 CAPITULO 2. O QUEE UM GRAFO ?23456Figura 2.3: Grafo com lacosdeste grafo). Para haver coer encia com os resultados da sec ao an-terior, temos que contar o laco duas vezes (uma para cada extremi-dade) quando calcularmos o grau do v ertice. No nosso exemplo:d(2) = 4; d(3) = 3; d(4) = 4; d(5) = 2; d(6) = 5.e o teorema continua valendo.Dois v ertices podem estar ligados por mais de uma aresta ?Podem; nestecasousamosonomeespecialdemultigrafo(vejagura 2.4). Um exemplo que veremos adiante resulta no seguintegrafo:Figura 2.4: Multigrafo (com arestas m ultiplas)Grafossemlacosouarestasm ultiplass aochamadosdegrafossimples. Nestetextoestaremostrabalhandoquase semprecomgrafos simples.G20pa2.5. ISOMORFISMO 11A gura 2.5 mostra um grafo ou dois grafos ?Figura 2.5: Um grafo ou dois ?Depende da situac ao. Em princpio parecem dois grafos distintos,epodemosconsider a-losassim. Maspodemospensarqueessegrafo representa as ligac oes entre casas de uma cidade onde passaum rio (veja gura 2.6).Figura 2.6:Se as pontes foremdestrudas emumtemporal a cidade ainda eumas o, apenas foi desconectada. Ografo dagura 2.5 poderiaser o que chamamos de grafo desconexo. Essa e uma noc ao im-portanteevoltaremosaelaalgumasvezes. Cadaparteconexado grafo (no nosso exemplo o quadrado e o tri angulo) e cha-madade componente conexa do grafo. Dizemosqueumgrafo econexosequalquer pardepontos eligadoporaomenosumcaminho.2.5 IsomorsmoObserve o grafo mostrado na gura adiante.G20pa12 CAPITULO 2. O QUEE UM GRAFO ?6A6B7A7B8A8BFigura 2.7:Veriquequeasituac aorepresentada eexatamenteamesmadografoinicialdocampeonato. Apenasnessecasoprocuramosfazerodesenho de forma a n ao haver pontos comuns entre as arestas (fora dosv ertices, eclaro). Quandodoisgrafosrepresntamamesmasituac aodizemos que eles s ao grafos isomorfos.Esseconceito` asvezesgerapol emica.Eomesmografooun ao?Claramente as caractersticas de ume de outro s ao as mesmas (graus,n umero de arestas e outras que veremos mais tarde). E na verdade estan ao e uma quest ao realmente importante. O essencial e saber discernirquandodois grafos s aoisomorfos oun ao. Paraissovamos usarumadenic ao t ecnica.Dois grafos G1e G2s ao ditos isomorfos se existe uma corres-pond encia1-a-1 entreseusconjuntosdev erticesquepreserveasad-jac encias.Vejamos um exemplo:abcdwxyzFigura 2.8:G20pa2.6. EXERCICIOS 13Vamos estabelecer uma correspond encia 1 1 entre os conjuntos dev ertices:f: a wb xc zd yEstafunc aofuncionaperfeitamente. Setomarmosumaarestanoprimeirografo(digamos(a; d))afunc aofar aacorrespond enciacom(w; y) que e umaaresta nosegundografo. Se tomarmos dois v erticesque n ao s ao ligados por uma aresta (digamosa ec) a func ao far a cor-responder dois v ertices (w e z) que tamb em n ao s ao ligados.2.6 Exerc cios1. Verique que a correspond encia a seguir n ao serve para mos-trar o isomorsmo. Sugest ao: Tome dois v ertices que n ao sejamligados, faca a correspond encia e veja o que acontece.f: a xb yc zd w2. Mostre que os pares de grafos abaixo s ao isomorfos:vFigura 2.9:3. Mostre que os grafos abaixo n ao s ao isomorfos:G20pa14 CAPITULO 2. O QUEE UM GRAFO ?Figura 2.10:Figura 2.11:2.7 Outras deni c oesO conjunto de v ertices adjacentes av e chamado vizinhan ca aberta dev, notado porN(v); a vizinhan ca fechada de v e notada e denida porN[v] =N(v) v. Podemosestenderestadenic aoparaconjuntosde v ertices (N(S)eN[S]). Por exemplo, no grafo do campeonato temosN(7B) = 6A; 8A; 8B e N[7B] = 6A; 7B; 8A; 8BUm v ertice de grau 0 e dito isolado; um v ertice de grau 1 e dito pen-dente; a seq u encia de graus de umgrafo e a seq u encian ao crescenteformada pelos graus dos v ertices dos grafos. Por exemplo, a seq u enciade graus do grafo do campeonato e (4, 3, 3, 3, 3, 2).O menor grau de um v ertice emG e o grau m nimo, denotado (G),e o maior e o graum aximo, denotado (G). No caso do campeonatotemos (G) = 4 e (G) = 2.G

editoumsubgrafodeGseV (G

) V (G)eA(G

) A(G).Figura 2.12:G20pa2.8. TIPOS ESPECIAIS DE GRAFOS 15Na gura a seguir, o grafoG

e umsubgrafo deG. OgrafoG e ditoumsubgrafo induzido pelo subconjunto(a,b,c,d) deV (G), pois todasasarestasincidentesaosv erticesdea,b,c,demG est aopresentesemG(veja a gura 2.13).dabcedabcedabceGGGFigura 2.13:2.8 Tipos especiais de grafosGrafo completoImagineografodocampeonatoquandotodososjogostiveremsido jogados. Ele caria com o aspecto da 2.14:Isto e o que chamamos um grafo completo. Um grafo completo edenido como sendo um grafo onde todo par de v ertices e ligadoporumaaresta. Umgrafocompletocomn v ertices e denotadoporKn (no nosso exemplo e K6).Veja um exemplo na gura 2.14.2.9 Exerc cio1. Quantas arestas temK7 ? e K12 ? e Kn ?2. Quantos v ertices um grafo simples precisa ter para poder ter200 arestas ?G20pa16 CAPITULO 2. O QUEE UM GRAFO ?6A6B7A7B8A8BFigura 2.14: O grafo completo K6Grafo complementar(veja gura 2.15)Imagine agora que temos o grafo do campeonato e queremos fa-zer o grafo dos jogos que faltam. Faramos um grafo com o mesmoconjunto de v ertices mas comas arestas que faltamno grafo ori-ginal. Veja a gura.6A6B7A7B8A8B6A6B7A7B8A8BFigura 2.15: Dois grafos complementaresChamamos este grafo de grafo complementardo grafoG, deno-tado por G.E f acil perceber que V (G) = V (G) e que A(G) A(G)inclui todas as arestas de G.G20pa2.9. EXERCICIO 17Grafo nulo ou vazio(gura 2.16) -E o grafo cujo conjunto de ares-tas A(G) e o conjunto vazio.Por exemplo, antes de comecar o campeonato nenhum jogo haviasido jogado. Nosso grafo caria como na gura.6A6B7A7B8A8BFigura 2.16: Grafo nulo ou vazioGrafo regular(gura 2.17)Um grafo e regular (de grauk, ou ainda k-regular) quando todosos seus v ertices t em o mesmo grau (k).Figura 2.17: Um grafo regular de grau 3Ciclo(gura 2.18)Um ciclo e um grafo conexo regular de grau 2. A notac ao e CnCaminho(gura 2.19)Umcaminho eumciclodoqual retiramos umaaresta. Ocom-primentodo caminho e dado pelo n umerode arestas (o que fazG20pa18 CAPITULO 2. O QUEE UM GRAFO ?Figura 2.18: Exemplos de ciclo: C5 e C6sentido: e o n umero de passos que gastamos para percorrer ocaminho). Assimo caminhoPn e obtido retirando uma aresta dociclo Cn+1.Figura 2.19: Exemplos de caminho: P4 e P5Arvores(gura 2.20)Uma arvore e umgrafo conexo semciclos como subgrafos. Noteque o fato de n aoter ciclos faz comque a arvore sejaamaneiramaisecon omicadeconectar osv ertices. As arvoresformamuma famlia importante de grafos e voltaremos a elas mais tarde.Grafos bipartidos(gura 2.21)E um grafo em que o conjunto Vde v ertices pode ser particionadoemdois subconjuntosdisjuntosV1eV2tal que toda aresta deGtemuma extremidade emV1 e outra emV2. OsubconjuntoV1 edito um subconjunto independente de v ertices do grafoG poisn ao h a arestas ligando dois v ertices de V1. Temos tamb em que V2 e um subconjunto independente de v ertices de G.Grafos bipartidos completos - Nota c aoKp,q(gura2.22)E umgrafo bipartido em que todos os v ertices de V1 s ao ligados a todosos v ertices de V2.G20pa2.9. EXERCICIO 19Figura 2.20: Exemplos de arvoresFigura 2.21: Grafo bipartidoFigura 2.22: Grafo bipartido completo K2,4G20pa20 CAPITULO 2. O QUEE UM GRAFO ?2.10 Representa c ao por matrizesMatrizes e umassunto tpico do ensino m edio mas o que mostraremosaqui podeserentendidoportodos. Umadsformasmaiscomunsdeinformar umaestruturade grafo para umcomputador e atrav es dematrizes. Umamatriznadamais edoqueumatabelacomlinhasecolunas. Um exemplo bastante conhecido e a tabuada: 0 1 2 3 4 5 6 7 8 90 0 0 0 0 0 0 0 0 0 01 0 1 2 3 4 5 6 7 8 92 0 2 4 6 8 10 12 14 16 183 0 3 6 9 12 15 18 21 24 274 0 4 8 12 16 20 24 28 32 365 0 5 10 15 20 25 30 35 40 456 0 6 12 18 24 30 36 42 48 547 0 7 14 21 28 35 42 49 56 638 0 8 16 24 32 40 48 56 64 729 0 9 18 27 36 45 54 63 72 81Se quisermos saber o valor de 3 5 procuramos o valor na linha do 3 ena coluna do 5, isto e 15.Mas as matrizes t emoutras utilidades. No caso dos grafos elas po-demser usadas na representac ao de v arias formas. Eis algumas delas.Exemplicaremos com as representac oes do grafo a seguir:ab cdFigura 2.23:Matriz de adjac encia - e a matriz denida porG20pa2.11. EXERCICIOS 21xij =

1 se ij A(G)0 se ij / A(G)No exemplo da gura 2.23, a matriz de adjac encia e:0 1 1 11 0 1 01 1 0 11 0 1 0Matriz de incid encia - e a matriz n m denida porxij =

1 se a aresta ej e incidente emvi0 caso contr arioNo exemplo da gura 2.23 a matriz de incid encia e:ab ac ad bc cda 1 1 1 0 0b 1 0 0 1 0c 0 1 0 1 1d 0 0 1 0 12.11 Exerc cios1. Qual o grafo complementar do grafo que temduas componentesconexas isomorfas a K3 e K7 ?2. Qual o grafo complementar do grafo que temduas componentesconexas isomorfas a Kr e Ks ?3. Mostre que umgrafo G e deconexo ent aoG temumsubgrafo bi-partido completo. Mostre que a recproca n ao e verdadeira.4. Mostre que as seq u encias (9, 8, 7, 6, 5, 5, 4, 3, 3) e (7, 7, 7, 6, 5, 4, 3,2) n ao correspondem` a seq u encias de graus de nenhum grafo.G20pa22 CAPITULO 2. O QUEE UM GRAFO ?5. mostre que aseq u encia(3, 3, 3, 3, 3, 3) corresponde adois grafosn ao isomorfos.6. Mostrequeumamesmaseq u enciapodecorresponder agrafosn ao isomorfos.7. Prove que 2.mn .8. Mostre que em um grafo bipartido m n24 .9. (a) Mostre que se G e conexo, ent ao m > n 1.(b) Mostre que a recproca n ao e verdadeira.(c) Qual o menor valor de m que garante que G e conexo ?10. Desenhe uma representac ao do grafo cuja matriz de adjac encia e:0 1 0 1 11 0 1 1 00 1 0 1 01 1 1 0 11 0 0 1 011. Umgrafo e auto-complementar seforisomorfoaoseucomple-mento. Mostre que seG e auto-complementar, ent aon=4k oun = 4.k + 1 para algumk inteiro.12. O grafo de linha ou grafo adjunto, notac ao L(G) , e o grafo cujosv ertices est ao em correspond encia 1 a 1 com as arestas de Ge cujasarestas ligamv ertices que correspondema arestas incidentes emG.(a) Mostre que L(K3) = L(K1,3).(b) Mostre que se G e regular de grauk, L(G) e regular de grau2.k 2.(c) Encontre uma express ao para o n umero de arestas deL(G)em func ao dos graus de G.G20pa2.11. EXERCICIOS 2313. Suponha que as arestas de K6 sejamcoloridas de azul oude ver-melho. Mostre que, seja qual for a forma de colorir, o grafo ter aum subgrafo isomorfo a K3 colorido com uma s o cor.Roteiro: Suponha, por absurdo que isso n ao e verdade.(a) Escolha um v ertice v qualquer; mostre que existem (pelo me-nos) 3 arestas incidentes a v com a mesma cor (digamos, semperda de generalidade: (v; a); (v; b); e (v; c) s ao coloridas deazul).(b) Mostre que (a; b); (a; c); e (b; c) n aopodemsercoloridas deazul.(c) Conclua que (a; b); (a; c); e (b; c) devem ser coloridas de ver-melho, mostrando o absurdo, e provando a armac ao.14. SuponhaqueasarestasdeK17sejamcoloridasdeazul, verdeoude vermelho. Mostre que, sejaqual foraformade colorir, ografo ter a umsubgrafo isomorfoaK3 colorido comuma s ocor.Sugest ao: Use o exerc cio anterior15. Mostrequenumgrafosimplespelomenosdoisv erticest emomesmo grau.G20pa24 CAPITULO 2. O QUEE UM GRAFO ?G20paCaptulo 3Ciclos e caminhos3.1 Conexidade outra vezObserva c ao: Quando n ao houver risco de confus ao a aresta (v, w) ser adenotada simplemente porvw.Um passeio e uma seq u encia de arestas do tipov0v1,v1v2,v2v3,...vs1vs; s e o comprimento do passeio. Se todasas arestas dopasseios aodistintas, opasseio e chamadotrilha; sev0=vsopasseio eumatrilha fechada. Se, al emdasarestas, todosos v ertices s ao distintos ent ao temos umcaminho, e sev0=vs temosumciclo(comovistoanteriormente). Umaoutraformadedenir aconexidade eobservarqueumgrafoG e conexosee s oseexiste umcaminho entre quaisquer dois v ertices deG. As componentes conexaspodem ser vistas como as classes de equival encia da relac ao:x y se e s o se existe um caminho ligando x a y.(Paraissoestamosconsiderandoqueentreumv erticeeelemesmo,existe um caminho de comprimento 0). O menor comprimento possvelpara um caminho entre os v ertices u e v e chamado de dist ancia entre ue v. Podemos tamb em sinalizar as sequ encias de arestas descritas acimapela sucess ao de v ertices v0,v1,v2,...,vs1,vs.25G20pa26 CAPITULO 3. CICLOS E CAMINHOSDizemosqueumgrafoconexo ek-conexose, aoretirarmosk 1v ertices do grafo, ele continua conexo. Por exemplo, o grafo da gura2.17 e 3 conexo, pois podemos escolher 2 v ertices quaisquer para retirar,e mesmo assim o grafo continuar a conexo.Teorema UmgrafoG ebipartidosees osen aocont emciclosdecomprimento mpar.Demonstra c ao: SejaG bipartido; se n ao houver ciclo emG, n aoh aoquemostrar. Seh aumcicloemG estealternav erticesdeV1eV2, dois subconjuntosindependentes e disjuntos. Partindo deV1 (porexemplo), pararetornaraopontode partidateremosqueutilizarumn umero par de arestas. O ciclo e, portanto, de comprimento par.Podemos considerar apenas grafos conexos. Seja Gum grafo semciclos mpares. Vamos particionar seu conjunto de v ertices em dois sub-conjuntosV1 e V2 independentes e disjuntos. Tomamos primeiramenteumv erticequalquer v; OsubconjuntoV1ser aformadopor todososv ertices w tais que exista um caminho de comprimento par entre v e w.O subconjuntoV2 ser a formado por todos os v erticesw tais que existaumcaminho de comprimento mpar entrev ew. Os conjuntosV1 eV2s ao disjuntos , pois sew estivesse emV1 eV2 ao mesmo tempo, have-riaumcaminhode comprimentopare umcaminhode comprimentompar ligando v a w. Esses dois caminhos podem se cruzar (ou n ao) an-tes de chegar emw, produzindo alguns ciclos ( veja a gura a seguir).Comoon umerodearestas usadonestesciclos e mpar( easomadon umero de arestas dos dois caminhos)issoproduziria pelomenos umciclo mpar emG, contrariando a hip otese.wzFigura 3.1:J a sabemos que o conjunto de v ertices de umgrafo bipartido e par-ticionadoemdoissubconjuntosV1eV2. OconjuntoV1(etamb emoconjuntoV2) e chamado conjunto independente, isto e, sew et foremambos v ertices de V1 eles n ao s ao adjacentes.Exerc cio: Nosparesdegrafosabaixo, mostrequaldosgrafos eG20pa3.2. O PROBLEMA DO MENOR CAMINHO 27bipartido e qual n ao e.Figura 3.2:Figura 3.3:3.2 O problema do menor caminhoAlgoritmos e computadoresNesta sec ao vamos tratar de umproblema relativamente simples. Porexemplo,algu emprecisasedeslocardeumacidadeparaoutra. Paraisso, eledisp oedev ariasestradas, quepassampordiversascidades.Qual caminho oferece uma trajet oria de menor comprimento?Oalgoritmo que solucionaeste problema (e at e hoje n ao se encon-trou formamelhor)foi criadopor Edsger WybeDijkstra, em1952.Dijkstranasceuem1930, nacidade de Roterdan- Holanda, e morreuem2002. Foi umcientistadecomputac aoerecebeuoTuringAwardde 1972 por suas contribuic oes fundamentais na area de linguagens deprogramac ao.Notemumfato interessante: geralmente o que estudamos emMa-tem atica foi criado h a muito tempo. Mas a Matem atica continua a ofe-recer soluc oes e com o desenvolvimento da Inform atica a id eia de umaG20pa28 CAPITULO 3. CICLOS E CAMINHOSsoluc ao para um problema tem se modicado. Em vez de procurarmosum n umero, uma resposta (o que em muitos casos e necess ario), procu-ramos um algoritmo, isto e, uma s erie de procedimentos que nos levem` a soluc ao. A vantagem e que, se oproblema formuitoextenso pode-remosprogramarumcomputador pararealizarestealgoritmo. Esseproblema e um excelente exemplo disso.Veremos mais tarde que isso n ao quer dizer que n ao precisamos deteoria, muitopelo contr ario. Umbomalgoritmo depende de boama-tem atica. Mas voltaremos aisso. Porenquantovamosverasoluc ao,simples e interessante oferecida por Dijkstra, que viveu no nosso tempo,ou dos nossos pais.Observe que trabalharemos comgrafos valorados , isto e, esta-mos atribuindo valores` as arestas. Esses valores podemser dist ancias,tempo gasto no trajeto, custo com a ligac ao, etc. Usaremos as express oescusto ou dist ancia para nos referirmos a estes valores. Esses valoresgeralmente s ao estimados por engenheiros, economistas e considerare-mos nos pr oximos exemplos que eles s ao dados. Esse algoritmo traba-lha apenas com grafos valorados com valores positivos e nossa tarefa eminimizar custoou dist ancia.3.3 Qual o menor caminho at e a Escola ?Lembremos que este grafo e valorado, isto e, atribumos valores ` as ares-tas. A dist ancia e diferente da que estamos acostumados. Por exem-plo, entre a Pracinha (P) e a Banca de Jornal (B) colocamos a dist ancia11 pois h a um cachorro que nos assusta. Entre a Quitanda (Q) e a Can-cela(C) adist ancia e4poish aumamoca(ourapaz) interessante.Usaremos este grafo simples e pequeno para vermos como o algoritmode Dijkstra funciona. Comecamos calculando todas as dist ancias a par-tir da Casa de Jo ao (J). A dist ancia de J at e J e 0 (zero).Vamos comecar com o mapa sem ligac oes.At eondepossochegarapartirdacasadeJo ao(J) emuma unicaetapa? Qual o custo? Vamos preencher a tabela abaixo.G20pa3.3. QUAL O MENOR CAMINHO AT E A ESCOLA ? 29ArmazemPracinhaBanca deJornalQuitandaCancelaEscolaCasa doJoo56103611648133 Figura 3.4:ArmazemPracinhaBanca deJornalQuitandaCancelaEscolaCasa doJoo088888 8Figura 3.5:G20pa30 CAPITULO 3. CICLOS E CAMINHOSDeterminado Posso chegar ...com custo ... vindo de...(fechado) at e.. ou dist ancia...* J - Casa de Jo ao 0 ***A - Armaz em Ainda n ao atingimosP - Pracinha Ainda n ao atingimosQ - Quitanda Ainda n ao atingimosB- Banca de Jornal Ainda n ao atingimosC - Cancela Ainda n ao atingimosE - Escola Ainda n ao atingimosAtenc ao: colocamos a dist ancia para dizer que ainda n ao atingi-mos este v erticeVamos entender a gura e a tabela; na gura escurecemos a Casade Jo ao, pois j a sabemos a menor dist ancia, 0. Os outros v ertices aindapodemser melhorados, por isso n ao est ao escurecidos, e a etiqueta mostra que ainda n ao foram atingidos.A partir da casa de Jo ao, quem podemos atingir imediatamente ? OArmazem, que est a a dist ancia 5 da Casa de Jo ao, a Pracinha que est aa dist ancia6 e aQuitanda, que est a adist ancia 10. Vouassinalar issono meugrafo. Mais ainda, euagora percebo que a dist ancia ao arma-zemn ao ir adiminuir. De fato, qualqueroutrocaminhoque eutome,j a comeca comumvalor maior que 5 (oueventualmente igual). Ent aoescureco o v ertice do armazem para mostrar que ele est a fechado.At e onde posso chegar a partir da casa de Jo ao (J) emuma unica etapa? Qual o custo? Vamos preencher a tabela abaixo.Determinado Posso chegar ...com custo ... vindo de...(fechado) at e.. ou dist ancia...* J - Casa de Jo ao 0 **** A - Armaz em 5 JP - Pracinha 6 JQ - Quitanda 10 JB- Banca de Jornal Ainda n ao atingimosC - Cancela Ainda n ao atingimosE - Escola Ainda n ao atingimosG20pa3.3. QUAL O MENOR CAMINHO AT E A ESCOLA ? 31ArmazemPracinhaBanca deJornalQuitandaCancelaEscolaCasa doJoo0106588 85610Figura 3.6:Como a dist ancia at e o armaz em n ao vai diminuir, e a nossa vez deinvestigarse indopelo caminhodoarmazempoderemos melhorarasdist ancias. A partir do Armazem s o podemos chegar ` a Banca de Jornais(B) (Lembre-se que J j a est a fechado). Nosso grafo e tabela camassime o pr oximo v ertice a ser fechado e a Pracinha (P). Note que a etiquetade dist ancia da Banca de Jornal passa a ser 18 = 5 + 13 (5 da etiquetado Armazemmais 13 da dist ancia Armazem-Banca de Jornais. Como18 < a melhor dist ancia at e a Banca e de 18.Nosso grafo e tabela cam assim e o pr oximo v ertice a ser fechado ea Pracinha (P).G20pa32 CAPITULO 3. CICLOS E CAMINHOSArmazemPracinhaBanca deJornalQuitandaCancelaEscolaCasa doJoo01065188 8561013Figura 3.7:Determinado Posso chegar ...com custo ... vindo de...(fechado) at e.. ou dist ancia...* J - Casa de Jo ao 0 **** A - Armaz em 5 JP - Pracinha 6 JQ - Quitanda 10 JB- Banca de Jornal 18 AC - Cancela Ainda n ao atingimosE - Escola Ainda n ao atingimosComo a dist ancia` a Pracinha n ao pode ser melhorada e a partir delaque investigaremos. Podemoschegar, passandopelaPracinha` aQui-tanda, ` a Banca de Jornal e ` a Cancela. Vamos ver o que acontece nos tr escasos:Quitanda: 6 (etiqueta da Pracinha) + 3 (dist ancia Pracinha-Quitanda) =9; como9 12. Ent ao n ao e vantagem, e continuo a ir para a Cancela passando pelaPracinha.O grafo e a tabela cam assim (observe que escurecemos o v ertice daCancela, que e o que tem menor dist ancia acumulada entre os abertos):Nosso grafo e tabela cam assim:ArmazemPracinhaBanca deJornalQuitandaCancelaEscolaCasa doJoo09651512 8563116Figura 3.9:G20pa3.3. QUAL O MENOR CAMINHO AT E A ESCOLA ? 35Determinado Posso chegar ...com custo ... vindo de...(fechado) at e.. ou dist ancia...* J - Casa de Jo ao 0 **** A - Armaz em 5 JP - Pracinha 6 JQ - Quitanda 9 PB- Banca de Jornal 15 QC - Cancela 12 PE - Escola Ainda n ao atingimosJ a estamos quase terminando. Da Cancela s o consigo ir ` a Escola comdist ancia acumulada 12 + 8 = 20 < .Minhatabela e grafo camassim(escurecemos ov ertice da Bancade Jornais):Nosso grafo e tabela cam assim:ArmazemPracinhaBanca deJornalQuitandaCancelaEscolaCasa doJoo09651512205631168Figura 3.10:G20pa36 CAPITULO 3. CICLOS E CAMINHOSDeterminado Posso chegar ...com custo ... vindo de...(fechado) at e.. ou dist ancia...* J - Casa de Jo ao 0 **** A - Armaz em 5 JP - Pracinha 6 JQ - Quitanda 9 PB- Banca de Jornal 17 QC - Cancela 12 PE - Escola 20 CE nalmente vemos que pela Banca de Jornal conseguimos chegar` aEscola com dist ancia acumulada de 15 + 3 < 20.O grafo e tabela nais cam:ArmazemPracinhaBanca deJornalQuitandaCancelaEscolaCasa doJoo0965151218563116 3Figura 3.11:G20pa3.3. QUAL O MENOR CAMINHO AT E A ESCOLA ? 37Determinado Posso chegar ...com custo ... vindo de...(fechado) at e.. ou dist ancia...* J - Casa de Jo ao 0 **** A - Armaz em 5 JP - Pracinha 6 JQ - Quitanda 9 PB- Banca de Jornal 17 QC - Cancela 12 PE - Escola 18 BObserve que:Ografonal euma arvore-conexaesemciclos(semprequecheg avamos numv ertice, elimin avamosumaaresta, impedindoa formac ao de ciclos.Oalgoritmo encontra o menor caminho da Casa de Jo ao a todosos outros pontos. Ele n ao encontra o menor caminho entre doisv erticesquaisquer. PorexemploparairdaCancela` aBancadeJornais a dist ancia e 11 e n ao 15 como a arvore sugere.Arepresentac aogr acafoi util paraentendermosoproblema,mas poderamos perfeitamente terusado apenas umamatrizdedist ancias:J A P Q B C EJ 0 5 6 10 A 5 0 13 P 6 0 3 11 6 Q 10 3 0 6 4 B 13 11 6 0 3C 6 4 0 8E 3 8 0Exerc cios:Nas guras abaixo use o algoritmo de Dijkstra para descobrir qualo menor caminho do v ertice A a todos os outros v ertices.G20pa38 CAPITULO 3. CICLOS E CAMINHOSNPM LJH IGEDCFBA701103170651006730126105743039 19261261140 85Figura 3.12:Abaixotemosumatabeladedist anciasentreumaMerceariaeaslocalidades ondeelafazentregas. UseoalgoritmodeDijks-tra para descobrir qual o menor caminho da Mercearia a todas asoutras localidades.Mercearia B C D E F G HMercearia 0 11 5 8 B 11 0 3 8 C 5 0 2 8 D 8 3 2 0 4 12 11E 8 4 0 15 4F 15 0 3 7G 8 12 3 0 2H 11 4 7 2 0G20paCaptulo 4Mais ciclos e maiscaminhos4.1 Euler e as pontes de K oenisbergNaintroduc aoperguntamossevoc econseguiriadesenhar acasinhaabaixo semtirar ol apis dopapel. Aguramostraumasoluc ao, e naverdade o problema e bastante f acil.ABCDEABCDEFigura 4.1:Massequisermoscomecar pelov erticeB? (voc epodetentar otempo que quiser).39G20pa40 CAPITULO 4. MAIS CICLOS E MAIS CAMINHOSOfato e que esse outroproblema e impossvel. Todasas soluc oescomecam/ terminampelov erticeA/E. SecomecamemAterminamemE, e vice-versa.Oproblema temorigemno famoso problema das pontes deK oenisberg, considerado o marco fundador da Teoria dos Grafos. Oshabitantes de K oenisberg (hoje Kaliningrado) se perguntavamse seriapossvel atravessar as sete pontes do Rio Prega, sem passar duas vezesnamesmaponte, retornandoaopontode partida. Oproblemae suamodelagem por grafos est a apresentada na gura a seguir.Figura 4.2:Observamos queoproblemad aorigemaumgrafocomarestasm ultiplas, oque n aoafetar a asoluc ao. LeonardEulermostrouquearespostaeranegativa, estabelecendoassimumacondic aonecess aria;emboraseacreditequeasuci encian aolhefossedesconhecida, so-mente muito mais tarde essa segunda parte foi publicada - por Hierhol-zer em 1873.Antes de prosseguir com a soluc ao vamos tecer algumasconsiderac oes sobre grafos, computadores e problemas nitos.4.2 Esse problema e importante ?Sim. Para comeco de conversa ele e interessante, simples de propor everemos que suasoluc ao e atraente, interessante e temconseq u enciasimportantes.G20pa4.3. ESTRUTURA DE DADOS 41Masnoaspectoimediato, pensenumapequenacidade, comum unico caminh ao para recolher o lixo; o prefeito deseja economizar o quesignica que prefere que o caminh ao passe uma unica vez por todas asruas e retorne ao ponto de partida.O problema e id entico ao problema da casinha e se a cidade tivesseessa congurac ao n ao teria soluc ao (pois o caminh ao n ao retornaria aoponto inicial (Voc e experimentou?). Se o mapa da cidade fosse comona gura a seguir, o prefeito caria contente (experimente !)ABCDEFFigura 4.3:E em que um computador pode nos ajudar nesse caso ?4.3 Estrutura de dadosO desenho ajuda a n os , pessoas, mas os computadores pre-ferem letras e n umeros. Lembre-se que a casinha representao grafo G em que V (G) = A, B, C, D, E e A(G) =(A; B); (A; D); (A; E); (B; C); (B; D); (B; E); (C; D); (D; E).Observe que usamos uma ordem semelhante ` a ordem do dicion ario;isso facilita encontrar a aresta que procuramos e isso vale para o com-putador tamb em.Bem, queremos saber se realmente todas as soluc oescomecam/ terminampor A/E. N ao haver a excess ao ? Como onossoproblematemumn umerodepossibilidadesnitoepequenopodemos examinar todas. Como um computador pode fazer isso ?G20pa42 CAPITULO 4. MAIS CICLOS E MAIS CAMINHOSCalma! N aoprecisamossaber programac aodecomputadores.Basta lembrar que computadores t em facilidade para tratar informac oesorganizadas. Como isso funciona no nosso caso ?Digamosqueachei asoluc aocodicadapelaseq u enciadeletrasAEBDCBADE. Mesmo sem o desenho podemos vericar que esta ede fato uma soluc ao. As arestas disponveis s ao:ABAD AE BC BD BE CD DEComecamos pela arestaAE. Ela est a disponvel ?Sim. Retiramos elada lista de disponveis:ABAD AE == BC BD BE CD DEApr oximaarestaaser examinada eEB. Est adisponvel? Sim.Retiramos ela da lista de disponveis:ABAD AE == BC BD BE == CD DERepare que no nosso problema EB e BE s ao a mesma coisa.E assim por diante. A seq u encia da vericac ao est a a abaixo:AEBDCBADE ABAD AE == BC BD BE CD DEAEBDCBADE ABAD AE == BC BD BE == CD DEAEBDCBADE ABAD AE == BC BD == BE == CD DEAEBDCBADE ABAD AE == BC BD == BE == CD == DEAEBDCBADE ABAD AE == BC == BD == BE == CD == DEAEBDCBADE AB == AD AE == BC == BD == BE == CD == DEAEBDCBADE AB == AD == AE == BC == BD == BE == CD == DEAEBDCBADE AB == AD == AE == BC == BD == BE == CD == DE ==E a vericac ao mostra que a soluc ao e boa.Observe que n ao usamos o desenho. E que foi fundamental amaneira como apresentamos os dados.E o que chamamos uma estru-tura de dados. Lembre-se, computadores s ao m aquinas e n ao podemospassarinformac oesdequalquerjeito. Aestruturadedados efunda-mental.N aotemosaintenc aoaqui deexplicitar ofuncionamentodeumcomputador, mas intuitivamente percebemos que com a estrutura ade-quada e umaseq u encia de procedimentos (umprograma !) isto e umG20pa4.3. ESTRUTURA DE DADOS 43algoritmo, podemos vericar se uma seq u encia de 9 letras (por qu e 9 ?) e ou n ao uma soluc ao.Vamos fazer algumas contas.Temos 8 arestas disponveis e po-demos numer a-las de 1a 8. Podemos pensar numprocedimento-queveriquese umadeterminadaseq u enciade 8 algarismosdotipo(1, 2, 3, 4, 5, 6, 7, 8) ou(3, 5, 6, 2, 8, 4, 7, 1) eoun aoumasoluc aoparaoproblema da casinha. Melhor ainda, podemos colocar essas seq u enciasem ordem de (1, 2, 3, 4, 5, 6, 7, 8) at e (8, 7, 6, 5, 4, 3, 2, 1).Quantas seq u encias temos ? Na apostila [2] vimos queteremos8! = 8 7 6 5 4 3 2 1 = 40320 seq u encias. S aoaspermutac oes de 8 elementos. Ora, umbomcomputador pode gerar evericar essas seq u encias todas emsegundos ! Poderemos ter certezade que todas as soluc oes realmente comecam (ou terminam) com a letraA ouE.Issosechamaumasolu c aopor for ca brutaen aousamosne-nhumasosticac aomatem atica, nehumteorema. Ser aomdaMa-tem atica ? N ao e bem assim...Lembre-se do prefeito. Digamos que a cidade dele n ao tenha 8 ruas,mas20. N ao eumagrandecidadeepodemostentar usar amesmaforca bruta do computador para resolver o problema de percorrer comocaminh aosemrepetic aode ruas. Setemos 20ruas, teremos 20!seq u encias. Quanto e isso ?20! = 2432902008176640000 seq u enciasS ao muitas seq u encias. Mas ser a que umbomcomputador n ao re-solveriaesteproblema? Seocomputadorvericasse ummilh aodeseq u encias por segundo (e poucos computadores o fazem hoje em dia)ele demoraria (os c alculos s o incluem a parte inteira):2432902008176640000 1000000 = 2432902008177 segundos2432902008177 60 = 40548366803 minutos40548366803 60 = 675806113 horas675806113 24 = 28158588 diasG20pa44 CAPITULO 4. MAIS CICLOS E MAIS CAMINHOS28158588 365 = 77147 anos77147 1000 = 77 mil eniosO prefeito n ao pode esperar tanto tempo (nemn os, nemningu em).Quem vir a nos socorrer ? Um teorema de Euler.4.4 Grafos eulerianosUm grafo commarestas e dito euleriano se existe uma trilha fechada decomprimentom emG; em outras palavras, se podemos percorrer cadaaresta uma e s o uma vez partindo de um v ertice e a ele retornando. Seo grafo n ao e euleriano mas temuma trilha aberta de comprimentom, e dito semi-euleriano.abcde abcde abcdeffG1G2G3Figura 4.4:Na gura acimaG1 e euleriano (a trilha pode ser a-b-c-d-e-f-a-d-b-e-a), G2 e semi-euleriano (a trilha pode se a-e-b-d-c-b-a-d-e) e G3 n ao eeuleriano nem semi-euleriano.J a vimos que o problema (e o nome euleriano) se originoucomoproblema das pontes de K oenisberg. Euler mostrouque a resposta eranegativa, estabelecendoassimumacondic aonecess aria. Comecamospor um lema simples por em necess ario.Lema: - Se todov ertice de umgrafo (gen erico)G temgraumaiorouigual a 2, G cont em um ciclo.Demonstra c ao - SeG cont emlacos ouarestas m ultiplas, n ao h a o queprovar, pois, automaticamente, Gcont emumciclo. Consideramos,portanto, apenas os grafos simples.`A partir de um v ertice v0 qualquerG20pa4.4. GRAFOS EULERIANOS 45iniciamos nossa trilha. Quando chegamos a umv ertice qualquer,ou oestamos visitandopelaprimeiravezepodemos continuar, ouchegamos a umv erticej a visitado, produzindoumciclo. Comoon umero de v ertices e nito, o lema est a provado.E agora, o teorema.Teorema de Euler - (Euler-1736) Umgrafo conexoG e euleriano see s o se todos os seus v ertices t em grau par.Demonstra c ao-Suponhamosque Gtenhaumatrilhafechadadecomprimentom. Cadavezqueatrilhapassapor umv erticeutilizaduas novas arestas, uma para entrar e umapara sair. Logo ograudecada v ertice deve ser obrigatoriamente par. Usaremos induc aosobreon umerodearestasm dografo. Porvacuidade, oteorema evalidoquandom=0. Suponhamosqueoteorema seja v alido para todos os grafos commenos do quem arestas.SendoG conexo, todososv erticest emgraumaior doque2, poisosgrauss aopares. Pelolemaanterior, Gcont emumciclo(que eumatrilha fechada). Dentretodos as trilhas fechadasemGescolhemosumatrilhaTcomcomprimentom aximo. SeTtemcomprimentom,o teorema est a provado. Caso contr ario, consideramos o grafo Hresultantedaretiradadasarestas deT. Comoretiramosumn umeropardearestas decadav erticedeT, etodososv erticesdografot emgraupar (pela hip otese), pelo menos uma das componentes deH temumv erticeemcomumcomTetemtodososv erticescomgraupar.Pelahip otesedeinduc ao, Htemumatrilhafechadaquepassaportodososv erticesdeH, epodemosformarumatrilhafechadamaiorconcatenando Tcom a trilha emH. Mas isso contraria a maximalidadena escolha de T.Corol ario - Umgrafo conexoG e semi-eulerianose, e somentese,tem no m aximo dois v ertices tem grau mpar.Demonstra c ao - Deixada ao leitor.Umalgoritmodecorrentedademonstrac aodoteoremaacimaas-seguraaconstruc aodeumatrilhafechadadecomprimentomnumgrafoeuleriano. Ademonstrac aodacorrec aodoalgoritmopodeserG20pa46 CAPITULO 4. MAIS CICLOS E MAIS CAMINHOSencontrada em [6]. Podemos dar uma id eia do funcionamento do algo-ritmo e do motivo pelo qual ele funciona. Veja a gura 4.5. Comecandonossatrilhapelov erticea poderamosfazer abfcedcbefa chegandoaumbecosemsada. Reparequeosgrauseramtodospareseareti-rada de um ciclo subtrai sempre numeros pares dos graus. O grafo res-tante tamb emtem v ertices comgrau par (Veja ainda a gura 4.5). Esseresto pode serpercorrido pela trilhafechadadghijkcjhd. Basta agoraincluiressatrilhanatrilhainicial, ondeest aov erticed. Nossatrilhaca abfced(dghijkcjhd)dcbefa(veja a gura 4.6).abcdefghijkdhijgcFigura 4.5:abcdefghijkFigura 4.6:Exerc cio : Na gura 4.7 Qual desses grafos e euleriano ? Quais s aosemi-eulerianos ? No caso de serem semi-eulerianos, por onde devemoscomecar(terminar) nossa trilha ?G20pa4.4. GRAFOS EULERIANOS 47 Figura 4.7:G20pa48 CAPITULO 4. MAIS CICLOS E MAIS CAMINHOS4.5 O problema chin es do carteiroEsseproblema eumaaplicac aobastanteimportantedoconceitodegrafo euleriano. Usamos um grafo valorado onde ` as arestas e associadoum peso, isto e, uma func aof: A '+. Este peso pode representarcomprimento, custo, tempo, ou o que a modelagem do problema exigir.J a vimos esse conceito no caso do algoritmo de Dijkstra.Oproblemachin es docarteiro(quetemestenome por ter sidoapresentado pelaprimeiravezporumpesquisadorchin ese n aopelanacionalidadedocarteiro...) consisteemminimizar oesforcodeumcarteiro que percorre todas as ruas de uma cidade. Ora, se o grafo emquest ao e euleriano, n ao h a problema. Mas se esse n ao for ocaso, te-remos que eulerizar ografo. Lembramos que o n umero de v ertices degraumpar e par (vejao corol ario nasec ao 2.3), logopoderemos unirpares desses v ertices por novas arestas, tornando-os pares.E claro quen ao construiremos novas ruas ! A id eia e fazer o carteiro percorrer ruasrepetidasdeformaecon omica. Oproblemapodesecomplicar bas-tantemash ahojealgoritmosqueproduzemresultadosaproximadoscombastanteeci encia.E umproblemabastanteestudadodevido` aeconomia que uma boa soluc ao pode gerar. Vamos ilustrar o caso maissimples possvel, quandoografo e semi-euleriano, isto e, temapenasdois v ertices de grau mpar.Omenorcaminho entre os v erticesa eb (calculado pelo algoritmode Dijkstra) indica que o melhormeio de eulerizar o grafo e construiruma aresta virtualentre a e b, o que signica simplesmente percorrero caminho av2, v2v3, v3v4, v4b como se fosse uma aresta. Assim gastare-mos menos a sola do carteiro.4.6 Grafos e ciclos hamiltonianosUmproblemaaparentementesimilar aodosgrafoseulerianos eodeprocurar emG umatrilhafechada que passasse portodos osv erticesuma e s o uma vez. Uma trilha assim teria de ser necessariamente um ci-clo (salvo no caso do grafo nulo com um v ertice); chamamos um tal ciclode ciclo hamiltoniano. Onome homenageiaSirWillianR. Hamilton,G20pa4.6. GRAFOS E CICLOS HAMILTONIANOS 49arestavirtual1253535343887210abv1v3v42v5v6v2Figura 4.8:queestudouedivulgouoproblema- emboraaprimeiraformulac aotenhasidofeitaporKirkmanem1885. Asprimeiras denic oesgrafohamiltoniano e de grafo semi-hamiltonianos seguemas mesmas dire-trizesdosgrafoseulerianos. Umgrafoeseuciclohamiltonianoapa-recemnagura4.9(a); umgrafon aohamiltonianoaparece nagura4.9(b).As semelhancas, entretanto, parampor aqui. O problema de saberse umgrafo e oun ao hamiltoniano e umdos mais estudados da teoriados grafos, por sua aplicabilidade em comunicac ao, transporte e plane-jamento. Entretanto, at e hoje, nenhuma condic ao necess aria e sucienteelegante foi encontrada. Naverdade, todososteoremas se encontrammuito longe de oferecer uma previs ao razo avel de soluc ao.G20pa50 CAPITULO 4. MAIS CICLOS E MAIS CAMINHOS(a)(b)Figura 4.9:4.7 O problema do caixeiro viajante- PCVO PCV e um dos problemas mais estudados no campo da pesquisa ope-racional mas at e hoje n ao foi encontrado um algoritmo computacional-menteecientepararesolv e-lo. Suaformulac ao esimples: dadoumgrafo completo valorado G desejamos determinar o valor do menor ci-clo hamiltoniano de G. Tomemos o exemplo seguinte, dado pela matrizvalorada de adjac encia. Comoo grafo emquest ao eK7, umasoluc ao obvia seria examinar todas as permutac oes entre os v ertices, cada umacorrespondendo a um ciclo hamiltoniano.Com7v ertices, teremos7! =5760permutac oes; naverdades ao6!=820 pois s ao permutac oes circulares. Seja como for, e uma tarefaat e modesta para um computador. Mas o PCV frequentemente trata degrafos commais de 60 v ertices. Issonos daria60!, o que nos tomarias eculos, mesmo usando todos os computadores do mundo !a b c d e f ga XXX 404 270 490 490 338 258b 404 XXX 618 890 890 460 320c 270 618 XXX 360 360 210 240d 490 890 360 XXX 78 390 330e 490 890 360 78 XXX 390 330f 338 460 210 390 390 XXX 270g 258 320 240 390 330 270 XXXG20pa4.7. O PROBLEMA DO CAIXEIRO VIAJANTE- PCV 51Nossa atitude ser a ent ao de procurar umalgoritmo heurstico, isto e, queusaumaid eiarazo avel, mesmoquen aoassegureamelhorsoluc ao, a soluc ao otima. A primeira tentativa e um algoritmo guloso,quepartedopontoAeprocurasempreamenor dist anciaaopontodavez. Nonossocaso, ocicloproduzidoseria a-g-c-f-g-b-d-e-a comvalor 2470. A contra-indicac ao para o algoritmo guloso e que no nalterminamospor aceitararestasdevaloresmuitoaltos. Observamos,entretanto, queestamos` aprocurade umciclo, en aotemosportantonescessidade de agirseq uencialmente; umaoutratentativaheursticaseria procurar agregar sempre a aresta de menor valor que n ao produzaciclocommenosde7 v erticesnemproduzav erticesdegrau3 (numciclo, todos os v ertices s ao de grau 2). As escolhas recaem sobre:Aresta ValorDE 78CF 210CG 240GA 258AC Bifurcac aoFG Bifurcac aoAF Fecha cicloCD Bifurcac aoCE Bifurcac aoDF 390BE 890AB 404Ociclo e a-c-d-e-f-g-b-a e o valor conseguido tamb em e 2470. Isso foicoincid encia, como veremos emoutros exemplos. A id eia parecia boa,e o resultado foi umpouco melhor. Entretanto, o melhor valor encon-trado, examinando todas as possibilidades, corresponde ao ciclo a-c-d-e-f-g-b-a com o valor, bem inferior, de 2092.E claro, se tivermos que examinar o PCV para 20 cidades teramosque examinar cerca de 20! permutac oes e j a vimos que este e um n umeromuito grande. Pior ainda, n ao foi descoberto ainda umalgoritmoe-ciente para este problema (como no caso euleriano, emque o teoremade Euler nos salvou). E ainda pior, os cientista da computac ao acredi-tam que ele pertenca uma classe de problemas para a qual n ao h a umaG20pa52 CAPITULO 4. MAIS CICLOS E MAIS CAMINHOSsoluc ao elegante. Vamos falar um pouco sobre isso adiante.Exerc cio : Nagura 4.10 temos umgrafo completo, valorado nasarestas, edesejamosencontrarociclohamiltonianocommenorvalortotal(Problema do Caixeiro Viajante). Para isso use os algoritmos gulo-sos descritos nesta sec ao e constate que o valor obtido e sempre maiordo que o melhor valor (que pode ser encontrado por exame exaustivo).AB CD1080507015020Figura 4.10:4.8 Uma palavra sobre complexidadeA an alise da complexidade de algoritmos e um assunto bastante t ecnicoe que foge` a intenc ao destas notas. Entretanto, as diculdades enfren-tadas por quemtrabalha comproblemas combinat orios (entre os quaisos da teoriados grafos) podemser informalmente compreendidas. J aviemos fazendo issoquando falamos de soluc oes elegantes, eci enciacomputacional, enm, sugerindoqualitativamentequecertosproble-mas t emsido mais resistentes a uma abordagem algortmica e compu-tacional do que outros.Um algoritmo e composto de passos elementares; se a totalidade dospassosexigidospor qualquer problemaqueessealgoritmoresolva edado por uma func ao polinomial do tamanho da entrada do algoritmo,umaumento de poder computacional pode reduzir signicativamenteo tempo utilizado.Entretanto, seatotalidadedospassosdoalgoritmo, nopior doscasos, eumafunc aoexponencial dotamanhodaentrada, oaumentodo poder computacional tempouco efeito sobre o tempo de execuc ao;G20pa4.9. EXERCICIOS 53bastaumpequenoincrementonaentradaparainutilizar oaumentocomputacional.Dos problemas que j a examinamos, o de pesquisa de menordist ancia (Dijkstra) e de complexidade polinomial assimcomo dadeterminac ao se umgrafo e oun ao euleriano ( e de sua exibic ao, casoseja o caso). Para o PCV, entretanto, at e hoje n ao foi descoberto um algo-ritmo polinomial; mais ainda, a maior parte dos pesquisadores acreditaque isso n ao ser a mesmo possvel.Maior informac ao sobre complexidade computacional pode ser en-contrada em Garey e Johnson[5].4.9 Exerc cios1. Uma ponte e uma aresta que, quando retirada, desconecta o grafo.Dado umgrafoG conexo, umv erticev ser a chamado de v erticePonteFigura 4.11:separador quandoasuaretirada resultarnumgrafo desconexo.Prove que um grafo s o tem uma ponte se tiver um v ertice separa-dor, mas a recproca n ao e verdadeira. A mesma id eia se estendeao conceito de conjunto separador.2. Prove que entre G e G, pelo menos um e conexo.3. Mostre que A2, o quadrado da matriz de adjac encia de um grafo,nos d a o n umero de caminhos de comprimento 2 entre cada par dev ertices de umgrafo. Que n umero aparece na diagonal principalde A2? Qual o signicado da matriz Ak? (Teorema de Festinger).G20pa54 CAPITULO 4. MAIS CICLOS E MAIS CAMINHOS4. Mostre que se umgrafo tem2.k v ertices de graumpar seucon-junto de arestas pode ser paricionado emk caminhos disjuntos.5. Para que valores de n, p e q os grafos Kn, Kp,qePns ao eulerianos ? semi-eulerianos ? hamiltonianos ?semi-hamiltonianos ?6. Mostre que Ki,j e hamiltoniano se e s o se i = j; e que nesse caso,existem i2| cicloshamiltonianosdisjuntos. Obs: x| eomaiorn umero inteiro menor ouigual ax; por exemplo 57| = 0, 413 | =13 e 62| = 3.7. Seja o grafoQj= (Xj, Uj) no qualXj= vetores dej coordena-das, cada uma igual a 0 ou 1 e Uj = (vj, wj)[vj difere de wj poruma s o coordenada . A gura 4.12 mostra Q1, Q2 e Q3.(0) (1)(0,0)(1,0) (1,1)(0,1) (0,0,0)(0,0,1)(1,0,0)(1,1,0)(0,1,1)(1,1,1)(0,1,0)(1,0,1)Q1Q2Q3Figura 4.12:(a) Calcule nj = [Xj[ e mj = [Uj[.(b) Para que valores de j e Qj euleriano ? Justique.(c) Mostre que Qj e bipartido.(d) Para que valores de j e Qj hamiltoniano ? Justique.8. MostrequeseGfor euleriano, L(G)ser ahamiltoniano, masarecproca n ao e verdadeira.G20pa4.9. EXERCICIOS 559. Mostre que o grafo de Petersen (ver gura 4.13) n ao e hamiltoni-ano.Figura 4.13:G20pa56 CAPITULO 4. MAIS CICLOS E MAIS CAMINHOSG20paCaptulo 5Arvores5.1 Deni c oes e caracteriza c oesUm dos tipos mais freq uentes de grafos s ao as arvores, j a denidos an-teriormentecomografosconexossemciclos. Umgrafocujascompo-nentes conexas s ao arvores e chamado de oresta.rvoreflorestaFigura 5.1:Para umdado n umero de v erticesn, uma arvore e o grafo conexocommenorn umerode arestas. As v arias caracterizac oesdas arvorespodem ser reunidas no teorema a seguir.57G20pa58 CAPITULO 5.ARVORESTeorema - Seja Tum grafo comn v ertices. As seguintes armac oess ao equivalentes :(i) T e uma arvore.(ii) Tn ao cont em ciclos e temn 1 arestas.(iii) T e conexo e temn 1 arestas.(iv) T e conexo e toda aresta e uma ponte.(v) Todo par de v ertices de T e ligado por um unico caminho.(vi) Tn ao cont emciclos, mas a adic ao de uma aresta produz um unico ciclo.Demonstra c ao(i) (ii) - Peladenic ao de arvoreTn aocont emciclos. Portantoa retirada de uma arestauv separau dev e o grafo e separado emumparde arvoresT

eT

comn

en

v ertices respectivamente taisquen = n

+n

. Por induc ao, o n umero de arestas de T

e n

1 e o n umerode arestas de T

e n

1. Acrescentando a aresta uv concluimos que on umero de arestas de T e, portanto, (n

1) + (n

1) + 1 = n 1.(ii) (iii) - Se T fosse desconexo, cada componente seria uma arvore. Por induc ao, o n umero de arestas emcada componente e infe-rior ao n umero de v ertices em uma unidade e o n umero total de arestasseria inferior a n 1.(iii) (iv) - A retirada de qualquer aresta separa o grafo, pois n 2arestas s ao insucientes para conectar o grafo.(iv) (v) - Se existisse mais de umcaminhoentre dois v ertices, ografo teria um ciclo e haveria uma aresta que n ao separaria o grafo.(v) (vi) - SeTcontivesseumciclo, haveriaumpardev erticesligado por mais de umcaminho. A adic ao de uma arestauv, concate-nada como caminho ( unico) entre u e v, produz umciclo. Se esse ciclon ao fosse unico, a retirada da aresta uv deixaria dois caminhos distintosentre u e v.(vi) (i) - Basta mostrar que T e conexo. Se T fosse desconexo, umaaresta ligando duas componentes n ao produziria um ciclo.G20pa5.2.ARVORES GERADORAS 595.2Arvores geradorasO problema de conex ao de peso mnimoUma arvore geradora de umacomponente conexa de umgrafoG,comn v ertices, e um subgrafo que e uma arvore comn 1 arestas, isto e, toca todos os v ertices.Vimosqueumalgoritmogulosopodeser f acildeimplementar,mas dicilmente dar a umbomresultado (da o nome...). Uma excec aoocorre na soluc ao do seguinte problema: Dado umgrafoG valorado,qual a arvore geradora de menor valor ?. Por exemplo, se queremosrealizar a ligac ao de computadores em rede a cuso mnimo, que ligac oesdeveremos fazer ?A resposta ser a uma arvor geradora, e claro. Mas qual ?Ografo da gura 5.2 mostra o custo entre as ligac oes de umgrafoK5.abc de401004446441024260642Figura 5.2:Para resolver o problema, usaremos o algoritmo de Kruskal. Estealgoritmo consiste emtomar a aresta de menor valor; se ela n ao formaciclo, a acrescentamos` a nossa arvore. Caso contr ario, n os a despreza-mos. Quandotivermos conseguidon 1 arestas, nossa arvore estar aG20pa60 CAPITULO 5.ARVORESpronta.No nosso caso :c e 6a e 40Agora h a um empate entre a c e b d. Podemos escolher qualqueruma.a c forma ciclo.b d 42Temosoutroempate, agoraentreb c ed e. Podemosescolherqualquer uma. b c 44Ja temos 4 arestas. Nossa arvore est a completa.Total: 132Nossa arvore car a assim (veja gura 5.3) :deabc4042446Figura 5.3:Teorema - O algoritmo de Kruskal fornece uma soluc ao otima parao problema da conex ao de peso mnimo.Demonstra c ao - Oalgoritmo, evidentemente, fornece uma arvoregeradoraT. Suponhamos queTn ao tenha peso mnimo, isto e, existeuma arvore geradoraT

tal queopesodeT

e menordoqueopesoG20pa5.3. EXERCICIOS 61deT. Sejae a primeira aresta escolhida paraTque n ao pertence aT

.SeadicionarmoseaT

obtemosumcicloquecont emumaarestaekque n ao est a emT. Retiramos a arestaek e temos uma arvoreT compeso menor queT. Mas nesse caso, essa arestaek teria sido escolhidapeloalgoritmonolugardee, oquemostraqueoalgoritmoconstroiefetivamente uma arvore de menor peso.Umalgoritmo guloso pode ser usado para obter umlimite inferiorpara o PCV. Como umciclo e umcaminho adicionado de uma aresta,umlimiteinferior paraoPCV edadopelovalorda arvoregeradoramnima (obtido por umalgoritmo guloso) mais o menor valor de umaaresta n ao usada na arvore.5.3 Exerc cios1. Desenhe todas as arvores com 6 v ertices e com 7 v ertices.2. Mostre que umgrafo conexo, comn v ertices e m arestas, tem, nomnimo, mn + 1 ciclos distintos.3. Determine todas as arvores geradoras do grafo da gura 5.4.abcdeFigura 5.4:4. (a) Mostre que toda arvore e um grafo bipartido.(b) Que arvores s ao tamb em grafos bipartidos completos ?5. Como posso adaptar o algoritmo de Kruskal para obter o valor deuma arvore geradora de valor m aximo ?G20pa62 CAPITULO 5.ARVORES6. Prove que um grafo conexo e uma arvore se e s o se tem uma unica arvore geradora.7. Provequeuma arvorecom>1 tem, nomnimo v erticespendentes.8. Proveque uma arvoreemque exatamente2v ertices n aos aov ertices separadores e um caminho.9. O afastamento, de umv erticev e a maiordist ancia entrev e al-gumoutrov erticedografo. Omenor afastamentoentretodosos v ertices e chamado raio e denotado porr(G). O di ametro deumgrafo, denotado pordiam(G), e a maiordist ancia entre doisv ertices.Mostre que r(G) diam(G) 2.r(G).G20paCaptulo 6Subconjuntos especiais deum grafo6.1 Conjuntos independentesJ a vimos, pelo menos, um exemplo de subconjunto not avel de um grafo:um subgrafo independente, no qual nenhum par de v ertices est a ligado.Umconjuntoindependentepodedesempenhar papel importanteemuma modelagem.Suponhamos que um grafo represente a incompatibilidade dehor ariosentreprofessoresquedevemdar provanal; osv erticexey estar ao ligados se representaremprofessores que t emalunos emco-mum para ministrar a prova. Qual o maior n umero de professores quepode dar prova ao mesmo tempo ? a resposta e dada pelo subconjuntoindependente m aximo de v ertices do grafo.Osubconjuntoassinaladocomquadradosnegrosnografoda-gura6.1 mostraumconjuntocomestas caractersticas. O n umero deindepend encia, notac ao(G) e acardinalidade do subconjuntoinde-pendente m aximo de v ertices do grafo. No nosso exemplo (gura 6.1)(G) = 4.63G20pa64 CAPITULO 6. SUBCONJUNTOS ESPECIAIS DE UM GRAFOFigura 6.1:6.2 Colora c aoSuponha, noexemploanterior, quequis essemossaber qual omenorn umerodehor ariosnecess ariosparaministrar asprovas. Paraisto,devemos resolver o problema de particionar o conjunto de v ertices dografo emsubconjuntos independentes; cada conjunto corresponder a aumhor ariodeprova. Umaformaderesolver oproblema eatribuircores aos v ertices de forma que v ertices adjacentes tenhamnecessaria-mente cores diferentes.O menorn umero de cores que se pode utilizarser a portanto a soluc ao do problema.Observa c ao : N ao precisamos efetivamente colorir os v ertices. Oque fazemos e atribuir um n umero ou um smbolo aos v erticesPodemoscolorirosv erticescom12 cores(umaparacadav ertice)mas omenorn umeropossvel de cores e4 (vejaagura6.1). Ome-nor n umero de cores para colorir os v ertices de um grafo G e chamadon umero crom atico de G e denotado por(G). No caso, (G) = 4.Teorema - (G) + 1Demonstra c ao - Colorimos v ertice por v ertice. Cada v ertice podeG20pa6.3. CLIQUES 65ser adjacente a, no m aximo, v ertices. Podemos sempre encontrar umacor com que colorir o v ertice da vez.A demonstrac ao acima fornece um algoritmo para colorir um grafocom + 1 cores.Apresentamos, sem demonstrar, um teorema cl assico, que reduz umpouco o limite acima.Teorema (Brooks, 1941) - Se G e umgrafo conexo e n ao e Kn, e se(G) 3, ent ao (G) (G)Teorema - Um grafo G e bipartido se e s o se (G) = 2.Demonstra c ao - Basta fazer corresponder as partic oes independen-tes ` a duas cores.6.3 CliquesUma clique de G e um subgrafo completo de G. O n umero de v erticesdacliquem axima eon umerodecliquedeG, denotadopor (G).Note-se que uma clique de Gcorresponde a um conjunto independenteemG, isto e (G) = (G).6.4 AcoplamentosDa mesma forma que selecionamos umconjunto independente dev ertices, podemosconsiderar umconjuntoindependentedearestas,isto e, de arestas n ao incidentes duas a duas. Umconjunto deste tipo echamado um acoplamento do grafo G.Nagura6.2 oacoplamento emG1 e maximal (pois n aopode seraumentado) mas n ao e m aximo. O acoplamento emG2 e m aximo, masn ao toca todos os v ertices; os que s ao tocados s ao ditos v ertices satura-dos e os outros v ertices n ao saturados. O acoplamento em G3 e m aximoe saturatodos osv ertices; dizemos ent ao que e umacoplamento per-feito. O n umero de acoplamento de umgrafo G, denotado por

(G), e a cardinalidade do maior acoplamento de G.G20pa66 CAPITULO 6. SUBCONJUNTOS ESPECIAIS DE UM GRAFOG1G2G3Figura 6.2:Observac ao: Observeadiferencaentreosconceitosdem aximo(oconjuntodemaior cardinal podsvel dentrodascondic oes exigidas)emaximal(umconjuntoquen aopodeser aumentadosemviolar ascondic oesexigidas). Amesmaid eiase aplicaaconjuntosm nimoseminimais.Dado um grafo Ge um acoplamento M, um caminho M-aumentante emG e umcaminho que liga dois v ertices n ao saturadosporM que alternam arestas de M e arestas de GM.Teorema (Berge) - Um acoplamento M de um grafo G e m aximo see s o se n ao cont em um caminho M-aumentante.Demonstra c ao - Seh aumcaminhoM-aumentante, podemosobterumacoplamento umaunidade maioradicionando as arestas docaminho fora de M ao acoplamento e retirando as arestas emM do aco-plamento. A denic ao de caminho aumentante garante que o resultado e ainda um acoplamento. SeMn ao emaximoent aoexisteM

maximo. ConsidereD=MM

, a diferenca sim etrica entre M e M

(isto e, o conjunto de arestasde Me M

que n ao pertencemaM M

); como s ao acoplamentos, osv ertices emD t emgrau no m aximo 2. Logo, as componentes de D s aociclos pares (alternamarestas deMeM

) oucaminhos. Como [M

[ [M[, uma das componentes ao menos e um caminho alternando arestasde [M

[ e [M[ comecandoeterminandoemM

. Esse eumcaminhoM-alternante.G20pa6.5. ACOPLAMENTOS EM GRAFOS BIPARTIDOS 676.5 Acoplamentos em grafos bipartidosO acoplamento modela situac oes em que formamos pares; se o grafo Gfor bipartido, o acoplamento assume a forma de formac ao de casais, e e estudado de forma ligeiramente diferente. Seja G um grafo bipartidocom partic oes dos v ertices X e Y . Dizemos que temos um acoplamentode X em Y quando um acoplamento de G satura Y(mas n ao necessari-amente X).Apresentamos o seguinte teorema, sem demonstrac ao.Teorema - SeG e umgrafo bipartido compartic oes de v erticesXeY . Ent aoG temumacoplamentodeXemY sees ose [N(S)[[S[ S X, sendo N(S) a vizinhanca aberta de S.Demonstra c ao - Ver em West [6].As condic oes deste teorema s ao tamb em conhecidas como Condi c aode Hall.Teorema - Se k> 0, qualquer grafo k-regular bipartido admite umacoplamento perfeito.Demonstra c ao - Comecamos contando as arestas pelas extremida-des emXeY , as partic oes de v ertices; cada aresta temumaextremi-dade emX e outra emY , logok.[X[ =k.[Y [ e portanto [X[ = [Y [. S oprecisamos ent ao provar a condic ao de Hall. Considere S X, tal quehajar arestas entre S e N(S). ComoG e k-regular, temos que r = k[S[.Do lado de Ytemos r k.[N(S)[. Logo, k.[S[ k.[N(S)[ e, nalmente[S[ [N(S)[.6.6 Outros subconjuntosOutros tipos de subconjuntos e de invariantes t emsido estudados. Ci-taremos apenas 3.Coberturas de v ertices - E um subconjunto de v ertices tal que todaaresta e incidente a umv ertice do conjunto. O n umero de cober-tura de v ertices de um grafo G, denotado por(G), e a cardinali-dade da maior cobertura de v ertices de G.G20pa68 CAPITULO 6. SUBCONJUNTOS ESPECIAIS DE UM GRAFOCoberturas de arestas -E umsubconjunto de arestas tal que todov ertice e tocado por uma aresta do conjunto. O n umero de cober-tura de arestas de um grafo G, denotado por

(G), e a cardinali-dade da maior cobertura de arestas de G.Conjuntos dominantes -Eumsubconjuntodev erticestal quetodo v ertice do grafo est a no conjunto ou e adjacente a um de seusv ertices. O n umero de domin ancia de um grafo G, denotado por(G), e a cardinalidade do maior conjunto dominante de G.6.7 Exerc cios1. Qual o n umero de independ encia (Pet) do grafo de Petersen ?2. Qual o n umero de colorac ao (Pet) do grafo de Petersen ?3. ApresenteumacoplamentomaximaldografodePetersencom3 arestas. Encontre caminhos aumentantes que fornecamacopla-mentos de 4 e 5 arestas.4. Prove quen2 (G) n + 15. Mostre que se Kt e subgrafo de G ent ao (G) t.E verdade quese (G) = t ent ao Kt e subgrafo de G ?6. O ndice crom aticodografoG, denotadopor

(G), eomenorn umero de cores comque podemos colorir as arestas de maneiraque duas arestas incidentes tenham cores diferentes.(a) Calcule

(Kn).(b) Calcule

(Pet), o ndice crom atico do grafo de Petersen.7. (a) Provequeumconjuntoindependentemaximal eumcon-junto dominante.(b) Prove que um conjunto dominante minimal pode n ao ser umconjunto independente.G20pa6.7. EXERCICIOS 698. Mostre que:(a)

(G) (G).(b) (G)

(G).(c) (G).(G) n.(d) (G) n2.G20pa70 CAPITULO 6. SUBCONJUNTOS ESPECIAIS DE UM GRAFOG20paCaptulo 7Grafos planares7.1 Deni c oes e resultados simplesUm grafo planar e um grafo que admite uma representac ao gr aca emque as arestas s o se encontrem(possivelmente) nos v ertices a que s aoincidentes. Exemplos cl assicos de grafos planares s ao dados pelos gra-fos que representam os poliedros. Na gura 7.1, apresentamos os grafosdos 5 s olidos plat onicos: tetraedro, cubo, octaedro, dodecaedro e icosa-edro.Figura 7.1:71G20pa72 CAPITULO 7. GRAFOS PLANARESUma pergunta que pode ser feita e se existe umgrafo que n ao sejaplanar. Mostraremos queografoK5n ao e planar. De fato, qualquerrepresentac ao de K5 dever a ter um ciclo de comprimento 5, que divideo plano em interiore exterior. S o conseguimos colocar duas arestasno interior semque se cruzem; no exterior, a situac ao e a mesma. Nossobra uma aresta.Quantasarestaspodeter umgrafoplanar ? Umarepresentac aogr aca de um grafo com pelo menos um ciclo separa o plano em regi oes(no caso das arvores, temos uma unica regi ao). Essas regi oes s ao cha-madas faces; n ao devemos esquecer que uma das faces e tudo que so-brado plano - e a face ilimitada. O n umero de faces de umgrafo ser adesignado porf. Agura7.2 mostraduas representac oes do mesmografo, ilustrando que qualquer face pode ser colocada como face ilimi-tada.gabcdecdfabgefFigura 7.2:Para grafos planares, vale a relac ao de Euler para poliedros conve-xos.Teorema (Euler) - Num grafo planar conexo vale f m+n = 2Demonstra c ao - Demonstraremos por induc ao sobre o n umero dearestas. Tomemos um grafo conexo qualquer. Se for uma arvore, temosf m+n = 1(n1)+n = 2. Se houver um ciclo, retiramos uma arestado crculo, e o grafo ca comuma face a menos, mas pela hip otese deinduc ao a relac ao vale para o novo grafo. Temos ent ao (f 1) (m1) +n = 2 e logo f m+n = 2.Observamosquepodemosacrescentar arestasaumgrafoplanarG20pa7.1. DEFINICOES E RESULTADOS SIMPLES 73sempre que uma porc ao do plano estiver limitada por um ciclo de com-primento maior do que 3. Logo, umgrafo maximal planar, umgrafoao qual n ao poderemos acrescentar arestas semcomprometer a plana-ridade, tem uma representac ao composta por ciclos de comprimento 3.Isso nos d a outra relac ao importante.Teorema -Num grafo planar conexo Gvale m 3.n6; a igualdadevale se G e maximal planar.Demonstra c ao - Se formos contar as arestas de cada face, contare-mos duas vezes cada aresta do grafo. Como cada face tem no mnimo 3arestas (a igualdade valendo no caso maximal) temos:3.f 2.mSubstituindo na f ormla de Euler:f m+n = 23.f 3.m+ 3.n = 62.m3.m+ 3.n 6m 3.n 6Esteteoremanosd aoutrademonstrac aodequeK5n ao eplanar.De fato,K5 ( e de resto todos os grafos completos commais do que 4v ertices) n ao obedece ` a relac ao acima: 10 > 3.5 6.Teorema - Num grafo planar bipartido conexo G vale m 2.n 4.Demonstra c ao - Observamos que umgrafo bipartido s o temciclospares. Cada face tem no mnimo 4 arestas.4.f 2.mSubstituindo na f ormla de Euler:f m+n = 24.f 4.m+ 4.n = 8G20pa74 CAPITULO 7. GRAFOS PLANARES2.m4.m+ 4.n 8m 2.n 4Vemos agora queK3,3 n ao e planar, pois 9>2.6 4. Oproblemadas casinhas, na introduc ao, acaba de ser resolvido.7.2 Teorema de KuratowskiA id eia de planaridade e aparentemente topol ogica, mas sempre pairoua quest ao sobre se haveria uma caracterizac ao combinat oria dos grafosplanares. Arespostafoi dadaatrav es de umteorema, que apresenta-mos, sem demonstrac ao, depois de algumas denic oes.Uma subdivis ao do grafo G e o grafo G

que obtemos pela inserc aodeP2 (caminho de comprimento 2) no lugar de uma aresta deG. Umgrafo G

e dito homeomorfo ao grafo Gse G

puder ser obtido de Gporsucessivas operac oes de subdivis ao(veja gura 7.3)G GFigura 7.3:Teorema (Kuratowski) - Um grafo e planar se n ao contiver subgrafohomeomorfo a K5 ou a K3,3. Demonstra c ao - Ver em Fournier[7]Comoaplicac aomostramosnagura7.4 queografode Petersenn ao e planar.Observamos que embora tenhamos tratado o exemplo gracamente,a vericac ao das condic oes do teorema pode ser feita de forma compu-tacional (embora possa ser complexa).G20pa7.3. DUALIDADE 75aaabbbK3,3Figura 7.4:7.3 DualidadeO DualGDde umgrafo simples planarG e o grafo construdo da se-guinte maneira:(i) A cada face de G associamos um v ertice emGD.(ii) AcadaarestadeG (que separaduas faces) associamos umaaresta emGDligando os v ertices correspondentes ` as faces.Um bomexemplo s ao os s olidos plat onicos apresentados na Figura7.4. O cubo e o dual do octaedro, o icosaedro e o dual do dodecaedro eo tetraedro e o dual dele mesmo (auto-dual). Esses duais correspondemaos duais da geometria cl assica. A gura 7.5 mostra a correspond enciaentre as faces do cubo e os v ertices do octaedro.fif1f5f3f4f2f6v1v3v2v5v4v6viFigura 7.5:G20pa76 CAPITULO 7. GRAFOS PLANARESVerica-se com facilidade que o dual do dual de G e o pr oprio grafoG (desde que G tenha conexidade maior ou igual a 3).A dualidade aparece numdos problemas mais famosos, n ao s o dateoria dos grafos, mas da matem atica.7.4 O problema das 4 coresEm1852 FrederickGuthrie, alunodeAugustusdeMorgan, trouxeaeste um problema proposto por seu irm ao Francis Guthrie. Na verdadetratava-se de uma conjectura, hoje um teorema.Teorema das 4 cores - Um mapa pode ser colorido com 4 cores.Colorir ummapa e colorir as regi oes de maneira que regi oesfronteiricas n ao sejam coloridas com a mesma cor. Usando a dualidadepodemos formular o teorema em forma de colorac ao de v ertices.Teorema das 4 cores-2aformula c ao - Num grafo planar (G) 4.O grafo K4mostra que 4 cores s ao necess arias; mas ser aosucientes ?Oproblemademorouums eculoparaser resolvidoem1976 por Appel, Haken e Koch, com o auxlio de 1200 horas do compu-tador mais rapido de sua epoca, executando mais do que 1010operac oescomputacionais. Embora a teoria envolvida seja profunda muitos con-sideram esta a mais feia prova da matem atica.As tentativas anteriores s ao, entretanto, dignas de nota. Kempe uti-lizouuma t ecnica (por isso chamada de cadeias de Kempe) e apresen-tou uma demonstrac ao em 1879. Heawood, onze anos depois, percebeuuma falha sutil na demonstrac ao, que a invalidava. Entretanto, utilizouascadeiasdeKempeparademonstrar umresultadoumpoucomaisfraco. Comecaremos por um lema.Lema - Num grafo planar h a pelo menos um v ertice comgrau me-nor ou igual a 5.Demonstra c ao -J a sabemos que

vV (G)d(v) = 2.m. Se d(v) > 5v Vent ao:6.n

vV (G)d(v) = 2.m.G20pa7.5. EXERCICIOS 77Mas num grafo planar m 3.n 6, isto e 2m 6.n 12. Ficamos com6.n 6.n 12,o que e impossvel.Teorema das 5 cores - Num grafo planar simples G, tem-se (G) 5Demonstra c ao - Em todo grafo planar existe um v ertice com grau me-nor ouigual a5. Podemosdecompor ograforetirandosempreumv ertice de graumenor que 5 e recomp o-lo colorindo, v ertice a v ertice.Desta forma, podemos sempre supor que estamos colorindo um v erticev de graumenorouigual a5. Se os v ertices emN(v) est ao coloridascommenosdoque5 cores, bastacolorir ov erticev. Podemosent aosupor que o v ertice est a cercado por 5 v ertices coloridos cada umcomuma cor do conjunto a, b, c, d, e.Consideremos o subgrafo induzido pelos v ertices coloridos comascores a e c. Se a componente que cont em o v ertice de N(v) colorido coma n ao contiver o v ertice colorido comc, podemos trocar as cores destacomponente: quem est a colorido coma ca colorido comc e vice versa.Podemos ent ao colorir o v ertice v com a cora.Se a componente que cont emo v ertice deN(v) colorido coma foro mesmo do v ertice colorido comc, existe umcaminho de v ertices quecercao v erticeb (veja gura 7.6). Ent ao, tomamos a componente dografo induzido por v ertices coloridos comb e d, que cont em o v ertice deN(v) colorido comb. Depois de trocar as cores b e d nesta componente,podemos colorir o v ertice v com a corb.7.5 Exerc cios1. Construa o grafo com sequ encia de graus (4, 4, 3, 3, 3, 3):(a) Que seja planar.(b) Que n ao seja planar2. Mostre que um grafo planar com = 5 tem no mnimo 12 v ertices.D e um exemplo de grafo com = 5 e n = 12.G20pa78 CAPITULO 7. GRAFOS PLANAREScabd eFigura 7.6:3. Um grafo e auto-dual se GD e isomorfo a G.(a) Mostre que se G e auto-dual ent ao 2.n = m+ 2.(b) Um grafo roda (notac ao Wn) e o grafo obtido pela adic ao deumv ertice de graun 1 aCn1 (ver gura 7.7).Mostre queos grafos roda Wn s ao auto-duais.W6Figura 7.7:4. Mostre que umgrafo planarG e bipartido se e s o se GD e euleri-ano.5. Mostre que umgrafo planar conexo pode ter sua faces coloridascom 2 cores se e s o se G e euleriano.6. Mostre que os grafos abaixo (gura7.8) s aoisomorfos mas seusduais n ao s ao. Esse fato contraria o texto do captulo ?G20pa7.5. EXERCICIOS 79Figura 7.8:7. A cintura de umgrafo, denotada porg(G), e o comprimento doseu menor ciclo. Mostre que num grafo planar temos:m (n 2).gg 2Sugest ao: adapte ademonstrac aodosdois ultimosteoremas dasess ao 7.1.8. Mostre que e possvel obter umgrafo planar a partir do grafo dePetersen pela retirada de 2 arestas.9. Mostre que um grafo n ao planar tem 5 v ertices de grau no mnimo4 ou tem 6 v ertices de grau no mnimo 3.10. (a) (Resolvido) Mostre que o grafo n ao planar K3,3 pode ser de-senhado semcruzamentos numtoro . E numa esfera, pode?Soluc ao: Aseq u encia apresentada na gura 7.9 mostracomopodemos recortarotoroparatransform a-lonumret angulo. As setas mostramcomo podemos passar as ares-tas pelos cortes.(b) Mostrecomopodemosdesenhar K5numtoro. Oteoremadas 4 cores vale para o toro ?(c) Mostre como podemos desenharK7 numtoro. Voc e conse-guedividir otoroem7 regi oesdemaneiraquecadaumafaca fronteira com todas as outras 6 ?G20pa80 CAPITULO 7. GRAFOS PLANARESa ab bccddFigura 7.9:G20paRefer encias Bibliogr acas[1] BoaventuraNetto,P.O.,Grafos: Teoria, Modelos, Algoritmos, 2a. ed,Edgard Bl ucher (1996)[2] Carvalho, P.C.P., Contagem, Apostila2 do Est agio de treinamentodos alunos premiados da OBMEP, 2006[3] Wilson, R., Introduction to Graph Theory, Addison Wesley,(1996)[4] Balakrishnan, J.;Ranganathan,K.,A Textbook of Graph Theory,Springer-Verlag (1999)[5] Garey, M. R.;Johnson, D. S.,Computers and Intractability: AGuide tothe Theory of NP-Completeness, W.WH. Freeman (1979)[6] West, D.,Introduction to Graph Theory, Prentice Hall (1996)[7] Fournier, J-C, Demonstration simple duth eoreme de Kuratowski et desa forme duale, Discrete Mathematics, 31 (1980) 329-33281G20pa82 REFERENCIAS BIBLIOGR AFICASG20paIndice RemissivoL(G), 22

(G), 65(G), 63

(G), 68(G), 67, 68(G), 64(G), 65diam(G), 62g(G), 79r(G), 62 arvore, 18 arvore geradora, 59ndice crom atico, 68acoplamento, 65acoplamento de X emY , 67acoplamento perfeito, 65adjacente, 6afastamento, 62algoritmo de Dijkstra, 27algoritmo de Kruskal, 59aresta, 6auto-complementar, 22auto-dual, 78cadeias de Kempe, 76caminho, 17caminho M-aumentante, 66ciclo, 17ciclo hamiltoniano, 48cintura, 79clique, 65coberturas de v ertices, 67componente conexa, 11, 25comprimento de um caminho, 17conjunto separador, 53di ametro, 62Dijkstra, 27dist ancia, 25dual, 75face, 72face ilimitada, 72oresta, 57grafo, 2, 5grafo k-regulrar, 17grafo adjunto, 22grafo bipartido, 18grafo bipartido completo, 18grafo complementar, 16grafo completo, 1583G20pa84INDICE REMISSIVOgrafo conexo, 11, 25grafo de linha, 22grafo de Petersen, 74grafo desconexo, 11grafo euleriano, 44grafo hamiltoniano, 49grafo homeomorfo, 74grafo maximal planar, 73grafo planar, 71grafo regulrar, 17grafo roda, 78grafo semi-euleriano, 44grafo semi-hamiltoniano, 49grafo simples, 10grafo valorado, 28grafo vazio, 17grafos isomorfos, 12grau, 7grau m aximo, 14grau mnimo, 14Kuratowski, 74laco, 9maximal, 65minimal, 66n umero crom atico, 64n umero de acoplamento, 65n umero de clique, 65n umero de cobertura de arestas, 68n umerodecoberturadev ertices,67n umero de domin ancia, 68n umero de independ encia, 63passeio, 25peso, 48ponte, 53raio, 62representac ao gr aca, 6saturados, 65seq u encia de graus, 14subconjunto independente, 18subdivis ao, 74subgrafo, 14subgrafo induzido, 15Teorema de Euler, 45Teorema de Festinger, 53trilha, 25trilha fechada, 25v ertice, 6v ertice isolado, 14v ertice pendente, 14v ertice separador, 53vizinhanca aberta, 14vizinhanca fechada, 14