Noções da Teoria dos Grafos
André Arbex Hallack
Junho/2015
Índice
1 Introdução e definições básicas.
Passeios eulerianos
1
1.1
Introdução histórica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2
Passeios eulerianos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2 Ciclos hamiltonianos
5
3 Árvores
7
Referências
11
i
Capı́tulo 1
Introdução e definições básicas.
Passeios eulerianos
1.1
Introdução histórica
O Problema das pontes de Königsberg
Na cidade de Königsberg, sete pontes cruzam o rio Pregel, estabelecendo ligações entre duas ilhas
e entre as ilhas e as margens opostas do rio, conforme a ilustração abaixo:
Problema: É possı́vel fazer um “passeio” pela cidade, cruzando cada ponte exatamente uma vez?
Em 1736, Euler publicou um artigo demonstrando que tal passeio é impossı́vel. Mais importante
é o fato de Euler ter formulado um critério geral para resolver o problema acima, o que é considerado
como o primeiro teorema da chamada TEORIA DOS GRAFOS, a qual possui desdobramentos e
aplicações nas mais diversas áreas.
1
2
CAPÍTULO 1
Definição 1.1. Um GRAFO é uma coleção G = (N, A) constituı́da por um conjunto não-vazio e
finito N de NÓS (ou pontos, ou vértices) e um conjunto A de ARCOS (ou arestas), sendo que cada
arco liga dois nós (não necessariamente distintos).
Exemplos:
Um grafo é dito SIMPLES quando cada par de nós é ligado por no máximo um arco e nenhum
nó é ligado a si próprio (nenhum laço). Caso contrário, temos o chamado MULTIGRAFO.
Um arco é dito INCIDENTE nos nós aos quais está associado e vice-versa.
Um nó é dito ISOLADO quando não está ligado a nenhum outro.
Dois arcos incidentes num mesmo nó são ditos ADJACENTES. Dois nós incidentes num mesmo
arco são ditos adjacentes.
O GRAU de um nó é o número de arcos incidentes no nó, sendo que cada laço conta como dois
arcos.
Teorema 1.2. (Euler) A soma dos graus dos nós de um grafo é igual ao dobro do número de arcos.
Prova: Ao somarmos os graus contamos cada arco duas vezes, uma vez em cada extremidade.
Corolário 1. O número de nós de grau ı́mpar de todo grafo é sempre par.
De fato, se denotarmos por di o grau de cada nó i no grafo G = (N, A) , temos:
X
X
X
2 · #A =
di =
di +
di
i∈ IN
di par
X
X di ı́mpar
Como 2 · #A e
di são pares, então
di é par e para que a soma de números
di par
di ı́mpar
ı́mpares seja par, devemos ter uma quantidade par de números ı́mpares.
Exercı́cio: Prove que numa festa com 51 pessoas existe sempre uma pessoa que conhece um
número par de outras pessoas.
Introdução e definições básicas.
Passeios eulerianos
1.2
3
Passeios eulerianos
Definição 1.3. Um PASSEIO entre os nós i e j de um grafo é uma sequência alternante de nós
e arcos, começando em um dos nós i ou j e terminando no outro, tal que cada arco percorrido é incidente aos nós que o cercam na sequência. Um passeio é dito FECHADO quando começa e termina
no mesmo nó.
Um CAMINHO é um passeio que não contém nós repetidos. Dois nós estão CONECTADOS
se existe um caminho entre eles no grafo. Um grafo é dito CONEXO quando cada par de nós está
conectado, caso contrário ele é dito DESCONEXO.
Um passeio em um grafo é dito EULERIANO quando passa por todo arco exatamente uma vez.
À luz das definições acima, o Problema das pontes de Königsberg refere-se exatamente à existência
ou não de um passeio euleriano pela cidade (grafo), quando se considera as pontes como arcos e os
territórios (ilhas ou margens) como nós:
O argumento de Euler para as pontes de Königsberg: Consideremos um dos territórios
(ilhas ou margens), que chamaremos de território I. Suponhamos que o passeio não começa em I.
Então entramos em I pela primeira vez através de uma ponte que é incidente em I e saı́mos de I por
outra ponte incidente em I. Cada entrada-e-saı́da de I corresponde ao uso de duas pontes. Como I
tem um número ı́mpar de pontes incidentes, na última vez que usamos uma ponte incidente em I,
entramos em I e não podemos mais sair, ou seja, o passeio termina necessariamente em I. Assim, pelo
mesmo argumento, se o passeio começa em qualquer território, deve necessariamente terminar nos
outros três (contradição!), pois todos têm um número ı́mpar de pontes incidentes.
4
CAPÍTULO 1
O argumento anterior leva ao seguinte teorema:
Teorema 1.4. (Euler)
(a) Se um grafo conexo tem mais que dois nós com grau ı́mpar, então ele não admite um passeio
euleriano.
(b) Se um grafo conexo tem exatamente dois nós com grau ı́mpar, então ele admite passeio euleriano e todo passeio euleriano tem que começar em um desses nós de grau ı́mpar e terminar no
outro.
(c) Se um grafo conexo não tem nós com grau ı́mpar, então ele admite passeio euleriano e todo
passeio euleriano é fechado.
Exercı́cio: Prove a partir do teorema acima que um grafo conexo tem um passeio euleriano
fechado se, e somente se, todo nó tem grau par.
Exercı́cio: Quais dos grafos abaixo admitem um passeio euleriano? Em caso afirmativo, indique
um passeio euleriano.
Exercı́cio:
(a) Construa ou destrua UMA ponte em Königsberg para que se tenha um passeio euleriano
(indique o passeio).
(b) Mostre como se pode ter um passeio euleriano fechado construindo mais DUAS pontes em
Königsberg (indique o passeio).
(c) Mostre como se pode ter um passeio euleriano fechado construindo UMA ponte e destruindo
OUTRA em Königsberg.
(d) O que ocorre se destruirmos DUAS pontes em Königsberg?
Capı́tulo 2
Ciclos hamiltonianos
Problema: Seis cidades (nós) são 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 das
demais cidades, terminando a viagem na cidade de origem.
É possı́vel realizar uma viagem nas condições acima?
Definição 2.1. Um CICLO é um passeio fechado no qual apenas o nó inicial-terminal se repete.
Um CICLO HAMILTONIANO é um ciclo que contém todos os nós de um grafo.
Observações:
(a) O problema acima equivale a perguntar se o grafo formado admite um ciclo hamiltoniano.
(b) É claro que para um grafo admitir um ciclo hamiltoniano é NECESSÁRIO que ele seja conexo.
(c) Não existem resultados gerais de caracterização dos grafos que admitem ciclos hamiltonianos.
(d) Problema do caixeiro viajante: achar um ciclo hamiltoniano de custo mı́nimo, sendo o custo
de um ciclo a soma dos custos dos arcos percorridos no ciclo.
5
6
CAPÍTULO 2
Proposição 2.2. Num ciclo com três ou mais nós são percorridos exatamente dois arcos incidentes
em cada nó do ciclo.
Corolário 1. Um grafo que tenha três ou mais nós e algum nó de grau menor ou igual a 1
não admite um ciclo hamiltoniano.
Exercı́cio: Resolva o problema inicial (do vendedor e as seis cidades): indique um ciclo hamiltoniano caso exista solução ou prove que não existe ciclo hamiltoniano algum.
Exercı́cio: Responda se os grafos abaixo admitem ou não um ciclo hamiltoniano. Indique um
ciclo hamiltoniano em caso afirmativo ou prove que não admite, no caso negativo.
Exercı́cio: Um grafo G = (N, A) é dito BIPARTIDO quando seu conjunto N de nós pode ser
particionado em DOIS subconjuntos tais que nós pertencentes a um mesmo subconjuntos não são
adjacentes.
(a) Prove que se um grafo bipartido G = (N, A) admite um ciclo hamiltoniano então os dois
subconjuntos da partição de N têm o mesmo número de elementos.
(b) Conclua que o grafo abaixo NÃO ADMITE um ciclo hamiltoniano.
(c) Construa um grafo bipartido com um número par de nós, todos com grau maior ou igual a
dois, e que não admite um ciclo hamiltoniano.
Capı́tulo 3
Árvores
Problema: Através de cabos telefônicos (arcos) entre pares de cidades (nós), deseja-se configurar
uma rede de comunicações (grafo) entre as sete cidades do mapa abaixo, de modo que possa haver
comunicação entre cada par de cidades, ou seja, cada par de cidades esteja conectado por pelo menos
um caminhona rede de comunicações (o grafo é conexo).
(a) É possı́vel obter uma rede (grafo) conexa com exatamente um caminho conectando cada par
de cidades? (neste caso é fácil ver que o grafo será MINIMALMENTE CONEXO, ou seja, a remoção
de qualquer arco irá tornar o grafo desconexo).
(b) Dentre todas as redes (grafos) conexas possivelmente obtidas na letra (a) acima, é possı́vel
obter uma de menor custo (ÓTIMA)?
Definição 3.1. Uma ÁRVORE é um grafo simples tal que para cada par de nós existe exatamente
um caminho que os conecta.
7
8
CAPÍTULO 3
Observações:
(a) O problema inicial equivale a perguntar se é possı́vel formar uma árvore com os nós (cidades)
dados e, em caso afirmativo, se existe uma árvore de menor custo.
(b) Um grafo G é uma árvore se, e somente se, G é conexo e a remoção de qualquer um de seus
arcos resulta em um grafo desconexo (uma árvore é um grafo MINIMALMENTE CONEXO).
(c) Uma árvore não admte ciclos com três ou mais nós (pois se admitisse haveria mais de um
caminho conectando dois nós) e a adição de um arco ligando dois nós que não eram ligados por um
arco gera um ciclo com três ou mais nós (uma árvore é um grafo MAXIMALMENTE LIVRE DE
CICLOS COM TRÊS OU MAIS NÓS).
(EXEMPLOS)
• PROCEDIMENTO DE CRESCIMENTO DE ÁRVORE (como obter árvores)
- Comece com um simples nó.
- Repita o que se segue um número (FINITO) qualquer de vezes: Se G é o grafo até então formado,
crie um novo nó e ligue-o por um arco novo a qualquer nó de G.
Teorema 3.2. Todo grafo obtido pelo procedimento de crescimento de árvore é uma árvore e toda
árvore pode ser obtida desta maneira.
Corolário 1. Toda árvore com n nós tem n − 1 arcos.
• O ALGORÍTMO GULOSO DE KRUSKAL (encontrando a árvore ótima)
- Considere n nós e nenhum arco.
- Construa um arco de menor custo entre dois nós distintos que não estejam ligados por um arco
e de maneira que não se obtenha um ciclo com três ou mais nós.
- Repita o procedimento acima até que se tenha n − 1 arcos.
Teorema 3.3. Dados n nós e nenhum arco, o Algorı́tmo Guloso produz uma árvore de menor custo
(árvore ótima) entre todas as possı́veis árvores com os n nós inicialmente dedos.
Observação: Uma tentativa de adaptação do Algorı́tmo Guloso pode não funcionar para obter
um ciclo hamiltoniano ótimo (Problema do caixeiro viajante).
Exercı́cio: (a) USANDO O PROCEDIMENTO DE CRESCIMENTO DE ÁRVORE, resolva
a letra (a) do problema inicial, obtendo uma rede de comunicações minimalmente conexa entre as
cidades dadas. (b) Considerando os custos proporcionais às distâncias, USE O ALGORÍTMO GULOSO e obtenha uma rede de comunicações minimalmente conexa e de menor custo possı́vel (ótima)
entre as cidades dadas, resolvendo assim a letra (b) do problema inicial.
Árvores
9
Exercı́cio: Prove a Observação após o Teo 3.3
(Sugestão: 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, faça o que se pede.
- Responda se o grafo é uma árvore.
- Se o grafo não for uma árvore, justifique.
- Se o grafo for uma árvore, responda se é uma árvore de menor custo (custos proporcionais às
distâncias) considerando os nós dados. Se não for uma árvore de menor custo, exiba uma árvore de
menor custo com os nós dados.
10
CAPÍTULO 3
Referências
[1] Lovász, L. e outros, Matemática Discreta, Coleção Textos Universitários, SBM, Rio de
Janeiro, 2003.
[2] Santos, J. P. O. e outros, Introdução à Análise Combinatória, Editora Unicamp, Campinas,
2002.
11