metodos finitos em matemática - contagem e grafos (2 de 3)

Prévia do material em texto

Caṕıtulo 3
Introdução à Teoria de Grafos
Se pegarmos num mapa do Porto e colocarmos um ponto • nos locais onde duas ou
mais ruas se cruzam e um ponto também nos becos sem sáıda, o que obtemos é uma
representação daquilo a que chamaremos um grafo. Se quisermos, adicionalmente,
representar o sentido do tráfego em cada rua, podemos acrescentar uma seta, ! ou
", em cada rua de sentido único, indicando a direcção permitida, e uma seta de duas
pontas # nas ruas com ambos os sentidos. Neste caso obtemos um grafo dirigido, ou
digrafo. Tomemos agora as pessoas dessa cidade, representemo-las por pontos no plano
e tracemos uma linha entre cada par de pessoas que se conhece. Obtemos novamente a
representação de um grafo. Finalmente, consideremos uma molécula, constitúıda por
átomos, alguns dos quais ligados entre si. Temos assim mais um exemplo de um grafo.
O primeiro artigo de teoria de grafos é de 1736, da autoria do matemático súıço
Leonhard Euler, onde ele estudou o famoso problema das pontes de Königsberg. Apesar
das origens desta disciplina estarem muito ligadas a jogos e puzzles, hoje em dia a
teoria de grafos constitui uma área de investigação e uma ferramenta muito importante
em redes de transportes, qúımica, psicologia, ciências sociais, genética e ciências de
computadores, entre outras.
3.1 Definições e exemplos
Um grafo simples é um par ordenado G = (V, E), onde V é um conjunto finito cujos
elementos são denominados por vértices, e E é um conjunto de elementos do tipo
{x, y}, com x, y $ V e x %= y, chamados arestas. Dito de outra forma, E & P2(V ),
onde P2(X) designa o conjunto de todos os subconjuntos de X com dois elementos.
Usaremos ainda a notação V (G) = V e E(G) = E para o caso de a notação V e E ser
amb́ıgua.
Se ! = {x, y} $ E, dizemos que:
• a aresta ! liga ou une os vértices x e y;
38
CAPÍTULO 3. INTRODUÇÃO À TEORIA DE GRAFOS 39
• os vértices x e y são adjacentes;
• os vértices x e y são vizinhos;
• x (respectivamente y) e ! são incidentes;
• x (respectivamente y) é uma extremidade de !.
Podemos representar um grafo G no plano por um diagrama formado por pontos
e linhas, onde os pontos estão em correspondência com os vértices de G e dois pontos
são unidos por uma linha1 se e só se os vértices correspondentes determinam uma
aresta de G. Por abuso de linguagem designaremos ainda os pontos do diagrama por
vértices e as linhas entre vértices por arestas. Devemos ter o cuidado, ao representar
um grafo, de que uma aresta só passe por um vértice do diagrama se esse vértice for
uma extremidade da aresta que se está a representar, de forma a evitar ambiguidades.
Exemplo. Consideremos o grafo G = (V, E), onde:
V = {a, b, c, d, e} e E = {{a, b}, {a, d}, {a, e}, {b, c}, {b, e}, {c, d}, {d, e}}.
Abaixo apresentamos duas representações deste grafo:
a
db
c
e
b
a
c
d
e
Se permitirmos na definição de grafo que haja arestas múltiplas, isto é, pares de
vértices que sejam unidos por mais do que uma aresta, então dizemos que a estrutura
correspondente é a de um multigrafo. Mais geralmente, se num multigrafo permitir-
mos a existência de lacetes, isto é, arestas cujas duas extremidades coincidem, obtemos
a definição geral de grafo.
Exemplo. Nas duas figuras abaixo encontram-se representados um multigrafo (à es-
querda) e um grafo geral (à direita):
1curva C! sem auto-intersecções
CAPÍTULO 3. INTRODUÇÃO À TEORIA DE GRAFOS 40
Exerćıcio. Apresente uma definição de multigrafo e de grafo geral análoga à apresen-
tada para um grafo simples.
Um grafo diz-se completo se for simples e se cada par de vértices distintos formar
uma aresta. Um grafo completo com n vértices tem
!
n
2
"
= n(n!1)2 arestas e é denotado
por Kn.
Exemplo. Representações dos grafos completos K1, K2, K3, K4 e K5:
Uma outra representação de K5 é a seguinte:
Notamos que em ambas as representações que apresentámos de K5 há arestas que se
intersectam em pontos que não são vértices.
Um grafo diz-se planar se puder ser representado por um diagrama no plano de
forma a que duas arestas não se intersectem excepto em vértices comuns. Uma tal
representação diz-se um grafo plano ou uma representação planar do grafo. Pelo
exemplo anterior, os grafos completos K1, K2, K3 e K4 são planares. Veremos mais
tarde que não existe nenhuma representação planar de K5, e portanto este grafo não é
planar.
Um grafo bipartido é um multigrafo G = (V, E) cujo conjunto dos vértices admite
uma partição V = X'̇Y em dois subconjuntos X e Y de tal forma que cada aresta de
G tenha uma extremidade em X e outra em Y . O par X, Y diz-se uma bipartição de
G. Assim, G é bipartido com bipartição X, Y se e só se
({a, b} $ E a $ X )* b $ Y.
Em particular, um grafo bipartido não tem lacetes e não existem arestas entre os
vértices de X nem entre os vértices de Y .
CAPÍTULO 3. INTRODUÇÃO À TEORIA DE GRAFOS 41
É comum representar um grafo bipartido no plano com os vértices de X acima (ou
à esquerda) dos vértices de Y , ou vice-versa, embora não seja necessário fazê-lo.
Exemplo. O multigrafo representado abaixo é bipartido, com bipartição X = {a, b, c}
e Y = {t, u, v, w}
a b c
t u v w
Considere-se o grafo G representado abaixo, à esquerda. Desta representação não
é evidente que G seja bipartido. No entanto, este mesmo grafo pode também ser
representado pela figura abaixo, à direita, de onde se percebe que de facto G é bipartido,
com bipartição X = {a, c, g, h, j, k} e Y = {b, d, e, f, i}.
Este exemplo mostra que, em geral, não é óbvio concluir de uma particular re-
presentação de um grafo se este é ou não bipartido. Veremos nos exerćıcios uma
caracterização dos grafos bipartidos.
Exemplo. Seja G o grafo com V (G) = {1, 2, . . . , 20} e E(G) = {{i, j} | i, j $
V (G) e i+ j é ı́mpar}. Consideremos
X = {i $ V (G) | i é par} e Y = {i $ V (G) | i é ı́mpar}.
Então, como i+ j é ı́mpar se e só se i e j têm paridades diferentes, conclúımos que G
é bipartido, com bipartição X, Y .
Um grafo simples bipartido G com bipartição X, Y diz-se completo se cada vértice
de X for adjacente a cada vértice de Y . Assim, se |X| = n e |Y | = m, então G tem
exactamente mn arestas. Um tal grafo é denotado por Km,n.
Exerćıcio. Verifique que o grafo do exemplo anterior é o grafo bipartido completo
K10,10.
CAPÍTULO 3. INTRODUÇÃO À TEORIA DE GRAFOS 42
3.2 O primeiro resultado
O grau do vértice v do grafo G é o número deg(v) de arestas incidentes com v. Cada
lacete {v, v} contribui 2 para deg(v) uma vez que ambas as extremidades do lacete são
v. Por exemplo, no grafo completo Kn cada vértice tem grau n+1 e no grafo bipartido
Km,n existem m vértices de grau n e n vértices de grau m. A sequência de graus
de G é a sequência decrescente (d1, d2, . . . , dn), com d1 , d2 , · · · , dn , 0, formada
pelos graus de cada vértice de G.
Por exemplo, no grafo
a sequência de graus é (7, 4, 2, 2, 2, 2, 1, 0).
O primeiro resultado de teoria de grafos que vamos ver, da autoria de Euler, é por
vezes referido como o lema dos apertos de mão, por razões que serão fáceis de adivinhar.
Teorema 3.1. Seja G um grafo. Então
#
v"V
deg(v) = 2|E|.
Em particular, o número de vértices de grau ı́mpar num grafo é par.
Demonstração. Cada aresta de G, incluindo os lacetes, contribui com 2 para a soma
dos graus dos vértices de G, provando a igualdade enunciada. Logo, a soma dos graus
dos vértices de G é par e portanto o número de vértices de grau ı́mpar também terá
de ser par.
Exerćıcio. Seja G um grafo com n vértices e exactamente n+ 1 arestas. Mostre que
ou G tem um vértice de grau 1 ou um vértice isolado (isto é, um vértice que não é
incidente em nenhuma aresta).
Exerćıcio. É posśıvel que, num grupo de sete pessoas, cada uma delas conheça exac-
tamente três das restantes pessoas do grupo?
Um grafo G diz-se k-regular se deg(v) = k para todo o v $ V .
Exerćıcio.Mostre que se G é um grafo k-regular então ou k é par ou |V (G)| é par.
CAPÍTULO 3. INTRODUÇÃO À TEORIA DE GRAFOS 43
Exemplo. (Lema de Sperner) Este exerćıcio destina-se a provar o caso bi-dimensional
do chamado lema de Sperner, que pode ser usado para provar o teorema do ponto fixo
de Brower.
Seja T um triângulo no plano. Dizemos que uma decomposição de T num número
finito de triângulos contidos em T é simplicial se dois quaisquer triângulos dessa decom-
posiçao, ou não se intersectam, ou se intersectam num vértice comum ou se intersectam
numa aresta comum.
Dada uma decomposição simplicial de T , dizemos que uma coloração dos vértices
dos triângulos da decomposição com as cores 0, 1 e 2 é própria se:
• são atribúıdas aos três vértices de T as cores 0, 1 e 2, por uma qualquer ordem;
• aos vértices da decomposição que ocorrem sobre o lado de T que liga os vértices
de T de cores i e j são atribúıdas indiferentemente as cores i e j
Um triângulo da decomposição cujos vértices tenham sido coloridos com as três cores
diz-se um triângulo especial.
Na figura abaixo temos à esquerda uma decomposição simplicial de um triângulo
e à direita uma coloração própria dos vértices dos triângulos dessa decomposição. Há
três triângulos especiais na coloração apresentada.
Lema de Sperner. Qualquer coloração própria de uma decomposição simplicial de
um triângulo tem um número ı́mpar de triângulos especiais. Em particular existe
sempre pelo menos um triângulo especial.
Denotemos os triângulos da decomposição por T1, T2, . . . , Tn e o exterior do triângulo
T por T0. Constrúımos um grafo simples G com V (G) = {v0, v1, . . . , vn}, em corres-
pondência com as regiões T0, . . . , Tn, e unimos os vértices vi e vj se Ti - Tj for uma
aresta comum a estes dois triângulos com as cores 0 e 1.
É fácil de ver que o vértice v0 tem grau ı́mpar. Logo, pelo Teorema 3.1, de entre
os restantes vértices v1, . . . , vn há um número ı́mpar deles com grau ı́mpar. Além
CAPÍTULO 3. INTRODUÇÃO À TEORIA DE GRAFOS 44
disso, nenhum destes pode ter grau 3, logo os de grau ı́mpar têm grau 1. Como, para
1 . i . n, deg(vi) = 1 se e só se o triângulo Ti é especial, fica assim provado o lema
de Sperner.
Dizemos que dois grafos G e G# são isomorfos se existir uma bijecção
" : V (G)! V (G#)
tal que, para todo o x, y $ V (G), o número de arestas entre x e y em G é igual ao
número de arestas entre "(x) e "(y) em G#. Se G e G# forem ambos grafos simples, esta
condição traduz-se simplesmente em
(x, y $ V (G) {x, y} $ E(G) )* {"(x), "(y)} $ E(G#).
Dizemos que " é um isomorfismo entre G e G# e escrevemos G / G#. Esta noção induz
uma relação de equivalência no conjunto dos grafos, que nos permite identificar dois
grafos isomorfos.
É fácil de ver que, se G / G#, então
• |V (G)| = |V (G#)| e |E(G)| = |E(G#)|;
• G é simples se e só se G# é simples;
• G é bipartido se e só se G# é bipartido;
• G é completo se e só se G# é completo;
• G é planar se e só se G# é planar;
• G e G# têm a mesma sequência de graus.
No entanto, o reciproco destas afirmações é falso, em geral.
Exemplos. 1. Os grafos representados abaixo são isomorfos, sendo ambos repre-
sentações de K4.
2. Os grafos abaixo têm o mesmo número de vértices e arestas, mas não são isomorfos
pois têm sequências de graus distintas.
CAPÍTULO 3. INTRODUÇÃO À TEORIA DE GRAFOS 45
3. Os grafos abaixo têm a mesma sequência de graus. No entanto não são isomorfos
porque no grafo G existem três vértices, cada um deles unido aos outros dois, e
tal não acontece com o grafo G#. Outra forma de concluir que não são isomorfos
é notando que G# é bipartido e isomorfo a K3,3, ao passo que G não é bipartido.
Seja G = (V, E) um grafo. Um subgrafo de G é um grafo H = (V #, E #) tal que
V # & V e E # & E. De forma equivalente, um subgrafo de G é um par H = (V #, E #)
que satisfaz:
• V # & V e E # & E;
• as extremidades de qualquer aresta ! $ E # são elementos de V #.
O subgrafo H diz-se:
• induzido de G se E # for o conjunto de todas as arestas de G com ambas as
extremidades em V #. Nesse caso denotamos H por G(V #).
• gerador de G se V # = V .
Assim, um subgrafo induzido de G obtém-se escolhendo um subconjunto V # de V e
tomando todas as arestas de G que ligam vértices de V #. Um subgrafo gerador de G
obtém-se tomando todos os vértices de G e algumas (ou nenhumas, ou todas) arestas
de G.
Exemplo. Consideremos o grafo G representado por:
Na figura abaixo temos um subgrafo de G que não é induzido nem gerador (es-
querda), um subgrafo induzido, que não é gerador (centro), e um subgarfo gerador que
não é induzido (direita).
CAPÍTULO 3. INTRODUÇÃO À TEORIA DE GRAFOS 46
Dado um conjunto de arestas A & E, o grafo G+A é o subgrafo gerador de G com
E(G + A) = E(G) \ A. Se A = {!} escrevemos também G + ! em vez de G + {!}.
Dado um conjunto de vértices X & V , o grafo G+X é o grafo induzido G(V \X). Se
X = {v} escrevemos ainda G+ v em vez de G+ {v}.
CAPÍTULO 3. INTRODUÇÃO À TEORIA DE GRAFOS 47
3.3 Passeios em grafos e conexão
Um passeio de comprimento m num grafo G é uma sequência da forma
P = v0!1v1!2v2 · · ·!mvm (3.1)
onde, para cada 1 . i . m, v0, vi $ V (G), !i $ E(G) e !i tem extremidades vi!1 e vi.
Dizemos ainda que P é um passeio de v0 a vm. Se G for simples, podemos simplesmente
denotar P por
v0 + v1 + · · ·+ vm,
desde que {vi!1, vi} $ E(G) para todo o i. Se v0 = vm dizemos que o passeio P é
fechado. No caso de m = 0 temos o passeio trivial v0, de comprimento 0.
O passeio inverso do passeio P em (3.1) é o passeio vm!mvm!1!m!1 · · · v1!1v0,
de vm a v0, denotado por P!1 e obtido invertendo a ordem por que são percorridos os
vértices e arestas de P . Se P # = v#0!
#
1v
#
1 · · ·!#lv#l é outro passeio em G tal que vm = v#0,
então o passeio v0!1v1 · · ·!mvm!#1v#1 · · ·!#lv#l, de v0 a v#l, obtido por concatenação de P
e P #, é denotado por PP #. Uma secção do passeio (3.1) acima é um passeio da forma
vi!i+1vi+1 · · ·!jvj, com i . j; dizemos que esta é a secção (vi, vj) de P .
Um atalho, ou trilho, é um passeio em que todas as arestas !1, . . . ,!m são dis-
tintas e um atalho fechado é chamado um circuito. Finalmente, dizemos que P é um
caminho se P for um atalho e todos os seus vértices forem distintos, com excepção
posśıvel de se ter v0 = vm. Um caminho fechado designa-se por ciclo.
Um lacete é um ciclo de comprimento 1 e duas arestas entre o mesmo par de
vértice determinam um ciclo de comprimento 2. Num grafo simples, qualquer ciclo
tem comprimento pelo menos 3.
Exerćıcio. Mostre que, num grafo, se existe um passeio entre dois vértices estão existe
também um caminho entre esses vértices.
O grafo G diz-se conexo se, dados quaisquer dois vértices x e y em G, existe um
passeio (ou, o que é equivalente, um caminho) entre x e y. Caso contrário, G diz-se
desconexo.
É fácil de ver que é posśıvel decompor de forma única qualquer grafo num conjunto
de subgrafos induzidos G1 = (V1, E1), . . ., Gk = (Vk, Ek) tais que, dados x $ Vi e y $ Vj,
existe um caminho entre x e y em G se e só se i = j. Os subgrafos G1, . . . , Gk dizem-se
as componentes conexas de G e o número k de componentes conexas denota-se por
#(G). É claro que #(G) = #(G#) se os grafos G e G# forem isomorfos.
CAPÍTULO 3. INTRODUÇÃO À TEORIA DE GRAFOS 48
Exemplo. O seguinte grafo é desconexo, tendo três componentes conexas.
Podemos agora formular a noção de distância num grafo. Sejam x e y vértices de
uma mesma componente conexa do grafo G. Definimos a distância entre x e y pela
fórmula
d(x, y) = min{k | existe um passeio em G de comprimento k entre x e y}.
É claro que d(x, y) = 0 )* x = y e que qualquer passeio entre x e y de comprimento
d(x, y) é necessariamente um caminho.
Exerćıcio. Mostre que a distância, definida para grafos conexos, é de facto uma
métrica. Mostre aindaque esta métrica tem a seguinte propriedade adicional: se
d(x, y) > 1 então existe z %= x, y tal que d(x, y) = d(x, z) + d(z, y).
Podemos agora enunciar um resultado que permite classificar os grafos bipartidos:
Teorema 3.2. Um grafo é bipartido se e só se todos os seus ciclos tiverem comprimento
par.
Demonstração. Seja G um grafo. Se G for bipartido, então é imediato que qualquer
ciclo em G tem de ter comprimento par. Suponhamos agora que todos os ciclos de G
têm comprimento par. Podemos também assumir que G é conexo, já que um grafo é
bipartido se todas as suas componentes conexas o forem.
Seja x $ V (G). Definimos a seguinte partição de V (G):
X = {y $ V (G) | d(x, y)é par};
Y = {y $ V (G) | d(x, y)é ı́mpar}.
Resta mostrarmos que X, Y é uma bipartição de G. Suponhamos, por redução ao
absurdo, que existem vértices a, b $ X ligados por uma aresta ! $ E(G) (o caso
a, b $ Y é análogo). Sejam C1 e C2 caminhos de comprimento mı́nimo de x a a e de
x a b, respectivamente. Como estes caminhos têm pelo menos o vértice x em comum,
existe um último vértice z em comum a ambos, de forma a que estes caminhos têm
a forma x · · · z · · · a e x · · · z · · · b, com z · · · a e z · · · b caminhos sem
vértices em comum, para além de z. Como C1 e C2 são caminhos de comprimento
mı́nimo, os seus caminhos iniciais entre x e z têm forçosamente o mesmo comprimento.
Logo, os comprimentos dos caminhos entre z e a e entre z e b obtidos de C1 e C2,
CAPÍTULO 3. INTRODUÇÃO À TEORIA DE GRAFOS 49
respectivamente, têm a mesma paridade. Mas então o ciclo z · · · a!b · · · z obtido
destes caminhos e da aresta ! tem comprimento ı́mpar, o que é absurdo. Logo X e Y
constituem de facto uma bipartição de G.
Vamos finalizar esta secção com uma outra forma de representar um grafo, a menos
de isomorfismo, que é particularmente útil para estudar algumas questões de conexão
em grafos (ver exerćıcios).
Seja G um grafo com |V (G)| = n. Vamos descrever G por meio de uma ma-
triz simétrica n 0 n com entradas em N. Começamos por ordenar os vértices de G:
v1, . . . , vn. A matriz de adjacência de G é a matriz A = (aij)1$i,j$n cuja entrada
aij é o número de arestas entre os vértices vi e vj. Assim, a entrada aii é o número
de lacetes no vértice vi. Se G for simples então as entradas não nulas de A são todas
iguais a 1 e a diagonal de A é constitúıda unicamente por zeros.
Exemplo. Um grafo com lacetes e a sua matriz de adjacência, relativamente à ordem
dos vértices indicada:
$
%%%%%%&
0 1 2 0 1 0
1 1 0 0 2 0
2 0 0 1 1 1
0 0 1 1 2 2
1 2 1 2 0 0
0 0 1 2 0 0
'
(((((()
CAPÍTULO 3. INTRODUÇÃO À TEORIA DE GRAFOS 50
3.4 Exerćıcios
1. Determine cada um dos 11 grafos simples não isomorfos com 4 vértices e represente-
os de forma planar.
2. Existe algum grafo cuja sequência de graus seja (4, 4, 3, 2, 2)?
3. Existe algum grafo simples cuja sequência de graus seja (4, 4, 4, 2, 2)? E algum
multigrafo?
4. Mostre que num grafo simples com n , 2 vértices há pelo menos dois vértices
com o mesmo grau. Este resultado é válido para multigrafos?
5. Seja (d1, . . . , dn) uma sequência de n inteiros não negativos tal que a soma d1 +
· · · + dn é par. Mostre que existe um grafo (geral) que tem esta sequência como
a sua sequência de graus. Descreva um algoritmo para a construção de um tal
grafo.
6. Apresente o diagrama de um grafo simples conexo cuja sequência de graus seja
(5, 4, 3, 3, 3, 3, 3, 2, 2).
7. Dê exemplo de um grafo simples G com 8 vértices tal que
(a) G é conexo e 3-regular;
(b) G é desconexo e 3-regular;
(c) G é 1-regular.
8. Qual é o número máximo e mı́nimo de arestas de um grafo simples com n vértices?
E qual é o valor máximo e mı́nimo do grau de um seu vértice?
9. Mostre que um grafo simples com n vértices e com pelo menos
(n+ 1)(n+ 2)
2
+ 1
arestas é necessariamente conexo. Dê um exemplo de um grafo simples desconexo
com n vértices e cujo número de arestas seja uma unidade inferior ao número
indicado acima.
10. Mostre que:
(a) Dois grafos isomorfos têm o mesmo número de vértices e de arestas e a
mesma sequência de graus.
(b) As afirmações rećıprocas das anteriores são falsas, mesmo para grafos sim-
ples.
CAPÍTULO 3. INTRODUÇÃO À TEORIA DE GRAFOS 51
11. Mostre que dois quaisquer grafos conexos, 2-regulares e com o mesmo número de
vértices são isomorfos.
12. Para cada par de grafos representados abaixo diga, justificando, se são ou não
isomorfos. Construa a matriz de adjacência de cada um deles.
13. Para cada par de grafos representados abaixo diga, justificando, se são ou não
isomorfos. Construa a matriz de adjacência de cada um deles.
14. Dos grafos seguintes há exactamente dois que são isomorfos. Diga, justificando,
quais são.
15. Dado um grafo simples G = (V, E), definimos o complementar de G como
sendo o grafo G com V (G) = V e E(G) = P2(V ) \ E.
(a) Determine o complementar dos grafos Kn e Km,n.
(b) Dê exemplos de grafos isomorfos ao seu complementar.
(c) Mostre que o complementar de um grafo desconexo é um grafo conexo.
16. Seja G um grafo com 9 vértices tal que
*
v"V (G) deg(v) , 27. Mostre que G tem
algum vértice de grau pelo menos 4.
17. Seja G um grafo simples, conexo e regular, com exactamente 22 arestas. Quantos
vértices é que G pode ter? Justifique.
18. Seja G um grafo simples, conexo e regular. Será que todos os seus vértices
têm necessariamente o mesmo número de segundos vizinhos (isto é, vértices à
distância 2 deles)?
CAPÍTULO 3. INTRODUÇÃO À TEORIA DE GRAFOS 52
19. Mostre que um grafo G com um vértice de grau pelo menos 1 e cujos vértices
restantes têm todos grau pelo menos 2 contém um ciclo de comprimento m , 1.
E se G tiver dois vértices de grau 1 e os restantes de grau pelo menos 2?
20. Mostre que qualquer grafo simples com 10 vértices e 28 arestas contém um ciclo
de comprimento 4.
21. Mostre que qualquer grafo simples e k-regular, com k , 2, contém um ciclo de
comprimento não inferior a k + 1.
22. Sejam x e y vértices de um grafo, e suponhamos que existe um passeio fechado
contendo x e y. Será que existe necessariamente também um circuito contendo
x e y?
23. Sejam x e y vértices de um grafo, e suponhamos que existe um circuito contendo
x e y. Será que existe necessariamente também um ciclo contendo x e y?
24. Seja A um atalho num grafo, entre os vértices x e y. Mostre que existe uma
partição das arestas de A de forma a que uma das partes determina um caminho
entre x e y e as restantes determinam ciclos. Em particular, qualquer circuito
pode ser decomposto em ciclos.
25. Seja G um grafo e seja G# o grafo obtido de G por remoção de todos os lacetes
e todas as cópias, menos uma, de arestas com multiplicidade maior do que 1.
Mostre que:
(a) G é conexo se e só se G# é conexo;
(b) G é planar se e só se G# é planar.
26. Seja G um grafo com precisamente dois vértices x e y de grau ı́mpar. Seja G% o
grafo obtido acrescentando a G uma nova aresta entre os vértices x e y. Mostre
que G é conexo se e só se G% é conexo.
27. Mostre que um grafo é bipartido se e só se cada uma das suas componentes
conexas o for.
28. Sejam m e n inteiros positivos. Para que valores de a e b é que os grafos bipartidos
completos Km,n e Ka,b são isomorfos?
29. Qual é o menor número de arestas que é necessário retirar a K5 de forma a que
o grafo resultante seja bipartido?
30. Uma ponte ou aresta de corte num grafo G é uma aresta ! $ E(G) tal que
#(G + !) > #(G), onde G + ! é o grafo obtido após eliminar a aresta ! de G.
Mostre que:
CAPÍTULO 3. INTRODUÇÃO À TEORIA DE GRAFOS 53
(a) #(G) . #(G+ !) . #(G) + 1 para qualquer ! $ E(G).
(b) Se ! $ E(G) é uma ponte então #(G+ !) = #(G) + 1.
(c) Se todos os vértices de G têm grau par então G não tem pontes.
31. Seja G um grafo bipartido e k-regular, para algum k , 2. Mostre que G não tem
pontes.
32. Mostre que se o grafo G é simples e conexo, mas nãoé completo, então existem
três vértices distintos u, v e w tais que {u, v}, {v, w} $ E(G) mas {u, w} /$ E(G).
33. Seja V = {1, . . . , 20} o conjunto dos primeiros 20 inteiros positivos. Considere os
seguintes grafos simples cujo conjunto dos vértices é V e cujo conjunto de arestas
está especificado abaixo. Para cada um destes grafos determine se ele é ou não:
(i) conexo, especificando as componentes conexas no caso de ser desconexo;
(ii) bipartido, especificando uma bipartição em caso afirmativo.
(a) {a, b} é uma aresta se e só se a + b é par.
(b) {a, b} é uma aresta se e só se a + b é ı́mpar.
(c) {a, b} é uma aresta se e só se ab é par.
(d) {a, b} é uma aresta se e só se ab é ı́mpar.
(e) {a, b} é uma aresta se e só se ab é um quadrado perfeito.
(f) {a, b} é uma aresta se e só se a+ b é diviśıvel por 3.
34. Seja A a matriz de adjacência de um grafo de vértices v1, v2, . . . , vn. Mostre
que a entrada da matriz Ak da linha i e coluna j é o número de passeios de
comprimento k entre os vértices vi e vj. Use este resultado para determinar,
em termos da matriz de adjacência e das suas potências, a distância entre dois
vértices num grafo conexo.
CAPÍTULO 3. INTRODUÇÃO À TEORIA DE GRAFOS 54
3.5 Grafos Eulerianos
Nesta secção iremos estudar o problema, certamente familiar, da possibilidade de traçar
um desenho sem levantar o lápis do papel e sem repetir nenhuma linha. Desenhos como
os seguintes são t́ıpicos exemplos que o leitor deverá tentar desenhar da forma descrita
acima reavivando assim a memória:
Após algumas tentativas, percebemos que é fácil seguir o procedimento indicado
na figura da esquerda e na figura ao centro, embora na figura da esquerda consigamos
sempre acabar no ponto inicial, o que parece não ser posśıvel com a do centro. Também
parece ser de todo imposśıvel traçar a figura da direita sem ter de levantar o lápis ou
traçar duas vezes a mesma linha. Como poderemos justificar estas afirmações?
Outro problema análogo a este é o famoso Problema das pontes de Königsberg, que
foi resolvido por Euler num artigo de 1736, considerado o primeiro artigo em teoria de
grafos.
No tempo de Euler, Königsberg era uma cidade da Prússia, mas actualmente o nome
da cidade é Kalinegrado e situa-se na Rússia. O rio Pregel (actualmente Pregolya)
passa por Königsberg onde se bifurca, criando duas ilhas no centro da cidade. As ilhas
estão ligadas ao resto da cidade por sete pontes e os seus habitantes pretendiam saber
se seria posśıvel fazer um passeio pela cidade de forma a passar por cada uma das
pontes exactamente uma vez, regressando no final do passeio ao ponto de partida (ver
esquema abaixo onde o rio aparece a cinzento e as pontes estão assinaladas com letras
minúsculas).
CAPÍTULO 3. INTRODUÇÃO À TEORIA DE GRAFOS 55
Neste problema, o comprimento das pontes, a distância entre elas e a precisa lo-
calização dos indiv́ıduos em cada uma das regiões determinadas pelo rio é irrelevante.
A informação relevante é somente a descrição das possibilidades de transitar de uma
região a outra usando as pontes. Assim, podemos modelar este problema usando um
grafo, cujos vértices são as quatro regiões determinadas pelo rio e cujas arestas corres-
pondem às pontes, sendo o número de arestas entre duas regiões igual ao número de
pontes que as ligam:
D
C
A
B
Um outro exemplo t́ıpico de um problema que pode ser traduzido em termos do
estudo de grafos é o de um carteiro que deseja, começando a sua jornada de trabalho
na estação de correios, percorrer todas as ruas que lhe foram destinadas e entregar
o correio. Ao final do dia deve regressar à estação de correios de onde partiu. Será
que pode fazê-lo sem ter de percorrer duas vezes a mesma rua? Para começar, pode-
mos representar as ruas e as suas intersecções por um grafo, como foi já referido na
introdução deste caṕıtulo. Em linguagem de teoria de grafos, todos estes problemas
se traduzem na seguinte questão: Existe no grafo dado um circuito contendo todas as
arestas do grafo? Não existindo um circuito, existe um atalho?
Motivados pelo problema das pontes de Königsberg, e pelo matemático que o re-
solveu, dizemos que um atalho num grafo é Euleriano se contiver todas as arestas do
grafo. Dizemos ainda que um grafo é Euleriano se for conexo e possuir algum circuito
Euleriano.
Suponhamos então que A = v0!1v1 · · ·!mvm é um circuito Euleriano no grafo co-
nexo G, onde vm = v0. Seja v um qualquer vértice de G. Como G é conexo, deg(v) > 0
(excepto no caso trivial em que |V (G)| = 1) e todas as arestas incidentes em v ocorrem
em A. Em particular, v é um dos vértices de A. Estudamos primeiro o caso v %= v0.
Em cada ocorrência de v em A, este vértice é precedido e sucedido por uma aresta
que lhe é incidente, e todas as arestas incidentes em v ocorrem desta forma. (Note-se
que este argumento é consistente com a definição de grau de um vértice no que toca
aos lacetes.) Resulta então que deg(v) é par. Se v = v0, então as ocorrências de v0
na secção (v1, vm!1) de A contribuem com um número par de arestas para deg(v0) e
as ocorrências de v0 como extremidade inicial e final de A contribuem exactamente
com 2 para deg(v0). Em qualquer dos casos, deg(v) é par. Logo, num grafo Euleriano
todos os vértices têm grau par. Esta conclusão permite já concluir que o problema das
CAPÍTULO 3. INTRODUÇÃO À TEORIA DE GRAFOS 56
pontes de Königsberg tem solução negativa, uma vez que os quatro vértices do grafo
correspondente têm grau ı́mpar.
Vamos ver de seguida que a condição necessária que acabámos de encontrar para que
um grafo seja Euleriano é também suficiente. Começamos com um lema de interesse
independente.
Lema 3.3. Seja G um grafo em que deg(v) é par, para todo o v $ V (G). Então, dada
! $ E(G), existe um ciclo em G que contém !.
Demonstração. Sejam v0 e v1 as extremidades de !. Se v0 = v1 então v0!v1 é um
ciclo contendo !. Caso contrário, seja Ai = v0!1v1 · · · vi!1!ivi um atalho com !1 = !,
i , 1 e v0 %= vi. Como o grau de vi é ı́mpar em Ai e par em G, existe alguma aresta
!i+1 incidente com vi e diferente de !1, . . . ,!i. Seja vi+1 a outra extremidade de !i+1.
Obtemos assim um atalho Ai+1 = Aivi!i+1vi+1 de comprimento i + 1. Como este
procedimento não pode ser implementado indefinidamente, existe algum k , 2 tal que
v0 = vk e Ak é um circuito que contém a aresta !. Pelo exerćıcio 24 da secção 3.4, este
atalho é união de ciclos, algum dos quais conterá !.
Teorema 3.4. Seja G um grafo conexo. Então G é Euleriano se e só se o grau de
cada um dos seus vértices for par.
Demonstração. Já vimos que se G for Euleriano então deg(v) é par, para todo o v $
V (G). Consideramos agora o caso de G ser conexo e todos os seus vértices terem grau
par. Faremos a prova por indução sobre o número de arestas de G.
Se G não tiver arestas então, uma vez que é conexo, G é constitúıdo por um único
vértice e o atalho trivial sem arestas é um circuito Euleriano em G. Suponhamos então
que G tem alguma aresta. Pelo lema anterior, existe um ciclo C em G de comprimento
não nulo. No grafo G+C todos os vértices têm ainda grau par, uma vez que o número
de arestas de C incidentes com cada vértice é par. Além disso, G + C tem menos
arestas do que G e podemos assim aplicar a hipótese de indução a cada uma das l , 1
componentes conexas de G+C. Obtemos assim l circuitos tais que cada aresta de G+C
ocorre uma vez em precisamente um destes circuitos. Além disso, por construção, cada
componente conexa de G+C tem pelo menos um vértice em comum com C. Podemos
agora construir um circuito Euleriano em G da seguinte forma: Começamos a percorrer
C até chegar ao primeiro vértice em comum com algum dos circuitos, digamos C1; desse
vértice percorremos o circuito C1, voltando novamente ao vértice e prosseguimos com
o circuito C até encontrar um vértice comum a algum dos restantes circuitos, digamosC2; desse vértice percorremos C2 e prosseguimos assim até percorrer todos os circuitos
C1, . . . , Cl e fechar o circuito C. Este novo circuito é Euleriano uma vez que C e
C1, . . . , Cl não têm arestas em comum e cada aresta de G pertence a algum destes
circuitos.
CAPÍTULO 3. INTRODUÇÃO À TEORIA DE GRAFOS 57
Exemplo. Ilustração do processo indutivo da prova do Teorema 3.4.
Começando no grafo G com o circuito C, cuja sequência de arestas é abfghl, ob-
temos em G + C as componentes conexas C1, C2 e C3, que têm circuitos Eulerianos
dados pelas sequências de arestas cde, jki e m, respectivamente. A construção do
teorema anterior permite formar o circuito Euleriano em G cuja sequência de arestas
é bcdefghijklma.
Podemos dar ainda outra caracterização dos grafos Eulerianos:
Corolário 3.5. Seja G um grafo conexo. As seguintes condições são equivalentes:
(a) G é Euleriano;
(b) deg(v) é par para todo o v $ V (G);
(c) Existem ciclos C1, . . . , Ck, todos subgrafos de G, tais que:
(i) E(G) = 'ki=1E(Ci);
(ii) E(Ci) - E(Cj) = 1 para i %= j.
Demonstração. Pelo Teorema 3.4 sabemos já que (a) e (b) são equivalentes. Basta-nos
portanto mostrar as implicações (a) =* (c) e (c) =* (b).
Suponhamos que G é Euleriano. Então existe um circuito C contendo todas as
arestas de G. Pelo exerćıcio 24 da secção 3.4, esse circuito pode ser decomposto em
ciclos C1, . . . , Ck, de forma a que 'ki=1E(Ci) = E(C) = E(G). Além disso, como em C
não há arestas repetidas, E(Ci) - E(Cj) = 1 se i %= j.
Suponhamos agora que (c) se verifica. Dado v $ V (G), o grau de v pode ser calcu-
lado somando o número de arestas incidentes com v em cada um dos ciclos C1, . . . , Ck.
Como o número de arestas incidentes com um vértice num ciclo é par, resulta que
deg(v) é par, sendo a soma de k números pares.
Vamos agora descrever um algoritmo que permitirá, sempre que G seja um grafo
Euleriano, construir um circuito Euleriano em G. Recordamos dos exerćıcios que uma
ponte num grafo G é uma aresta ! $ E(G) tal que #(G+ !) > #(G).
CAPÍTULO 3. INTRODUÇÃO À TEORIA DE GRAFOS 58
Algoritmo de Fleury
Seja G um grafo Euleriano.
Passo 1.
• Escolher um vértice v0 $ V (G).
• Definir A0 = v0.
• Se deg(v0) = 0 então G = ({v0}, 1) e A0 é um circuito Euleriano em G; parar.
Caso contrário, prosseguir para o Passo 2.
Passo 2.
• Dado o atalho Ai = v0!1v1 · · ·!ivi, com i , 0, escolher !i+1 $ E(G)\{!1, . . . ,!i}
tal que:
– !i+1 é incidente em vi;
– se posśıvel, !i+1 não é uma ponte do grafo G+ {!1, . . . ,!i}.
• Definir Ai+1 = Aivi!i+1vi+1, onde vi+1 é a outra extremidade de !i+1.
Passo 3.
Parar se Ai+1 contém todas as arestas de G. Caso contrário, voltar ao Passo 2,
substituindo i por i + 1.
Observações. 1. No algoritmo de Fleury, a condição “se posśıvel, !i+1 não é uma
ponte do grafo G+ {!1, . . . ,!i}” significa que só escolhemos uma ponte do grafo
G+ {!1, . . . ,!i} se todas as arestas incidentes em vi nesse grafo forem pontes.
2. Não é de todo óbvio que este algoritmo termine sempre com um circuito Euleriano
se o grafo em que é aplicado for Euleriano. Esse facto será provado adiante. No
entanto, um argumento semelhante ao usado no prova do Teorema 3.4 mostra
que, no Passo 2, se não houver mais arestas incidentes em vi então ou G não é
Euleriano ou vi = v0.
Exemplo. Aplicando o algoritmo de Fleury ao grafo
CAPÍTULO 3. INTRODUÇÃO À TEORIA DE GRAFOS 59
obtemos, por exemplo, o seguinte atalho Euleriano:
a7d10a5d6a2d5a4d9a7d12a8d8a3d2a1d3a8d11a6d7a1d1a2d4a7
Note-se que, ao longo da aplicação do algoritmo de Fleury a este grafo, verifica-se
sempre que as componentes conexas de G+ {!1, . . . ,!i} são todas vértices de grau 0,
com excepção posśıvel da componente conexa contendo o vértice vi. É esta propriedade,
válida em geral, que faz com que o algoritmo de Fleury funcione.
Teorema 3.6. Se G for um grafo Euleriano então o algoritmo de Fleury termina com
um circuito Euleriano de G.
Demonstração. Seja então G um grafo Euleriano. Usaremos a notação introduzida
no algoritmo de Fleury: Ai = v0!1v1 · · ·!ivi é o atalho constrúıdo na i-ésima imple-
mentação do passo 2 no algoritmo. Definimos ainda G0 = G e Gi = G+ {!1, . . . ,!i},
para i , 1.
Pela observação que se seguiu à descrição do algoritmo, basta mostrar que, ao longo
da aplicação do algoritmo, a seguinte propriedade (Pi) é válida: “As componentes
conexas de Gi são todas vértices de grau 0, com excepção posśıvel da componente
conexa que contém o vértice vi”. Faremos a prova por indução sobre i. (P0) verifica-se,
já que G é conexo. Suponhamos então que (Pi) se verifica e vejamos que, ao passar de
Ai para Ai+1, (Pi+1) é ainda válida.
Se v0 = vi então, para cada v $ V (G), há um número par de arestas em Ai
incidentes em v (cada lacete é contado como duas arestas). Logo, como deg(v) é par
em G, resulta que v ainda tem grau par em Gi. Se v0 %= vi um racioćınio análogo
mostra que, em Gi, v0 e vi têm grau ı́mpar ao passo que os restantes vértices têm grau
par.
Suponhamos primeiro que v0 %= vi e que deg(vi) = 1 em Gi. Então existe uma única
aresta em Gi incidente com vi, digamos e $ E(G). Pelo algoritmo de Fleury, temos de
escolher !i+1 = e, apesar de e ser uma ponte de Gi. Ao fazê-lo, a componente conexa
de vi em Gi separa-se em duas componentes conexas de Gi+1: uma contendo apenas o
vértice isolado vi e outra contendo o vértice vi+1, a outra extremidade de !i+1.
Logo, neste caso (Pi+1) ainda se verifica.
Suponhamos agora que v0 %= vi e que deg(vi) %= 1 em Gi. Então deg(vi) , 3 em Gi.
Vamos mostrar que, neste caso, é posśıvel escolher uma aresta de Gi incidente com vi
que não é uma ponte em Gi. Desta forma, como não serão criadas novas componentes
conexas em Gi+1, (Pi+1) ainda será válida. Se existir um lacete em vi, não há nada a
CAPÍTULO 3. INTRODUÇÃO À TEORIA DE GRAFOS 60
provar. Caso contrário, basta mostrarmos que se deg(vi) , 2 em Gi então existe no
máximo uma ponte em Gi incidente com vi.
Suponhamos, por redução ao absurdo, que existem duas pontes e# e f # em Gi inci-
dentes com vi e sejam u e v, respectivamente, as outras extremidades destas arestas.
Então, no grafo H = Gi + {e#, f #}, o grau de vi ainda é ı́mpar (é igual ao seu grau em
Gi subtráıdo de 2), os graus de u e v diminúıram em 1 relativamente a Gi e há pelo
menos três componentes conexas: uma delas contendo vi, outra contendo u e outra
contendo v, digamos C1, C2 e C3, respectivamente (ver figura acima).
Como estamos a assumir que v0 %= vi, estes são os únicos vértices de grau ı́mpar
em Gi. Se v0 %= u e v0 %= v, então existem exactamente quatro vértices de grau ı́mpar
em H, v0, vi, u e v, o que é absurdo pois tal implicaria que alguma das componentes
conexas C1, C2 e C3 teria um único vértice de grau ı́mpar. Se v0 = u (o caso v0 = v é
idêntico) então haverá em H exactamente dois vértices de grau ı́mpar, vi e v, o que é
absurdo pois assim cada uma das componentes conexas C1 e C3 teria exactamente um
vértice de grau ı́mpar. Logo, alguma das arestas e# ou f # não é ponte em Gi e (Pi+1) é
válida.
Resta estudar o caso v0 = vi. Neste caso, todos os vértices de Gi têm grau par. Em
particular, vi tem grau par. Se deg(vi) = 0 em Gi então, por (Pi), Gi não tem arestas e
Ai é um circuito Euleriano. Caso contrário, deg(vi) , 2 e podemos usar um argumento
análogo ao apresentado acima para mostrar que nenhuma das arestas incidentes com
vi em Gi é uma ponte. Logo, (Pi+1) é válida.
Fica assim provado por indução que (Pi) se verifica para todo o i , 0, o que mostra
a eficácia do algoritmo de Fleury.
Observação. Pela prova apresentada acima verificamos também que se G é Euleriano
então no algoritmo de Fleury só somos forçados a escolher uma ponte se deg(vi) = 1
em Gi.
Temos agora uma caracterização completa dos grafos Eulerianos e um algoritmo
que permite construir sempre um circuito Euleriano num tal grafo. Noentanto, há
grafos conexos que, não sendo Eulerianos, têm atalhos Eulerianos. É o caso do grafo
seguinte:
CAPÍTULO 3. INTRODUÇÃO À TEORIA DE GRAFOS 61
De seguida veremos como identificar estes grafos.
Teorema 3.7. Um grafo conexo tem atalhos Eulerianos não fechados se e só se tem
exactamente dois vértices de grau ı́mpar. Nesse caso, qualquer atalho Euleriano começa
num desses vértices e termina no outro.
Demonstração. Seja G um grafo conexo.
Se A = v0!1v1 · · ·!mvm for um atalho Euleriano em G com v0 %= vm então, por um
argumento já várias vezes usado nesta secção, os vértices v0 e vm têm grau ı́mpar e os
restantes vértices de G têm grau par.
Reciprocamente, suponhamos que os vértices x e y são os únicos vértices de G de
grau ı́mpar. Seja G# o grafo obtido ao acrescentar a G uma nova aresta !, entre os
vértices x e y. Então G# é conexo e todos os seus vértices têm grau par. Logo, existe
um circuito Euleriano C em G#. Além disso, eventualmente re-escrevendo C, podemos
assumir que C = y!xA. Então A é um atalho Euleriano em G que começa no vértice
x e termina no vértice y.
A prova do Teorema 3.7 e o algoritmo de Fleury permitem determinar em qualquer
grafo conexo com exactamente dois vértices de grau ı́mpar um atalho Euleriano. Para
tal, começamos por acrescentar ao grafo uma nova aresta ! entre os vértices de grau
ı́mpar, digamos x e y. O novo grafo é Euleriano e podemos começar o algoritmo de
Fleury com o atalho y!x, pois ! não é ponte. Se y!xA for o circuito Euleriano obtido
pela implementação do algoritmo de Fleury, então A é um atalho Euleriano de x a
y no grafo inicial. Note-se que este procedimento equivale a começar o algoritmo de
Fleury em G no vértice x. A observação acima mostra que o resultado da aplicação do
algoritmo de Fleury a G com vértice inicial x é um atalho Euleriano em G de x a y.
Exerćıcio. Usando o algoritmo de Fleury desenhe, se posśıvel, cada um dos seguintes
diagramas sem levantar o lápis do papel e sem traçar duas vezes a mesma linha.
CAPÍTULO 3. INTRODUÇÃO À TEORIA DE GRAFOS 62
3.6 Exerćıcios
1. Considere os seguintes grafos:
(a) Diga quais deles admitem atalhos ou circuitos Eulerianos.
(b) Aplique o algoritmo de Fleury aos grafos obtidos em (a) de forma a obter
um circuito ou um atalho Euleriano.
2. Seja G um grafo Euleriano:
(a) G tem sempre um número par de arestas?
(b) G pode ter arestas de corte (pontes)?
3. (a) Quais dos seguintes grafos são Eulerianos?
i. o grafo completo Kn, para n , 3;
ii. o grafo completo bipartido Km,n, para m, n , 1.
(b) Dos grafos anteriores, quais é que admitem atalhos Eulerianos abertos (isto
é, que não são circuitos)?
4. Seja G um grafo conexo com exactamente quatro vértices de grau ı́mpar. Mostre
que existem dois atalhos abertos em G tais que cada aresta de G pertence a
precisamente um destes atalhos.
5. Seja G um grafo conexo com exactamente 2k vértices de grau ı́mpar, onde k , 1.
Mostre que é posśıvel decompor G numa união, disjunta nas arestas, de k atalhos
abertos. Mostre ainda que tal decomposição não é posśıvel com menos de k
atalhos.
6. Usando o exerćıcio anterior, determine o número mı́nimo de vezes que será ne-
cessário levantar o lápis de forma a desenhar cada uma das figuras seguintes sem
traçar mais de uma vez a mesma linha.
CAPÍTULO 3. INTRODUÇÃO À TEORIA DE GRAFOS 63
7. Determine um passeio fechado para o problema das pontes de Königsberg de
forma a que o número de pontes passadas mais de uma vez seja mı́nimo.
8. Seja G um grafo simples com E(G) = {!1, . . . ,!n}, n , 1. O grafo de linhas
de G é o grafo L(G) com vértices x1, . . . , xn, em correspondência com as arestas
de G, tal que os vértices xi e xj estão ligados por uma aresta em L(G) se e só se
as arestas !i e !j correspondentes são adjacentes em G. Na figura abaixo temos
um grafo G e o seu grafo de linhas L(G).
(a) Mostre que se G for Euleriano então L(G) também é.
(b) Para n , 3 determine o grafo de linhas do grafo bipartido completo K1,n.
(c) Dê um exemplo de um grafo simples G tal que L(G) seja Euleriano embora
G não o seja.
9. Diz-se que um grafo Euleriano G é aleatoriamente traçável de um vértice
v $ V (G) se todo o atalho em G com ińıcio no vértice v puder ser estendido a
um circuito Euleriano de G.
(a) Mostre que o seguinte grafo Euleriano é aleatoriamente traçável do vértice
v indicado, mas não o é de nenhum outro vértice.
CAPÍTULO 3. INTRODUÇÃO À TEORIA DE GRAFOS 64
(b) Dê um exemplo de um grafo Euleriano que não seja aleatoriamente traçável
de nenhum dos seus vértices.
(c) Dê um exemplo de um grafo Euleriano que seja aleatoriamente traçável de
todos os seus vértices.
(d) Mostre que um grafo Euleriano é aleatoriamente traçável do seu vértice v
se e só se v está em todos os ciclos de G.
10. (a) Identifique os grafos conexos tais que deg(v) = 2 para todo o vértice v.
(b) Identifique os grafos conexos tais que deg(v) . 2 para todo o vértice v.
(c) Identifique os grafos tais que deg(v) . 2 para todo o vértice v.
CAPÍTULO 3. INTRODUÇÃO À TEORIA DE GRAFOS 65
3.7 Grafos Hamiltonianos
Um caminho Hamiltoniano num grafo é um caminho onde ocorrem todos os vértices
do grafo exactamente uma vez. Assim, um ciclo Hamiltoniano é um ciclo que contém
todos os vértices do grafo exactamente uma vez, com excepcção dos vértices inicial e
final que têm de coincidir. Um grafo diz-se Hamiltoniano se possuir algum ciclo
Hamiltoniano. Note-se que um grafo Hamiltoniano é necessariamente conexo.
Se retirarmos uma aresta a um ciclo Hamiltoniano obtemos um caminho Hamilto-
niano aberto, logo todo o grafo Hamiltoniano possui caminhos Hamiltonianos abertos,
ao contrário do que se passa com os grafos Eulerianos, que não possuem atalhos Eu-
lerianos abertos. No entanto, o rećıproco desta afirmação não é verdadeiro, como o
seguinte exemplo mostra.
Exemplo. O grafo G1 não tem caminhos Hamiltonianos abertos (e portanto também
não tem ciclos Hamiltonianos); G2 tem caminhos Hamiltonianos abertos mas não tem
ciclos Hamiltonianos; G3 tem ciclos (e caminhos abertos) Hamiltonianos.
A designação de Hamiltoniano refere-se ao matemático irlandês Sir
William Rowan Hamilton (1805–1865), famoso pela sua descoberta
dos quaterniões, uma generalização não-comutativa dos números
complexos. Por volta de 1857 Hamilton criou um jogo ao qual deu
o nome de jogo icosiano, aludindo aos 20 vértices do dodecaedro.
A cada um desses vértices era atribúıdo o nome de uma capital e o
objectivo do jogo era, usando as arestas do dodecaedro, planear um
percurso que visitasse cada uma das cidades exactamente uma vez e
terminasse na cidade de onde se tinha partido. Assim, procurava-se
um ciclo Hamiltoniano no grafo do dodecaedro.
Um exemplo de um tal ciclo é o seguinte:
09/18/2007 05:38 PMIcosian Game -- from Wolfram MathWorld
Page 1 of 2http://mathworld.wolfram.com/IcosianGame.html
Search Site
Algebra
Applied Mathematics
Calculus and Analysis
Discrete Mathematics
Foundations of Mathematics
Geometry
History and Terminology
Number Theory
Probability and Statistics
Recreational Mathematics
Topology
Alphabetical Index
Interactive Entries
Random Entry
New in MathWorld
MathWorld Classroom
About MathWorld
Send a Message to the Team
Order book from Amazon
12,704 entries
Sun Aug 26 2007
Recreational Mathematics > Games > General Games 
Discrete Mathematics > Graph Theory > Simple Graphs > Polyhedral Graphs 
Recreational Mathematics > Interactive Entries > LiveGraphics3D Applets 
Icosian Game
The Icosian game, also called the Hamiltonian game (Ball and Coxeter
1987, p. 262), is the problem of finding a Hamiltonian circuit along the
edges of an dodecahedron, i.e., a path such that every vertex is visited a
single time, no edge is visited twice, and the ending point is the same as
the starting point (left figure). The puzzle was distributed commercially as a
pegboard with holesat the nodes of the dodecahedral graph, illustrated
above (right figure). The Icosian Game was invented in 1857 by William
Rowan Hamilton. Hamilton sold it to a London game dealer in 1859 for 25
pounds, and the game was subsequently marketed in Europe in a number
of forms (Gardner 1957).
A graph having a Hamiltonian circuit, i.e., on which the Icosian game may
be played, is said to be a Hamiltonian graph. While the skeletons of all the
Platonic solids and Archimedean solids (i.e., the Platonic graphs and
Archimedean graphs, respectively) are Hamiltonian, the same is not
necessarily true for the skeletons of the Archimedean duals, as shown by
Coxeter (1946) and Rosenthal (1946) for the rhombic dodecahedron
(Gardner 1984, p. 98).
SEE ALSO: Dodecahedral Graph, Dodecahedron, Hamiltonian Circuit,
Hamiltonian Graph, Herschel Graph, Polyhedral Graph. [Pages Linking Here]
REFERENCES:
Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New
York: Dover, pp. 262-266, 1987.
Coxeter, H. S. M. "Problem E 711." Amer. Math. Monthly 53, 156, 1946.
Dalgety, J. "The Icosian Game."
http://puzzlemuseum.com/month/picm02/200207icosian.htm.
Gardner, M. "Mathematical Games: About the Remarkable Similarity between the Icosian
Game and the Towers of Hanoi." Sci. Amer. 196, 150-156, May 1957.
Hamilton, W. R. Quart. J. Math., 5, 305, 1862.
Hamilton, W. R. Philos. Mag. 17, 42, 1884.
Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 4, 1994.
Herschel, A. S. "Sir Wm. Hamilton's Icosian Game." Quart. J. Pure Applied Math. 5, 305,
1862.
Lucas, E. Récréations mathématiques, Vol. 2. Paris: Gauthier-Villars, pp. 201 and 208-
255, 1891.
MacTutor Archive. "Mathematical Games and Recreations." http://www-
groups.dcs.st-
and.ac.uk/~history/HistTopics/Mathematical_games.html#49.
Rosenthal, A. "Solution to Problem E 711: Sir William Hamilton's Icosian Game." Amer.
Other Wolfram Sites:
 Wolfram Research
 Demonstrations Site
 Integrator
 Tones
 Functions Site
 Wolfram Science
 more…
Download Mathematica Player >>
Complete Mathematica
Documentation >>
Show off your math savvy with a
MathWorld T-shirt.
09/18/2007 05:38 PMIcosian Game -- from Wolfram MathWorld
Page 1 of 2http://mathworld.wolfram.com/IcosianGame.html
Search Site
Algebra
Applied Mathematics
Calculus and Analysis
Discrete Mathematics
Foundations of Mathematics
Geometry
History and Terminology
Number Theory
Probability and Statistics
Recreational Mathematics
Topology
Alphabetical Index
Interactive Entries
Random Entry
New in MathWorld
MathWorld Classroom
About MathWorld
Send a Message to the Team
Order book from Amazon
12,704 entries
Sun Aug 26 2007
Recreational Mathematics > Games > General Games 
Discrete Mathematics > Graph Theory > Simple Graphs > Polyhedral Graphs 
Recreational Mathematics > Interactive Entries > LiveGraphics3D Applets 
Icosian Game
The Icosian game, also called the Hamiltonian game (Ball and Coxeter
1987, p. 262), is the problem of finding a Hamiltonian circuit along the
edges of an dodecahedron, i.e., a path such that every vertex is visited a
single time, no edge is visited twice, and the ending point is the same as
the starting point (left figure). The puzzle was distributed commercially as a
pegboard with holes at the nodes of the dodecahedral graph, illustrated
above (right figure). The Icosian Game was invented in 1857 by William
Rowan Hamilton. Hamilton sold it to a London game dealer in 1859 for 25
pounds, and the game was subsequently marketed in Europe in a number
of forms (Gardner 1957).
A graph having a Hamiltonian circuit, i.e., on which the Icosian game may
be played, is said to be a Hamiltonian graph. While the skeletons of all the
Platonic solids and Archimedean solids (i.e., the Platonic graphs and
Archimedean graphs, respectively) are Hamiltonian, the same is not
necessarily true for the skeletons of the Archimedean duals, as shown by
Coxeter (1946) and Rosenthal (1946) for the rhombic dodecahedron
(Gardner 1984, p. 98).
SEE ALSO: Dodecahedral Graph, Dodecahedron, Hamiltonian Circuit,
Hamiltonian Graph, Herschel Graph, Polyhedral Graph. [Pages Linking Here]
REFERENCES:
Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New
York: Dover, pp. 262-266, 1987.
Coxeter, H. S. M. "Problem E 711." Amer. Math. Monthly 53, 156, 1946.
Dalgety, J. "The Icosian Game."
http://puzzlemuseum.com/month/picm02/200207icosian.htm.
Gardner, M. "Mathematical Games: About the Remarkable Similarity between the Icosian
Game and the Towers of Hanoi." Sci. Amer. 196, 150-156, May 1957.
Hamilton, W. R. Quart. J. Math., 5, 305, 1862.
Hamilton, W. R. Philos. Mag. 17, 42, 1884.
Harary, F. Graph Theory. Reading, MA: Addison-Wesley, p. 4, 1994.
Herschel, A. S. "Sir Wm. Hamilton's Icosian Game." Quart. J. Pure Applied Math. 5, 305,
1862.
Lucas, E. Récréations mathématiques, Vol. 2. Paris: Gauthier-Villars, pp. 201 and 208-
255, 1891.
MacTutor Archive. "Mathematical Games and Recreations." http://www-
groups.dcs.st-
and.ac.uk/~history/HistTopics/Mathematical_games.html#49.
Rosenthal, A. "Solution to Problem E 711: Sir William Hamilton's Icosian Game." Amer.
Other Wolfram Sites:
 Wolfram Research
 Demonstrations Site
 Integrator
 Tones
 Functions Site
 Wolfram Science
 more…
Download Mathematica Player >>
Complete Mathematica
Documentation >>
Show off your math savvy with a
MathWorld T-shirt.
CAPÍTULO 3. INTRODUÇÃO À TEORIA DE GRAFOS 66
A noção de ciclo (resp. caminho aberto) Hamiltoniano é análoga à de circuito (resp.
atalho aberto) Euleriano, mas é importante notar que estes dois problemas são notori-
amente distintos. Enquanto que a caracterização dos grafos que admitem circuitos ou
atalhos Eulerianos é simples e computacionalmente eficaz, não existem até à data ca-
racterizações deste tipo para os grafos Hamiltonianos, não obstante o esforço e empenho
de várias gerações de matemáticos, e a importância do problema.
Exemplo. Este exemplo mostra a independência entre a existência de circuitos (ata-
lhos) Eulerianos e a existência de ciclos (caminhos) Hamiltonianos num grafo.
grafo circuito Euleriano atalho Euleriano ciclo Hamiltoniano caminho Hamiltoniano
(a) sim não sim sim
(b) não sim não sim
(c) não não sim sim
(d) sim não não sim
(e) não sim não não
(f) não não não sim
Observação. É fácil de ver que, com excepção do grafo com dois vértices unidos por
uma aresta de multiplicidade 2, um grafo G possui um ciclo ou caminho Hamiltoniano
se e só se o grafo simples associado a G (o que se obtém de G eliminando os lacetes
e todas menos uma das arestas entre cada par de vértices adjacentes em G) possui
um ciclo ou caminho Hamiltoniano, respectivamente. Por esta razão, todos os grafos
considerados nesta e na próxima secções serão simples. Como tal, descreveremos os
passeios nestes grafos pela sua sequência de vértices.
Dado um grafo, determinar se este possui ou não um caminho ou um ciclo Hamil-
toniano é, como já foi referido, um problema em geral muito complexo. Não sendo
conhecidas condições necessárias e suficientes para um grafo ser Hamiltoniano, apre-
sentaremos de seguida algumas condições necessárias, que nos permitirão concluir que
certos grafos não são Hamiltonianos, e também algumas condições suficientes, que per-
mitirão concluir que certos grafos são Hamiltonianos. Condição suficientes para um
CAPÍTULO 3. INTRODUÇÃO À TEORIA DE GRAFOS 67
grafo ser Hamiltoniano são dadas pelos Teoremas de Dirac e de Ore, que apresentare-
mos em breve. Antes de o fazer, comecemos com algumas observações simples.
Os exemplos mais simples de grafos Hamiltonianos são os ciclos Cn, com n , 3
vértices v1, . . . , vn e n arestas {v1, v2}, . . . , {vi, vi+1}, . . . , {vn!1, vn}, {vn, v1}:
C7
Além disso, dado um grafo Hamiltoniano G e um grafo G# obtido de G por adição de
arestas, é claro que G# é aindaHamiltoniano já que um circuito Hamiltoniano em G
será ainda um circuito Hamiltoniano em G#. Em particular, o grafo completo Kn é
Hamiltoniano para n , 3 pois contém o ciclo Cn como seu subgrafo gerador.
No teorema que se segue, enunciamos duas condições necessárias para um grafo ser
Hamiltoniano. A prova é deixada como exerćıcio.
Teorema 3.8. Seja G um grafo Hamiltoniano. Então:
(a) G não tem pontes;
(b) Se 1 %= S ! V (G) então #(G+ S) . |S|.
Exemplo. O grafo G abaixo não é Hamiltoniano porque a aresta a indicada é uma
ponte. O grafo H também não é Hamiltoniano porque se v for o vértice indicado
na figura então #(H + v) = 2 > 1. No entanto, basta acrescentar uma qualquer
aresta entre vértices não adjacentes a G (respectivamente, H) para que este grafo
se torne Hamiltoniano. Por esta razão, dizemos que G e H são ambos grafos não-
Hamiltonianos maximais.
a
G
v H
Exemplo. Se retirarmos os três vértices representados a preto no grafo G abaixo,
obtemos um grafo com 4 componentes conexas. Logo G não é Hamiltoniano.
CAPÍTULO 3. INTRODUÇÃO À TEORIA DE GRAFOS 68
Vamos agora determinar condições suficientes para que um grafo seja Hamiltoniano.
Historicamente, o primeiro resultado neste sentido deve-se a Dirac, tendo este sido
posteriormente generalizado por Ore. No entanto, por razões de encadeamento lógico
dos argumentos a usar, iremos inverter a ordem histórica destes resultados e provar
primeiro um teorema que implicará o Teorema de Ore, do qual o Teorema de Dirac
decorrerá como corolário.
Teorema 3.9. Seja G um grafo simples com n , 3 vértices e sejam u e v vértices não
adjacentes de G tais que
deg(u) + deg(v) , n.
Então G é Hamiltoniano se e só se G + {u, v} é Hamiltoniano, onde G + {u, v} é o
grafo obtido adicionando a aresta {u, v} a G.
Demonstração. A implicação directa é trivial. Suponhamos então que G + {u, v} é
Hamiltoniano e seja C um ciclo Hamiltoniano em G + {u, v}. Se a aresta {u, v} não
ocorre em C então C é ainda um ciclo Hamiltoniano em G, o que prova que G é
Hamiltoniano. Caso contrário, C + {u, v} é um caminho Hamiltoniano em G entre os
vértices u e v, digamos
u = x1 + x2 + · · ·+ xn = v.
Sejam r = deg(u) e s = deg(v). Por hipótese, r + s , n. Como C + {u, v} contém
todos os vértices de G e u e v não são adjacentes em G, os vizinhos de u e v estão entre
os vértices x2, . . . , xn!1. Vejamos que existe um vizinho xk de u (k , 2) tal que xk!1 é
vizinho de v. Se assim não fosse, v teria no máximo n+ 1+ r vizinhos, ou seja,
s . n+ 1+ r )* r + s . n+ 1
o que contradiria a hipótese. Logo, existe k , 2 tal que u e xk são adjacentes, bem
como xk!1 e v. Podemos então formar o ciclo Hamiltoniano:
u = x1 + · · ·+ xk!1 + v = xn + xn!1 + · · ·+ xk + u.
CAPÍTULO 3. INTRODUÇÃO À TEORIA DE GRAFOS 69
u v
x x
k-1 k
Logo G é também Hamiltoniano.
Podemos aplicar sucessivamente o teorema anterior a um grafo, acrescentando-lhe
novas arestas. Se ao fim de algumas iterações obtivermos um grafo Hamiltoniano,
poderemos concluir que o grafo inicial também era Hamiltoniano, pelo Teorema 3.9.
Por exemplo, se por este processo aplicado ao grafo simples G obtivermos um grafo
completo Kn, com n , 3, então G é Hamiltoniano.
Exemplo. Aplicações sucessivas do Teorema 3.9 permitem chegar ao grafo completo
K6, logo G é também Hamiltoniano (como, de resto, é fácil de concluir directamente).
Teorema 3.10 (Ore, 1960). Seja G um grafo simples com n , 3 vértices tal que para
qualquer par de vértices não adjacentes u e v se tem
deg(u) + deg(v) , n.
CAPÍTULO 3. INTRODUÇÃO À TEORIA DE GRAFOS 70
Então G é Hamiltoniano.
Demonstração. A hipótese do Teorema 3.9 é válida para todos os pares de vértices não
adjacentes de G portanto, por esse teorema, o grafo G é Hamiltoniano se e só se o grafo
completo Kn o for. Logo, G é Hamiltoniano.
Enunciamos finalmente o Teorema de Dirac, que é consequência imediata do Teo-
rema de Ore.
Teorema 3.11 (Dirac, 1952). Seja G um grafo simples com n , 3 vértices. Se
deg(v) , n/2 para todo o vértice v de G, então G é Hamiltoniano.
Exemplo. O grafo seguinte é Hamiltoniano:
Note-se que as condições dos Teoremas de Dirac e de Ore são suficientes mas não
necessárias. Por exemplo, o ciclo Cn é Hamiltoniano mas, para n , 5, não satisfaz
essas condições.
Para terminar esta secção, apresentamos um algoritmo que permite, num grafo que
satisfaz as hipóteses do Teorema de Ore (em particular, basta que satisfaça as hipóteses
do Teorema de Dirac), construir um ciclo Hamiltoniano. A prova da eficácia do algo-
ritmo é idêntica à prova do Teorema 3.9, e será portanto omitida.
Algoritmo
Seja G um grafo simples com n , 3 vértices que satisfaz as hipóteses do Teorema de
Ore.
Passo 1. Escolher um vértice qualquer de G e, acrescentando vértices adjacentes à
direita e à esquerda, construir um caminho aberto em G de comprimento cada vez
maior, até não ser posśıvel prosseguir, digamos
C = y1 + y2 + · · ·+ ym, 3 . m . n,
de comprimento m+ 1.
CAPÍTULO 3. INTRODUÇÃO À TEORIA DE GRAFOS 71
Passo 2.
(i) Se y1 e ym não forem adjacentes em G, prosseguimos para o Passo 3. Caso
contrário, y1 e ym são adjacentes e prosseguimos para (ii).
(ii) Se m = n então y1 + y2 + · · · + ym + y1 é um ciclo Hamiltoniano em G; parar.
Caso contrário, y1 e ym são adjacentes e m < n; ir para (iii).
(iii) Existe um vértice z, diferente de y1, . . . , ym, que é adjacente a yk, para algum
1 . k . m. Substituir C pelo caminho aberto de comprimento m
z + yk + yk+1 + · · ·+ ym + y1 + · · ·+ yk!1.
De seguida, estender C acrescentando vértices adjacentes à direita e à esquerda
até não ser posśıvel prosseguir, de forma a termos ainda um caminho aberto de
comprimento maior ou igual a m. Voltar ao ińıcio do Passo 2.
Passo 3. Encontrar um vértice yk, com 1 < k < m, tal que y1 é adjacente a yk e ym é
adjacente a yk!1. Substituir C pelo caminho
y1 + · · ·+ yk!1 + ym + ym!1 + · · ·+ yk.
de comprimento m+ 1, tal como C. As duas extremidades deste caminho são adjacen-
tes. Voltar ao Passo 2(ii).
De facto, é posśıvel modificar ligeiramente este algoritmo de forma a obter uma
prova, também construtiva, do seguinte resultado:
Teorema 3.12. Seja G um grafo simples com n vértices tal que para qualquer par de
vértices não adjacentes u e v de G se tem
deg(u) + deg(v) , n+ 1.
Então G tem um caminho Hamiltoniano, que pode ser obtido adaptando de forma
natural o algoritmo apresentado acima.
Exerćıcio. Averigue se o seguinte grafo é ou não Hamiltoniano: