Nocoes da Teoria dos Grafos

Andre Arbex Hallack

Indice

1 Introducao e definicoes basicas.Passeios eulerianos 1

2 Ciclos hamiltonianos 7

3 Arvores 11

4 Emparelhamento em grafos 15

5 Grafos planares:Colorindo grafos e mapas 19

Referencias 25

i

Capıtulo 1

Introducao e definicoes basicas.

Passeios eulerianos

Introducao historica

O Problema das pontes de Konigsberg

Na cidade de Konigsberg, sete pontes cruzavam o rio Pregel, estabelecendo ligacoes entre duasilhas e entre as ilhas e as margens opostas do rio, conforme a ilustracao abaixo:

Figura 1.1: As pontes de Konigsberg

Problema: Seria possıvel fazer um “passeio” pela cidade, cruzando cada ponte exatamente uma vez?

1

2 CAPITULO 1

Em 1736, Euler publicou um artigo demonstrando que tal passeio era impossıvel. Mais importantee o fato de Euler ter formulado um criterio geral para resolver o problema acima, o que e consideradocomo o primeiro teorema da chamada TEORIA DOS GRAFOS, a qual possui desdobramentos eaplicacoes nas mais diversas areas.

Definicao 1.1. Um GRAFO e uma colecao G = (N,A) constituıda por um conjunto nao-vazio efinito N de NOS (ou pontos, ou vertices) e um conjunto (finito) A de ARCOS (ou arestas), sendoque cada arco liga dois nos (nao necessariamente distintos).

Exemplos:

Figura 1.2: Exemplos de grafos

Um grafo e dito SIMPLES quando cada par de nos e ligado por no maximo um arco e nenhumno e ligado a si proprio (nenhum laco). Caso contrario, temos o chamado MULTIGRAFO.

Um arco e dito INCIDENTE nos nos aos quais esta associado e vice-versa.Um no e dito ISOLADO quando nao esta ligado a nenhum outro.Dois arcos incidentes num mesmo no sao ditos ADJACENTES. Dois nos incidentes num mesmo

arco sao ditos adjacentes.

O GRAU de um no e o numero de arcos incidentes no no, sendo que cada laco conta como doisarcos.

Introducao e definicoes basicas.Passeios eulerianos 3

Teorema 1.2. (Euler) A soma dos graus dos nos de um grafo e igual ao dobro do numero de arcos.

Prova: Ao somarmos os graus contamos cada arco duas vezes, uma vez em cada extremidade.

Corolario 1. O numero de nos de grau ımpar de todo grafo e sempre par.

De fato, se denotarmos por di o grau de cada no i no grafo G = (N,A) , temos:

2 ·#A =∑i∈ IN

di =∑

di pardi +

∑di ımpar

di

Como 2 ·#A e∑

di pardi sao pares, entao

∑di ımpar

di e par e para que a soma de numeros

ımpares seja par, devemos ter uma quantidade par de numeros ımpares.

Exercıcio: Prove que numa festa com 51 pessoas existe sempre uma pessoa que conhece umnumero par de outras pessoas.

Passeios eulerianos

Definicao 1.3. Um PASSEIO entre os nos i e j de um grafo e uma sequencia alternante denos e arcos, comecando em um dos nos i ou j e terminando no outro, tal que cada arco percorridoe incidente aos nos que o cercam na sequencia. Um passeio e dito FECHADO quando comeca etermina no mesmo no.

Exemplo:

Figura 1.3: Um passeio entre os nos 6 e 1

Um CAMINHO e um passeio que nao contem nos repetidos. Dois nos estao CONECTADOSse existe um caminho entre eles no grafo. Um grafo e dito CONEXO quando cada par de nos estaconectado, caso contrario ele e dito DESCONEXO.

4 CAPITULO 1

Um passeio em um grafo e dito EULERIANO quando passa por todo arco exatamente uma vez.

A luz das definicoes acima, o Problema das pontes de Konigsberg refere-se exatamente a existenciaou nao de um passeio euleriano pela cidade (grafo), quando se considera as pontes como arcos e osterritorios (ilhas ou margens) como nos:

Figura 1.4: Grafo correspondente as pontes de Konigsberg

O argumento de Euler para as pontes de Konigsberg: Consideremos um dos territorios(ilhas ou margens), que chamaremos de territorio I. Suponhamos que o passeio nao comeca em I.Entao entramos em I pela primeira vez atraves de uma ponte que e incidente em I e saımos de I poroutra ponte incidente em I. Cada entrada-e-saıda de I corresponde ao uso de duas pontes. Como Item um numero ımpar de pontes incidentes, na ultima vez que usamos uma ponte incidente em I,entramos em I e nao podemos mais sair, ou seja, o passeio termina necessariamente em I. Assim, pelomesmo argumento, se o passeio comeca em qualquer territorio, deve necessariamente terminar nosoutros tres (contradicao!), pois todos tem um numero ımpar de pontes incidentes.

O argumento anterior leva ao seguinte teorema:

Teorema 1.4. (Euler)

(a) Se um grafo conexo tem mais que dois nos com grau ımpar, entao ele nao admite um passeioeuleriano.

(b) Se um grafo conexo tem exatamente dois nos com grau ımpar, entao ele admite passeio eu-leriano e todo passeio euleriano tem que comecar em um desses nos de grau ımpar e terminar nooutro.

(c) Se um grafo conexo nao tem nos com grau ımpar, entao ele admite passeio euleriano e todopasseio euleriano e fechado.

Exercıcio: Prove a partir do teorema acima que um grafo conexo tem um passeio eulerianofechado se, e somente se, todo no tem grau par.

Introducao e definicoes basicas.Passeios eulerianos 5

Exercıcio: Quais dos grafos abaixo admitem um passeio euleriano? Em caso afirmativo, indiqueum passeio euleriano.

Exercıcio:

(a) Construa ou destrua UMA ponte em Konigsberg para que se tenha um passeio euleriano(indique o passeio).

(b) Mostre como se pode ter um passeio euleriano fechado construindo mais DUAS pontes emKonigsberg (indique o passeio).

(c) Mostre como se pode ter um passeio euleriano fechado construindo UMA ponte e destruindoOUTRA em Konigsberg.

(d) O que ocorre se destruirmos DUAS pontes em Konigsberg?

6 CAPITULO 1

Capıtulo 2

Ciclos hamiltonianos

Problema: Seis cidades (nos) sao ligadas por uma rede de estradas (arcos) conforme o mapa(grafo) abaixo:

Um vendedor pretende, partindo de uma cidade, passar exatamente uma vez em cada uma dasdemais cidades, terminando a viagem na cidade de origem.

E possıvel realizar uma viagem nas condicoes acima?

Definicao 2.1. Um CICLO e um passeio fechado no qual apenas o no inicial-terminal se repete.

Um CICLO HAMILTONIANO e um ciclo que contem todos os nos de um grafo.

7

8 CAPITULO 2

Observacoes:

(a) O problema acima equivale a perguntar se o grafo formado admite um ciclo hamiltoniano.

(b) E claro que para um grafo admitir um ciclo hamiltoniano e NECESSARIO que ele seja conexo.

(c) Nao existem resultados gerais de caracterizacao dos grafos que admitem ciclos hamiltonianos.

(d) Problema do caixeiro viajante: achar um ciclo hamiltoniano de custo mınimo, sendo o custode um ciclo a soma dos custos dos arcos percorridos no ciclo.

Proposicao 2.2. Num ciclo com tres ou mais nos sao percorridos exatamente dois arcos incidentesem cada no do ciclo.

Corolario 1. Um grafo que tenha tres ou mais nos e algum no de grau menor ou igual a 1nao admite um ciclo hamiltoniano.

Exercıcio: Resolva o problema inicial (do vendedor e as seis cidades): indique um ciclo hamilto-niano caso exista solucao ou prove que nao existe ciclo hamiltoniano algum.

Exercıcio: Responda se os grafos abaixo admitem ou nao um ciclo hamiltoniano. Indique umciclo hamiltoniano em caso afirmativo ou prove que nao admite, no caso negativo.

Ciclos hamiltonianos 9

Exercıcio: Um grafo G = (N,A) e dito BIPARTIDO quando seu conjunto N de nos pode serparticionado em DOIS subconjuntos tais que nos pertencentes a um mesmo subconjuntos nao saoadjacentes.

(a) Prove que se um grafo bipartido G = (N,A) admite um ciclo hamiltoniano entao os doissubconjuntos da particao de N tem o mesmo numero de elementos.

(b) Conclua que o grafo abaixo NAO ADMITE um ciclo hamiltoniano.

(c) Construa um grafo bipartido com um numero par de nos, todos com grau maior ou igual adois, e que nao admite um ciclo hamiltoniano.

10 CAPITULO 2

Capıtulo 3

Arvores

Problema: Atraves de cabos telefonicos (arcos) entre pares de cidades (nos), deseja-se configuraruma rede de comunicacoes (grafo) entre as sete cidades do mapa abaixo, de modo que possa havercomunicacao entre cada par de cidades, ou seja, cada par de cidades esteja conectado por pelo menosum caminho na rede de comunicacoes (o grafo e conexo).

(a) E possıvel obter uma rede (grafo) conexa com exatamente um caminho conectando cada parde cidades? (neste caso e facil ver que o grafo sera MINIMALMENTE CONEXO, ou seja, a remocaode qualquer arco ira tornar o grafo desconexo).

(b) Dentre todas as redes (grafos) conexas possivelmente obtidas na letra (a) acima, e possıvelobter uma de menor custo (OTIMA)?

11

12 CAPITULO 3

Definicao 3.1. Uma ARVORE e um grafo simples tal que para cada par de nos existe exatamenteum caminho que os conecta.

Observacoes:

(a) O problema inicial equivale a perguntar se e possıvel formar uma arvore com os nos (cidades)dados e, em caso afirmativo, se existe uma arvore de menor custo.

(b) Um grafo G e uma arvore se, e somente se, G e conexo e a remocao de qualquer um de seusarcos resulta em um grafo desconexo (uma arvore e um grafo MINIMALMENTE CONEXO).

(c) Uma arvore nao admite ciclos com tres ou mais nos (pois se admitisse haveria mais de umcaminho conectando dois nos) e a adicao de um arco ligando dois nos que nao eram ligados por umarco gera um ciclo com tres ou mais nos (uma arvore e um grafo MAXIMALMENTE LIVRE DECICLOS COM TRES OU MAIS NOS).

Exemplos:

• PROCEDIMENTO DE CRESCIMENTO DE ARVORE (como obter arvores)

- Comece com um simples no.

- Repita o que se segue um numero (FINITO) qualquer de vezes: Se G e o grafo ate entao formado,crie um novo no e ligue-o por um arco novo a qualquer no de G.

Arvores 13

Teorema 3.2. Todo grafo obtido pelo procedimento de crescimento de arvore e uma arvore e todaarvore pode ser obtida desta maneira.

Corolario 1. Toda arvore com n nos tem n− 1 arcos.

• O ALGORITMO GULOSO DE KRUSKAL (encontrando a arvore otima)

- Considere n nos e nenhum arco.

- Construa um arco de menor custo entre dois nos distintos que nao estejam ligados por um arcoe de maneira que nao se obtenha um ciclo com tres ou mais nos.

- Repita o procedimento acima ate que se tenha n− 1 arcos.

Teorema 3.3. Dados n nos e nenhum arco, o Algorıtmo Guloso produz uma arvore de menor custo(arvore otima) entre todas as possıveis arvores com os n nos inicialmente dados.

Observacao: Uma tentativa de adaptacao do Algorıtmo Guloso pode nao funcionar para obterum ciclo hamiltoniano otimo (Problema do caixeiro viajante).

Exercıcio: (a) USANDO O PROCEDIMENTO DE CRESCIMENTO DE ARVORE, resolvaa letra (a) do problema inicial, obtendo uma rede de comunicacoes minimalmente conexa entre ascidades dadas. (b) Considerando os custos proporcionais as distancias, USE O ALGORITMO GU-LOSO e obtenha uma rede de comunicacoes minimalmente conexa e de menor custo possıvel (otima)entre as cidades dadas, resolvendo assim a letra (b) do problema inicial:

14 CAPITULO 3

Exercıcio: Prove a Observacao apos o Teo 3.3(Sugestao: considere os pontos A(0, 0), B(1, 0), C(0, 1) e D(9, 1))

Exercıcio: Para cada um dos grafos dados abaixo, faca o que se pede.

- Responda se o grafo e uma arvore.

- Se o grafo nao for uma arvore, justifique.

- Se o grafo for uma arvore, responda se e uma arvore de menor custo (custos proporcionais asdistancias) considerando os nos dados. Se nao for uma arvore de menor custo, exiba uma arvore demenor custo com os nos dados.

Capıtulo 4

Emparelhamento em grafos

Problema: Temos um conjunto de seis tarefas (nos) a ser realizadas e seis funcionarios (nos)para realizar as tarefas. Quando um funcionario tem habilidade para realizar uma tarefa, ambosserao ligados por um arco.

Cada funcionario Fi tem habilidade para realizar um conjunto {Tj} de tarefas, conforme o grafoabaixo:

E possıvel atribuir exatamente uma tarefa a cada funcionario de modo que todas as tarefas sejamrealizadas?

15

16 CAPITULO 4

Definicao 4.1. Uma grafo G = (N,A) e dito BIPARTIDO quando seu conjunto N de nos pode serparticionado em dois subconjuntos tais que os nos pertencentes a um mesmo subconjunto nao saoadjacentes.

Um EMPARELHAMENTO PERFEITO em um grafo bipartido e um conjunto de arcos A′ ⊂ A

tal que cada no do grafo e incidente em exatamente um arco do conjunto A′.

Observacoes:

(a) O problema inicial equivale a perguntar se o grafo dado tem um emparelhamento perfeito.

(b) E claro que se um grafo bipartido G = (N,A) , sendo N = N1 ∪ N2 a particao de N , temum emparelhamento perfeito entao #N1 = #N2 e N e obrigatoriamente par.

Teorema 4.2. (Teorema do emparelhamento) Um grafo bipartido G = (N,A) , sendo N = N1∪N2

a particao de N , tem um emparelhamento perfeito se, e somente se, #N1 = #N2 e para qualquersubconjunto N ′

1 ⊂ N1 temos pelo menos #N ′1 nos em N2 adjacentes aos nos de N ′

1.

Observacao: Vale a simetria no teorema acima.

Corolario 1. Se em um grafo bipartido todo no tem mesmo grau d ≥ 1 , entao o grafo contem umemparelhamento perfeito.

Exercıcio: Usando o Teorema 4.2, verifique se o problema inicial das seis tarefas para os seisfuncionarios tem solucao.

Exercıcio: Prove o Corolario do Teorema 4.2.

Exercıcio: Desenhe um grafo cujos nos sao os subconjuntos de {a, b, c} e dois nos sao adjacentesse, e somente se, eles sao subconjuntos que diferem por exatamente um elemento.(a) Qual e o numero de arestas e nos nesse grafo?(b) Esse grafo e conexo? Ele tem um emparelhamento perfeito? (exiba um caso tenha) Ele admiteum ciclo hamiltoniano? (exiba um caso admita)

Emparelhamento em grafos 17

Exercıcio: Verifique (justifique) se os grafos abaixo tem emparelhamentos perfeitos e exiba taisemparelhamentos nos casos afirmativos.

Exercıcio: Numa festa ha 286 convidados. Cada homem conhece 30 mulheres e cada mulherconhece 30 homens (o conhecimento e mutuo). A organizacao da festa deseja saber qual o numeromaximo de casais que podem estar dancando simultaneamente para providenciar o espaco adequado.Que numero e esse? (prove).

18 CAPITULO 4

Capıtulo 5

Grafos planares:

Colorindo grafos e mapas

Definicao 5.1. Uma grafo simples e conexo e chamado PLANAR quando ele pode ser desenhadocomo um mapa no plano: seus nos correspondem a pontos distintos no plano e seus arcos saocurvas plana (ligando os nos) as quais nao se intersectam em pontos que nao sejam os nos.

EXEMPLO: K4 = grafo completo sobre 4 nos = grafo com 4 nos onde cada no esta ligado atodos os demais:

Observacao: Um grafo planar, quando representado de forma planar, divide o plano em umaquantidade finita de regioes, sendo uma delas ilimitada e as demais (se existirem) limitadas.

19

20 CAPITULO 5

EXEMPLO:

Teorema 5.2. (Formula de Euler) Seja G um grafo planar. Se v e o numero de nos de G, a e onumero de arcos de G e f e o numero de regioes do plano determinadas pela sua forma planar, entao

v − a + f = 2

Corolario 1. Um grafo planar sobre n ≥ 3 nos tem no maximo 3n− 6 arcos. (Exercıcio)

Exercıcio: Existem 3 casas e 3 fontes. Podemos construir um caminho de toda casa para todafonte de modo que esses caminhos nao se cruzem? (os caminhos nao sao necessariamente linhas retas)

Exercıcio: Prove que K5 (grafo completo sobre 5 nos) nao e um grafo planar.

Exercıcio: O grafo obtido pela omissao de um arco de K5 e planar?

Exercıcio: O Grafo de Petersen e planar?

Grafos planares:Colorindo grafos e mapas 21

• Colorindo grafos

Regra para coloracao de grafos: nos adjacentes tem que ser coloridos com cores diferentes.

Se podemos colorir um grafo com k cores (dentro da regra acima), dizemos que o grafo ek−COLORIVEL.

O menor valor de k para o qual o grafo e k−colorıvel e chamado de NUMERO CROMATICO dografo.

Observacoes:

(a) E obvio que se um grafo tem n nos entao n cores sao sempre suficientes para colori-lo (o grafoe n−colorıvel) e seu numero cromatico e menor ou igual a n.

(b) Um grafo e 2−colorıvel se, e somente se, ele e bipartido.

Teorema 5.3. (Teorema de Brooks) Se todo no em um grafo tem grau no maximo d, entao o grafopode ser colorido com d + 1 cores.

Exercıcio: Obtenha o numero cromatico dos grafos a seguir:

A) K5

B)

C) Grafo de Petersen

D)

22 CAPITULO 5

• Colorindo mapas

Consideremos agora o problema de colorir um mapa que seja uma representacao plana de diversasregioes (paıses, estados, etc.) CONEXAS (dois pontos de uma mesma regiao podem ser “ligados poruma estrada dentro da propria regiao”).

E natural pedirmos que regioes vizinhas (com fronteira de comprimento nao-nulo comum) tenhamcores diferentes.

IDEIA: Cada regiao conexa sera representada por um no e regioes (nos) vizinhas serao ligadaspor um arco, formando assim um GRAFO DUAL do mapa original. O grafo dual assim obtido seraum grafo planar (desafio: tente provar) e o nosso problema de colorir o mapa original se reduz aoproblema de colorir seu grafo dual.

Exercıcio: Obtenha os grafos duais (em suas representacoes planares) para os mapas dadosabaixo:

Exercıcio: Obtenha os numeros cromaticos dos grafos duais obtidos no exercıcio anterior e coloraos grafos e os mapas segundo os numeros obtidos.

Exercıcio: De exemplo de um mapa para mostrar que se admitirmos regioes desconexas, o grafodual obtido nao e necessariamente planar.

Teorema 5.4. (Teorema das 4 cores) Todo grafo planar pode ser colorido com 4 cores.

Corolario 1. Todo mapa que e representacao planar de regioes conexas pode ser colorido com 4 cores.

Exercıcio: Exiba um mapa que precise de mais do que 4 cores para ser colorido.

Grafos planares:Colorindo grafos e mapas 23

Exercıcio: Um grafo G′ e dito um SUBGRAFO de um grafo G quando G′ e obtido a partir deG eliminando-se nos (e seus arcos incidentes) ou arcos de G.

(a) Prove que se todo subgrafo de um grafo G tem um no de grau menor ou igual a d entao G ed + 1 colorıvel. (Sugestao: inducao sobre o numero de nos de G)

(b) Prove que todo grafo planar tem um no de grau menor ou igual a 5. (Sugestao: use o Corolariodo Teorema 5.2)

(c) Conclua que todo grafo planar pode ser colorido com 6 cores (“Teorema das 6 cores”)

24 CAPITULO 5

Referencias

[1] Lovasz, L. e outros, Matematica Discreta, Colecao Textos Universitarios, SBM, Rio deJaneiro, 2003.

[2] Santos, J. P. O. e outros, Introducao a Analise Combinatoria, Editora Unicamp, Campinas,2002.

25