Teoria dos Grafos e Aplicações
Domingos Moreira Cardoso
Departamento de Matemática da Universidade de Aveiro
Mestrado em Matemática - 2004/2005
ii
Conteúdo
Introdução
1
1 Conceitos e Resultados Básicos
1.1 Notação e noções fundamentais
1.2 Resultados gerais . . . . . . . .
1.3 Grafos bipartidos . . . . . . . .
1.4 Exercícios . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
3
3
6
11
13
2 Grafos de Euler e Grafos de Hamilton
2.1 Circuitos e trajectos de Euler . . . . .
2.2 Ciclos de Hamilton . . . . . . . . . . .
2.3 Código de Gray * . . . . . . . . . . . .
2.4 Exercícios . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
15
15
17
20
24
.
.
.
.
.
.
.
.
.
.
.
.
3 Grafos Planares e Generalizações
25
3.1 Duais de grafos e digrafos planares . . . . . . . . . . . . . . . . . 25
3.2 Fórmula de Euler e aplicações . . . . . . . . . . . . . . . . . . . . 26
3.2.1 Condições necessárias para grafos planares . . . . . . . . . 27
3.2.2 Condições necessárias e suficientes para grafos planares * 29
3.2.3 Grafos platónicos . . . . . . . . . . . . . . . . . . . . . . . 30
3.3 Grafos em variedades compactas orientáveis . . . . . . . . . . . . 31
3.3.1 Menores combinatórios e menores topológicos . . . . . . . 33
3.3.2 Genus de um grafo e fórmula de Euler generalizada . . . . 35
3.3.3 Grafos g-platónicos . . . . . . . . . . . . . . . . . . . . . . 38
3.4 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4 Digrafos e Espaços Vectoriais Associados.
4.1 Espaço dos vértices e espaço dos arcos . .
4.2 Variantes do lema de Farkas para grafos .
4.3 Subespaços de circuitos e de cocircuitos .
4.4 Exercícios . . . . . . . . . . . . . . . . . .
iii
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
41
41
44
45
48
iv
5 Independentes, Cliques e Colorações
5.1 Formulações analíticas para estáveis máximos . . . . . .
5.2 Grafos com número de estabilidade quadrático convexo .
5.3 Emparelhamentos e coberturas de arestas por vértices .
5.4 Colorações de vértices e arestas . . . . . . . . . . . . . .
5.5 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . .
CONTEÚDO
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
49
49
60
63
67
78
6 Resultados Algébricos Associados a Grafos
79
6.1 Polinómios cromáticos . . . . . . . . . . . . . . . . . . . . . . . . 79
6.2 Espectros de grafos . . . . . . . . . . . . . . . . . . . . . . . . . . 82
6.2.1 Algumas propriedades dos valores próprios da matriz de
adjacência de um grafo . . . . . . . . . . . . . . . . . . . 83
6.2.2 Algumas propriedades dos vectores próprios da matriz de
adjacência de um grafo * . . . . . . . . . . . . . . . . . . 85
6.3 Grafos fortemente regulares . . . . . . . . . . . . . . . . . . . . . 86
6.3.1 Resultados fundamentais . . . . . . . . . . . . . . . . . . 87
6.3.2 Espectros de grafos fortemente regulares . . . . . . . . . . 89
6.4 Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
Bibliografia
93
Introdução
A origem da teoria dos grafos é, em geral, associada ao problema das pontes
de Königsberg (cidade da Prússia que agora se designa por Kaliningrad). Parte
desta cidade localizava-se em duas ilhas do rio Pregel as quais estavam ligadas
às margens e uma à outra através de 7 pontes, conforme a Figura 1 documenta.
A
B
C
D
Figura 1: Pontes de Königsberg em 1736 e o respectivo "multigrafo".
Consta que os habitantes de Königsberg gostavam de dar passeios de modo
a atravessar todas as pontes e que alguns andavam particularmente aborrecidos
pelo facto de não encontrarem um trajecto (com partida e chegada a um mesmo
lugar) que lhes permitisse atravessar apenas uma vez cada uma das pontes.
O matemático suiço Leonhard Euler (1707-1783) ao tomar conhecimento deste
problema resolveu-o (indicando a impossibilidade da existência de um tal percurso, numa memória que publicou em S. Petersburgo em 1736) modelando-o
pelo multigrafo representado na Figura 1. O problema dual do problema das
pontes de Königsberg, é o de saber se um nadador poderia nadar neste mesmo
rio e localidade de modo a passar por baixo de todas as pontes sem repetir
nenhuma.
Um problema com ingredientes semelhantes foi formulado e resolvido (em
1857) pelo matemático irlandês Sir William Hamilton (1805-1865). Este pro1
2
CONTEÚDO
blema, que consiste em percorrer todos os vértices do dodecaedro representado
na Figura 2, passando uma única vez em cada um, com partida e chegada no
mesmo vértice foi designado por viagem à volta do mundo.
Figura 2: Dodecaedro (poliedro regular com 20 vértices de grau 3, 12 faces
pentagonais, 30 arestas e 20 vértices.
Um outro problema, também bastante antigo, relacionados com a Teoria dos
Grafos, diz respeito à coloração de mapas. Com este problema, pretende-se saber
qual o menor número de cores necessárias para pintar um mapa de modo que
não existam países, com fronteira comum, pintados da mesma cor. Desde muito
cedo se conjecturou que 4 cores bastariam para resolver este problema. Com
efeito, o cartógrafo inglês Francis Guthrie, já em 1852, reclamava a suficiência
de 4 cores para distinguir os países num mapa plano e foi precisamente nesse ano
(1852) que A. de Morgan, numa carta que enviou a W. R. Hamilton, afirmou ter
tomado conhecimento deste problema, que designou por problema das 4 cores,
através de um seu aluno, Frederick Guthrie (irmão de Francis Guthrie).
Em 1878, numa comunicação apresentada na "London Mathematical Society", Cayley referiu-se ao problema das 4 cores como sendo um problema em
aberto. Desde então, muitos problemas de natureza combinatória têm sido modelados por grafos com abordagens que, por sua vez, têm gerado novos conceitos
e resultados de aplicação generalizada, transformando a teoria dos grafos numa
área da matemática contemporânea de grande produção científica.
Capítulo 1
Conceitos e Resultados
Básicos
1.1
Notação e noções fundamentais
Um grafo G é um par de conjuntos (V, E), tal que V = V (G) = {v1 , . . . , vn } é
o conjunto dos vértices e E = E(G) é o conjunto das arestas, a cada uma das
quais corresponde um subconjunto de V (G) de cardinalidade 2, i.e., E(G) =
{e1 , . . . , em }, com ek = {vki , vkj }, para k ∈ {1, . . . , m}. Por simplicidade de
notação, uma aresta entre os vértices x e y será representada por xy. Um grafo
diz-se simples se não existem arestas paralelas (mais do que uma aresta entre os
mesmos dois vértices) nem lacetes (arestas com ambos os extremos no mesmo
vértice).
Neste texto, os grafos simples são designados apenas por grafos e os grafos com
lacetes e/ou arestas paralelas por multigrafos.
O número de vértices e arestas de um grafo designa-se, respectivamente, por
ordem e dimensão do grafo.
Os grafos são muitas vezes representado(as) por figuras planas constituídas por
linhas e pontos, as primeiras representando arestas (arcos) e os segundos vértices.
1
6
3
1
6
5
3
-
2
4
2
4
¾
k
?
¾
3
6
6
5
Figura 1.1: Exemplos de grafo e digrafo.
Na Figura 1.1 representa-se um grafo de ordem 6 e dimensão 7 e um digrafo
3
4
Conceitos e Resultados Básicos
6
3
5
4
Figura 1.2: Subgrafo G[{3, 4, 5, 6}] do grafo representado na Figura 1.1.
de ordem 6 e dimensão 9.
Dado um grafo G (DG), uma aresta diz-se incidente no vértice v, se v é um
dos seus extremos e dois vértices, x e y, dizem-se adjacentes se
xy ∈ E(G) ({(x, y), (y, x)} ∩ A(DG) 6= ∅).
Dados dois grafos G e G0 , diz-se que G0 é um subgrafo de G e que G é um
supergrafo de G0 quando V (G0 ) ⊆ V (G) e E(G0 ) ⊆ E(G). Por sua vez, designa-se por subgrafo de G induzido pelo subconjunto de vértices V 0 e denota-se por
G[V 0 ] o subgrafo obtido de G ignorando o subconjunto de vértices V (G) \ V 0 e,
consequentemente, as arestas que lhe são incidentes. Por exemplo, na Figura 1.2
representa-se o subgrafo do grafo G de ordem 6, representado na Figura 1.1,
induzido pelo subconjunto de vértices {3, 4, 5, 6}, ou seja, G[{3, 4, 5, 6}].
Designa-se por grafo completo (nulo) de ordem n e denota-se por Kn (Nn )
um grafo com n vértices dois a dois adjacentes (não adjacentes, ou seja, sem
qualquer aresta). Por sua vez, designa-se por grafo complementar de um grafo
G e denota-se por Ḡ um grafo com o mesmo conjunto de vértices de G no qual
dois vértices são adjacentes se e só se não são adjacentes em G.
Denotando por Gn o conjunto de todos os grafos de ordem n e por ⊆P a relação
binária definida em Gn tal que G1 ⊆P G2 se e só se G1 é um subgrafo de G2 ,
é imediato concluir que P = (Gn , ⊆P ) é um conjunto parcialmente ordenado.
Neste conjunto parcialmente ordenado, Kn é o único elemento maximal e Nn o
único elemento minimal. Adicionalmente, dado G ∈ Gn \ {Nn , Kn }, é claro que
G e Ḡ não são comparáveis.
Dado um grafo G e um vértice v ∈ V (G) designa-se por grau ou valência de
v e denota-se por dG (v) o número de arestas de G incidentes em v. O máximo
grau dos vértices de G denota-se por ∆(G) e o mínimo grau por δ(G). Um grafo
diz-se p-regular se todos os seus vértices têm grau p (no caso de p = 3 estes
grafos também se designam por cúbicos).
Tendo em conta que ao adicionarmos os graus de todos os vértices de um
grafo arbitrário, G, cada aresta conta duas vezes, com facilidade se conclui que
X
dG (v) = 2|E(G)|
(1.1)
v∈V (G)
Notação e noções fundamentais
e, consequentemente, que
corre ainda que
5
P
v∈V (G)
δ(G) ≤ b
dG (v) = 0 (mod 2). Da igualdade (1.1) de-
2|E(G)|
c ≤ ∆(G).
n
(1.2)
O conjunto de vértices adjacentes a um vértice v designa-se por vizinhança de
v (ou conjunto de vizinhos de v) e denota-se por NG (v). Como consequência, é
claro que dG (v) = |NG (v)|.
Dados dois grafos G e H, a união de G com H denota-se por G ∪ H e
corresponde ao grafo G ∪ H = (V (G) ∪ V (H), E(G) ∪ E(H)) e a intersecção de
G com H denota-se por G ∩ H e corresponde ao grafo
G ∩ H = (V (G) ∩ V (H), E(G) ∩ E(H).
Com base nesta definição de união e intersecção, podemos afirmar que
S um grafo
G se parte nos grafos G1 = (V1 , E1 ), . . . , Gk = (Vk , Ek ) se G = 1≤j≤k Gj e
Gp ∩ Gq = ∅ ∀p 6= q, onde ∅ denota o grafo definido pelo par (∅, ∅).
Um grafo G diz-se conexo se não admite qualquer partição para além da trivial
(i.e, G = G ∪ ∅). Por sua vez, dado um grafo não conexo G, um seu subgrafo
diz-se uma componente conexa (ou simplesmente componente) de G, se é um
subgrafo conexo maximal, no sentido em que sendo induzido pelo subconjunto
de vértices V 0 , ∀x ∈ V (G) \ V 0 , o subgrafo G[V 0 ∪ {x}] não é conexo.
Designa-se por passeio num grafo G, entre os vértices x e y, toda a sequência
de vértices e arestas da forma
x = v1 , v1 v2 , v2 , . . . , vk−1 , vk−1 vk , vk = y,
com eventual repetição de vértices e arestas. Neste caso, os vértices x e y
designam-se por vértices extremos do passeio (sendo x o vértice inicial e y o
vértice final). Um trajecto num grafo G entre os vértices x e y é um passeio
entre x e y sem arestas repetidas (podendo, no entanto, existir vértices repetidos). Um caminho entre os vértices x e y é um trajecto entre x e y sem vértices
repetidos. Os trajectos fechados (onde o vértice final coincide com o inicial)
designam-se por circuitos e os trajectos fechados, onde os vértices inicial e final
são os únicos que coincidem, designam-se por ciclos. Geralmente, os caminhos,
trajectos, passeios, circuitos e ciclos representam-se pela respectiva sequência de
vértices.
Dado um caminho P (ciclo C) de um grafo G designa-se por comprimento de P
(C) e denota-se por comp(P ) (comp(C)) o número de arestas que o constitui.
Por exemplo, uma aresta é um caminho de comprimento 1 e um vértice um
caminho de comprimento 0. Por outro lado, um triângulo é um ciclo de comprimento 3.
Dado um grafo G de ordem n e dois vértices x, y ∈ V (G), denotando por PG (x, y)
o conjunto de todos os caminhos de G entre x e y, designa-se por distância entre
vértices de G a função
dG : V (G) × V (G)
7→
(x, y)
Ã
{0, . . . , n − 1} ∪ {∞}
½
min{comp(P ) : P ∈ PG (x, y)}
dG (x, y) =
∞
(1.3)
se
se
PG (x, y) 6= ∅,
PG (x, y) = ∅.
6
Conceitos e Resultados Básicos
Embora as notações utilizadas para grau de um vértice e para distância entre
dois vértices sejam idênticas, é fácil distingui-las de acordo com o contexto.
A partir das definições dadas de grafo conexo e de componente conexa, podemos concluir que um grafo é conexo se e só se tem uma única componente
ou, em alternativa, se e só se existe um caminho entre quaisquer dois dos seus
vértices.
A maior distância entre vértices de um grafo G designa-se por diâmetro de G
e denota-se por diam(G), por sua vez, designa-se por cintura de G e denota-se
por g(G) o comprimento do ciclo de menor comprimento contido em G. Quando
G não é conexo, diz-se que tem diâmetro infinito e escreve-se diam(G) = ∞ e
quando é acíclico (i.e, não tem ciclos) diz-se que tem cintura infinita e escreve-se
g(G) = ∞.
1.2
Resultados gerais
Theorem 1.2.1. Se o grafo G é tal que δ(G) ≥ 2, então G contém um caminho
P e um ciclo C tais que comp(P ) ≥ δ(G) e comp(C) ≥ δ(G) + 1.
Demonstração. Seja P = v0 , . . . , vk um caminho de maior comprimento em G.
Então todos os vizinhos de vk estão em P (caso contrário P , poderia ser estendido
para um vizinho e não teria comprimento máximo). Logo, comp(P ) = k ≥ dG (vk ) ≥
δ(G). Por outro lado, se vi é o vértice de menor índice em P tal que vi vk ∈ E(G),
então vi , vi+1 , . . . , vk , vi é um ciclo de comprimento pelo menos δ(G) + 1 (dado que
{vi , vi+1 , . . . , vk } contém todos os vértices adjacentes a vk , cujo número é não inferior
a δ(G)).
A Figura 1.3 ilustra a demonstração deste teorema.
v1
v2
vk−1
vi
vk
Figura 1.3: Ilustração a demonstração de Teorema 1.2.1.
Theorem 1.2.2 (Mantel, 1907). Dado um grafo G, se |E(G)| >
então g(G) = 3 (ou seja, G contém um triângulo).
|V (G)|2
,
4
Demonstração.
2
Suponha-se que |E(G)| = m, |V (G)| = n, m > n4 e ainda que g(G) > 3. Nestas
condições, dados dois vértices adjacentes arbitrários, x, y ∈ V (G), os conjuntos dos
respectivos vizinhos têm intersecção vazia, ou seja,
∀xy ∈ E(G)
NG (x) ∩ NG (y) = ∅.
Resultados gerais
7
Consequentemente, qualquer que seja a aresta xy ∈ E(G), dG (x) + dG (y) ≤ n, donde
vem que
X
X
(dG (i) + dG (j)) =
dG (v)2 ≤ mn.
(1.4)
ij∈E(G)
v∈V (G)
Por outro lado, de acordo com a desigualdade de Chevishev 1
P
X
( v∈V (G) dG (v))2
4m2
2
dG (v) ≥
=
.
n
n
(1.5)
v∈V (G)
Tendo em conta (1.4) e (1.5), vem que
4m2
≤
n
e, consequentemente, que m ≤
n2
,
4
X
dG (v)2 ≤ mn
v∈V (G)
o que contraria a hipótese.
Theorem 1.2.3. Se o grafo G contém um ciclo, então g(G) ≤ 2diam(G) + 1.
Demonstração. Seja C um ciclo de menor comprimento em G e suponha-se que
g(G) > 2diam(G) + 1, ou seja, que
g(G) = comp(C) ≥ 2diam(G) + 2.
Então ∃x, y ∈ V (C) tais que dC (x, y) ≥ diam(G) + 1. Uma vez que em G existe
um caminho P , entre x e y cujo comprimento é não superior ao diâmetro, podemos
concluir que P não é um subgrafo de C. Logo em P ∪ C (e, consequentemente, em G)
existe um ciclo C 0 tal que
comp(C 0 ) ≤ dC (x, y) + comp(P ) < 2dC (x, y) ≤ comp(C),
o que contraria a hipótese.
Theorem 1.2.4 (*). Se o grafo G é tal que g(G) = 2diam(G) + 1, então G é
regular.
1 Note-se
que, para p ≥ 2,
(
p−1
X
zk )2 ≤ (p − 1)
k=1
p−1
X
zk2
⇒
k=1
(
p
X
zk ) 2 ≤ p
k=1
p
X
zk2 .
k=1
Pp−1 2
P
2
Com efeito, admitindo que a desigualdade ( p−1
k=1 zk ) ≤ (p − 1)
k=1 zk se verifica, vem que
(
p
X
zk )2
=
k=1
(
p−1
X
zk )2 + zp2 + 2zp (
k=1
≤
(p − 1)
p−1
X
zk ) ≤ (p − 1)
k=1
p−1
X
k=1
zk2 + zp2 +
p−1
X
k=1
p−1
X
zk2 + zp2 +
k=1
(zp2 + zk2 ) = p
p
X
p−1
X
2zp zk
k=1
zk2 .
k=1
Logo, dado que para p = 2, a desigualdade é satisfeita na forma de igualdade, por indução,
conclui-se que ela é verdadeira para qualquer p ≥ 2.
8
Conceitos e Resultados Básicos
Demonstração. Primeiramente vamos provar que todos os vértices de um ciclo C
de comprimento g(G) têm a mesma valência e, posteriormente, prova-se que todos os
vértices não pertencentes a V (C) têm a mesma valência dos vértices em C. Sejam
x, y ∈ V (G) tais que dG (x, y) = diam(G) = d e seja P um caminho de comprimento d
entre x e y. Seja z ∈ NG (y)\V (P ). Então d = dG (x, y) ≤ dG (x, z)+1 ⇔ d−1 ≤ dG (x, z)
e, consequentemente, dG (x, z) = d (uma vez que dG (x, z) = d − 1 implica a existência de um ciclo em G de comprimento não superior a 2d). Logo, qualquer que seja
z ∈ NG (y) \ V (P ) existe um único caminho entre x e z de comprimento d (caso contrário ter-se-ia g(G) ≤ 2d). Cada caminho deste tipo utiliza diferentes vizinhos de
x e, consequentemente, x tem pelo menos tantos vizinhos quantos os vizinhos de y.
Analogamente se conclui que y tem pelo menos tantos vizinhos quantos os vizinhos de
x. Logo, podemos concluir x e y têm exactamente o mesmo número de vizinhos. Sendo
C um ciclo de comprimento 2d + 1, a partir de um dado vértice v, determinando os
dois vértices distintos de C à distância d de v, concluímos que ambos têm a valência
de v. Assim, todos os vértices de C têm a mesma valência. Considerando um vértice
arbitrário v fora de C bem como o caminho de comprimento i entre v e u ∈ V (C),
podemos concluir que existe em C um vértice w à distância d − i de u e, consequentemente, à distância dG (v, w) ≤ d − i + i. Porém, se dG (v, w) < d então existe um
ciclo de comprimento inferior a 2d o que é contraditório. Logo todos os vértices têm a
mesma valência
Theorem 1.2.5 (*). Dado um grafo G tal que k = b g(G)−1
c, verifica-se a
2
desigualdade
|V (G)|
≥ 1 + δ(G)
k−1
X
(δ(G) − 1)i .
(1.6)
i=0
Demonstração. Primeiramente, dado x ∈ V (G), vamos provar, por indução sobre
i, com 1 ≤ i ≤ k − 1, que o número de vértices à distância i de x é, pelo menos,
δ(G)(δ(G) − 1)i−1 , i.e, |{v ∈ V (G) : dG (x, v) = i}| ≥ δ(G)(δ(G) − 1)i−1 .
• O resultado é trivialmente verdadeiro para i = 1.
• Suponha-se que o resultado é verdadeiro para i = j, com 1 ≤ j < k − 1. Se
v ∈ V (G) é tal que dG (x, v) = j então (a) existe um único vizinho y de v à
distância j − 1 de x e (b) nenhum vizinho à distância j, conforme a seguir se
prova.
(a) Suponha-se que existem dois vértices vizinhos de v à distância j − 1. Então
existem dois caminhos distintos P 0 e P 00 , entre x e cada um destes vizinhos,
tais que comp(P 0 ) = comp(P 00 ) = j − 1 < k − 1, cuja união com as arestas
que os ligam a v contém um ciclo C tal que
comp(C) ≤ comp(P 0 )+comp(P 00 )+2 = 2j < 2k = 2b
g(G) − 1
c ≤ g(G)−1,
2
o que é contraditório.
(b) Suponha-se que existe um vértice z adjacente a v, à distância j de x. Então,
tal como anteriormente, existem dois caminhos distintos, P 0 e P 00 , entre x
e v e entre x e z, respectivamente, cuja união com a aresta vz contém um
ciclo C tal que
comp(C) ≤ comp(P 0 )+comp(P 00 )+1 = 2j+1 < 2k = 2b
g(G) − 1
c ≤ g(G)−1,
2
Resultados gerais
9
o que, mais uma vez, é contraditório.
Logo, para cada vértice v à distância j de x, existem pelo menos δ(G)−1 vértices
adjacentes a v à distância j + 1 de x e um único vértice adjacente a v à distância
j − 1 de x.
Analogamente se conclui que, para cada vértice y à distância j+1 de x, existe um
único vértice adjacente a y à distância j de x (dado que por hipótese 2(j + 1) ≤
2k < g(G)).
Uma vez que, por hipótese de indução, existem pelo menos δ(G)(δ(G) − 1)j−1
vértices à distância j de x, conclui-se que existem, pelo menos,
δ(G)(δ(G) − 1)j−1 (δ(G) − 1) = δ(G)(δ(G) − 1)j
S
vértices à distância j + 1. Consequentemente, tendo em conta que 0≤i≤k Vi ⊆
V (G), onde Vi = {v ∈ V (G) : dG (x, v) = i}, para i = 0, . . . , k, vem que
|V (G)|
≥
|V0 | + |V1 | + |V2 | + . . . + |Vk |,
≥
1 + δ(G) + δ(G)(δ(G) − 1) + . . . + δ(G)(δ(G) − 1)k−1 .
=
1 + δ(G)
k−1
X
(δ(G) − 1)j .
j=0
Deste teorema decorre imediatamente que se k = b g(G)−1
c e δ(G) > 2 então
2
|V (G)|
≥
1 + δ(G)
(δ(G) − 1)k − 1
.
δ(G) − 2
(1.7)
Um vértice v ∈ V (G) diz-se central em G se a maior das distâncias entre v
e os restantes vértices é a menor possível. Esta distância designa-se por raio de
G e denota-se por raio(G), pelo que
raio(G) = min{max{dG (v, x) : x ∈ V (G)} : v ∈ V (G)}.
Com facilidade se conclui que
raio(G) ≤ diam(G) ≤ 2raio(G).
(1.8)
Theorem 1.2.6 (*). Se G é um grafo tal que raio(G) ≤ r então
|V (G)| ≤ 1 + ∆(G)
r−1
X
(∆(G) − 1)i .
i=0
Demonstração. Seja v ∈ V (G) um vértice central
S em G e seja Vi = {x ∈ V (G) :
dG (v, x) = i},P
para i = 0, . . . , r. Então V (G) = ri=0 Vi e Vp ∩ Vq = ∅ ∀p 6= q, pelo
que |V (G)| = ri=0 |Vi |. Por outro lado, sabe-se que
|V0 |
=
1,
|V1 |
≤
∆(G),
|V2 |
≤
∆(G)|V1 | − |V1 | = |V1 |(∆(G) − 1) ≤ ∆(G)(∆(G) − 1),
|V3 |
..
.
≤
..
.
∆(G)|V2 | − |V2 | = |V2 |(∆(G) − 1) ≤ ∆(G)(∆(G) − 1)2 ,
..
.
|Vr |
≤
∆(G)|Vr−1 | − |Vr−1 | = |Vr−1 |(∆(G) − 1) ≤ ∆(G)(∆(G) − 1)r−1 ,
10
Conceitos e Resultados Básicos
donde vem que
|V (G)| =
r
X
|Vi | ≤ 1 + ∆(G)
i=0
r−1
X
(∆(G) − 1)i .
i=0
Como consequência imediata deste teorema, sendo diam(G) = d e tendo em
conta (1.8), conclui-se a desigualdade
|V (G)| ≤
1 + ∆(G)
d−1
X
(∆ − 1)i ,
(1.9)
i=0
a qual, para ∆(G) > 2, pode tomar a forma:
|V (G)| ≤
1 + ∆(G)
(∆(G) − 1)d − 1
.
∆(G) − 2
(1.10)
Tendo em conta as desigualdades (1.7) e (1.10), se diam(G) ≤ d, k =
c e δ(G) > 2, então
b g(G)−1
2
1 + δ(G)
d
(δ(G) − 1)k
δ(G) − 2
≤ |V (G)| ≤
1 + ∆(G)
(∆(G) − 1)
.
∆(G) − 2
(1.11)
Como exemplo de aplicação, considerando o grafo cúbico G representado na
Figura 1.4, onde g(G) = 5 (pelo que k = b g(G)−1
c = 2) e diam(G) = 3, vem
2
que
(3 − 1)2 − 1
(3 − 1)3 − 1
10 = 1 + 3
≤ |V (G)| ≤ 1 + 3
= 22.
3−2
3−2
6
1
4
3
5
7
8
9
2
12
11
10
Figura 1.4: Grafo cúbico G tal que g(G) = 5 e diam(G) = 3.
Theorem 1.2.7 (*). Sendo G um grafo conexo com diâmetro d, a desigualdade
(1.9) verifica-se na forma de igualdade se e somente se G é ∆-regular e g(G) =
2d + 1.
Demonstração. Seja G um grafo conexo tal que diam(G) = d.
1.3. GRAFOS BIPARTIDOS
11
• Se G não é ∆-regular então, tendo em conta a demonstração do Teorema 1.2.6, é
fácil concluir que a desigualdade (1.9) não se verifica na forma de igualdade (deve
observar-se que a escolha do diâmetro em vez do raio, na desigualdade, permite
que o vértice v do conjunto singular inicial V0 seja tal que dG (v) < ∆(G)).
• Suponha-se que G é ∆-regular e g(G) = 2d + 1. Nestas condições, fazendo k =
b g(G)−1
c, obtém-se k = d e, tendo em conta as igualdades δ(G) = ∆(G) = ∆,
2
combinando (1.9) com (1.6), vem que
1 + ∆(G)
d−1
X
(∆(G) − 1)i ≤ |V (G)| ≤ 1 + ∆(G)
d−1
X
(∆ − 1)i ,
i=0
i=0
ou seja,
|V (G)|
=
1 + ∆(G)
d−1
X
(∆(G) − 1)i .
(1.12)
i=0
Os grafos para os quais a desigualdade (1.9) se verifica na forma de igualdade, designam-se por grafos de Moore. Como consequência imediata do Teorema 1.2.7, os grafos de Moore são grafos conexos regulares com cintura 2d + 1,
onde d denota o diâmetro. Por outro lado, de acordo com os Teoremas 1.2.4 e
1.2.7, todo o grafo conexo com cintura 2d + 1, onde d denota o diâmetro, é um
grafo de Moore. O grafo de representado na capa deste texto é um exemplo de
grafo de Moore.
1.3
Grafos bipartidos
Um grafo G diz-se bipartido se existe uma partição do seu conjunto de vértices
em V 0 e V 00 tal que não existem arestas entre qualquer par de vértices de V 0
nem entre qualquer par de vértices de V 00 . Um tal grafo bipartido é usualmente
representado por G = (V 0 , V 00 , E), onde E denota o respectivo conjunto de
arestas. Quando |V 0 | = m, |V 00 | = n e ∀x ∈ V 0 ∀y ∈ V 00 , xy ∈ E(G) este grafo
denota-se por Kmn e designa-se por grafo bipartido completo.
Theorem 1.3.1. Um grafo admite uma bipartição se e só se não tem circuitos
de comprimento ímpar.
12
Conceitos e Resultados Básicos
Demonstração. Se G = (V 0 , V ”, E(G)) é um grafo bipartido, então é claro que
todos os circuitos têm comprimento par. Com efeito, uma vez que tanto em V’ como
em V"não existem vértices adjacentes, partindo-se, por exemplo, de um vértice em V’,
de cada vez que se passa para V", para se obter um circuito, tem de se voltar a V’
na aresta seguinte, pelo que qualquer circuito tem comprimento par. Suponhamos que
G não tem circuitos de comprimento ímpar. Uma vez que um grafo é bipartido sse
cada uma das suas componentes constitui um subgrafo bipartido, podemos supor, sem
perda de generalidade, que G é conexo. Considere-se um vértice arbitrário z ∈ V (G)
e seja V 0 = {w ∈ V (G) : dG (z, w) é ímpar}. Nestas condições não existem arestas
que liguem vértices de V 0 (caso contrário existiriam circuitos de comprimento ímpar).
Por outro lado, como todos os vértices de V (G) \ V 0 estão a uma distância par de z
(em particular z está a uma distância 0 dele próprio), não existem vértices adjacentes
em V (G) \ V 0 (uma vez que, por razões idênticas às anteriores, em tais condições,
existiriam circuitos de comprimento ímpar). Logo, fazendo V ” = V (G) \ V 0 obtém-se
uma bipartição para G, dada por G = (V 0 , V ”, E(G)).
Os grafos conexos acíclicos (i.e, sem ciclos) designam-se por árvores e constituem uma classe especial de grafos bipartidos. Por sua vez, designa-se por
floresta todo o grafo acíclico, pelo que uma floresta é um grafo cujas componentes
são árvores.
Theorem 1.3.2. Sendo G um grafo, são equivalentes as seguintes afirmações:
1. G é uma árvore.
2. G é conexo e tem |V (G)| − 1 arestas.
3. G não tem circuitos, mas acrescentando-se uma aresta a G resulta um
único circuito.
Demonstração. Para provar a implicação 1 ⇒ 2, dado que uma árvore é um grafo
conexo, basta provar que se G = (V (G), E(G)) é uma árvore, então tem |V (G)| − 1
arestas, para o que vamos utilizar indução sobre o número de arestas de grafos que
definem árvores. Seja Gk = (V (Gk ), E(Gk ) uma árvore comk arestas. Para k = 1
vem |V (G1 )| = 2, pelo que o resultado se verifica. Suponha-se que o resultado é
verdadeiro para k tal que 1 ≤ k ≤ n − 1 e considere-se a árvore Gn . Dado que Gn não
tem circuitos, existe pelo menos um vértice, v, com grau 1. Considerando o subgrafo
obtido de Gn , retirando-se o vértice v (e consequentemente a aresta que lhe é incidente),
determina-se Gn−1 que continua a ser uma árvore (uma vez que permanece conexo e
sem circuitos), logo, por hipótese de indução, E(Gn−1 ) = |V (Gn ) − 1| − 1. Dado que
|V (Gn )| = |V (Gn−1 )| + 1 concluí-se que Gn tem |V (Gn )| − 1 arestas, completando-se
assim a prova da implicação 1 ⇒ 2. A prova das implicações 2 ⇒ 3 e 3 ⇒ 1, fica como
exercício.
Theorem 1.3.3. Um grafo G é uma floresta se e só se
|E(G)| − |V (G)| + c(G) = 0,
onde c(G) denota o número de componentes de G.
Demonstração.
1.4. EXERCÍCIOS
13
⇒ A prova da condição necessária vai ser feita por indução sobre o número de arestas de G, tendo em conta que o resultado se verifica trivialmente para |E(G)| = 0.
Suponha-se |E(G)| > 0 e que o resultado se verifica para todas as florestas com
menos do que |E(G)| arestas. Seja G0 um subgrafo de G obtido por eliminação
de uma aresta arbitrária. Logo G0 é uma floresta com |E(G)| − 1 arestas, V (G)|
vértices e c(G) + 1 componentes. Por hipótese de indução, aplicada a G0 ,
0 = |E(G0 )|−|V (G0 )|+c(G0 ) = |E(G)|−1−|V (G)|+c(G)+1 = |E(G)|−|V (G)|+c(G).
⇐ Suponha-se
que G tem p componentes, G1 , . . . , Gp , pelo que |E(G)| − |V (G)| +
P
p = pj=1 (|E(Gj )| − |V (Gj )| + 1). Então
|E(G)| − |V (G)| + p = 0 ⇔
p
X
(|E(Gj )| − |V (Gj )| + 1) = 0
j=1
e, uma vez que ∀j ∈ {1, . . . , p} |E(Gj )| − |V (Gj )| + 1 ≥ 0, conclui-se que
∀j ∈ {1, . . . , p} |E(Gj )| − |V (Gj )| + 1 = 0.
Consequentemente, de acordo com o Teorema 1.3.2, todos os grafos Gj , com
j ∈ {1, . . . , p}, são árvores.
Deste teorema decorre que todo o grafo G tal que |E(G)| ≥ |V (G)| contém
pelo menos um circuito.
Dado um grafo conexo G, designa-se por árvore abrangente ou de suporte de
G todo o subgrafo de G que é uma árvore e contém todos os vértices de G.
Theorem 1.3.4. Todo o grafo conexo admite uma árvore abrangente.
Demonstração. Seja G um grafo conexo. Se G não tem circuitos então, por definição,
é uma árvore e o resultado verifica-se. Suponha-se que G tem um circuito. Então
retirando uma aresta a esse circuito o grafo mantém-se conexo (porquê?). Repetindo
este processo, ao fim de um número finito de arestas eliminadas, obtém-se uma árvore
abrangente (uma vez que o conjunto de vértices não foi alterado).
1.4
Exercícios
1.4.1. Sendo G um grafo de ordem n, com n ≥ 2, prove as seguintes afirmações:
(a) O número de vértices de grau ímpar é par.
(b) Existem dois vértices com o mesmo grau.
1.4.2. Dado um grafo H de ordem n ≥ 3, prove as seguintes afirmações:
(a) Se |E(H)| <
n(n−2)
,
4
então g(H c ) = 3.
(b) Se n ≥ 6, então H ou o seu complementar H c tem um triângulo.
14
Conceitos e Resultados Básicos
1.4.3. Seja G um grafo que não é uma árvore tal que diam(G) = 2.
(a) Supondo que G é bipartido e não é regular, determine g(G).
(b) Prove que se a ordem de G é 8 então g(G) 6= 5.
1.4.4. Considere o grafo H representado na Figura 1.4.
(a) Determine uma bipartição dos vértices de H em dois subconjuntos
V1 e V2 , de tal forma que (V1 , V2 , E(H)) defina um grafo bipartido.
(b) Determine uma árvore abrangente de H.
Capítulo 2
Grafos de Euler e Grafos de
Hamilton
2.1
Circuitos e trajectos de Euler
Um trajecto designa-se por trajecto de Euler se contém todos as arestas (logo
também todos os vértices) do grafo ou multigrafo a que se refere. Por sua vez,
designaŋse por circuito de Euler, todo o circuito que contenha todas as arestas
do grafo. O teorema a seguir estabelece uma condição necessária e suficiente
para a existência de um circuito de Euler.
Theorem 2.1.1. Um grafo (ou multigrafo) conexo G admite um circuito de
Euler se e somente se todos os seus vértices têm grau par.
Demonstração. Uma vez que é imediato verificar que a condição é necessárias,
vamos apenas provar que é suficientes, utilizando indução sobre o número de arestas
do grafo (ou multigrafo) G. Para um grafo (ou multigrafo) com uma única aresta o
resultado é trivial (se a aresta é um lacete, ou seja, existe um único vértice com grau
dois, então o grafo admite um circuito de Euler). Assumaŋse que todos os vértices de
G têm grau par e que todos os grafos (ou multigrafos) em tais condições com menos
arestas do que as de G admitem circuitos de Euler. Escolhaŋse um vértice v ∈ V (G)
e inicieŋse um trajecto segundo as arestas de G, sem se passar pela mesma aresta
duas vezes, até se encontrar v novamente (noteŋse que dada a paridade dos graus este
trajecto fechado existe). Posteriormente, retirandoŋse as arestas relativas ao trajecto
percorrido obtémŋse um certo número de subgrafos (ou submultigrafos) conexos que
cujos vértices continuam a ter grau par. Consequentemente, (por hipótese de indução)
admitem circuitos de Euler. Nestas condições, podemos criar um circuito de Euler para
G, acrescentando ao circuito inicial os circuitos de Euler de cada um dos subgrafos (ou
submultigrafos) obtidos.
Os únicos grafos não conexos, cujos vértices têm grau par, que admitem
circuitos de Euler são os que têm uma única componente com um número de
arestas superior a zero (i. e, as demais componentes são constituídas por vértices
isolados). Com base neste teorema fica claro que a pretenção dos habitantes de
Königsberg era impossível de satisfazer.
15
16
Grafos de Euler e Grafos de Hamilton
A prova construtiva do Teorema 2.1.1 sugere um algoritmo recursivo para
a determinação de circuitos de Euler em grafos ou multigrafos conexos, onde
todos os vértices têm grau par. Assim, denotando por Euler(G, v1 ) o algoritmo
recursivo para a determinação de um circuito de Euler num grafo ou multigrafo,
G, a partir de um vértice v1 ∈ V (G), est tem a seguinte formalização:
• Algoritmo Euler(G, v1 );
Se dG (v1 ) = 0
– então Euler(G, v1 ) := v1 ;
– senão faz
1. construir um circuito, C = (v1 , v2 , . . . , vk , v1 ), em G;
2. fazer G := (V (G), E(G) \ E(C));
3. devolver (Euler(G, v1 ), Euler(G, v2 ), . . . , Euler(G, vk ));
fim faz.
Fim do algoritmo.
O corolário que se segue estabelece as condições necessárias e suficientes para
a existência de um trajecto de Euler nos grafos que não admitem circuitos de
Euler (uma vez que um circuito de Euler é também um trajecto de Euler).
Corolário 2.1.2. Um grafo (ou multigrafo) conexo G admite um trajecto de
Euler, mas não um circuito de Euler, se e somente se tem exactamente dois
vértices de grau ímpar.
Demonstração. Se G admite um trajecto de Euler que não é um circuito, então,
uma vez que os vértices de partida e chegada são distintos, apenas estes têm grau
ímpar. Relativamente aos demais, em cada visita, foi utilizado uma aresta para atingir
o vértice e outra para o abandonar, pelo que têm grau par. Suponhaŋse que em G todos
os vértices têm grau par à excepção de dois. Então, pelo Teorema 2.1.1, é claro que
não existe um circuito de Euler, pelo que resta provar a existência de um trajecto de
Euler. Suponhaŋse que u e v são os vértices de grau ímpar em G e considereŋse o grafo
(ou multigrafo) G0 , E(G0 ) = E(G) ∪ {uv} (note-se que no caso da aresta uv já existir
em E(G), obtém-se um multigrafo, pelo que, nesse caso, E(G0 ) é um multiconjunto
com arestas repetidas). É claro que G0 satisfaz as hipóteses do Teorema 2.1.1, pelo que
admite um circuito de Euler. Se a este circuito retirarmos a aresta uv obtémŋse um
trajecto de Euler em G.
Os grafos (ou multigrafos) que admitem circuitos de Euler designam-se por
grafos de Euler ou eulerianos. Existem várias caracterizações de grafos (ou multigrafos) eulerianos, alternativas ao Teorema 2.1.1, das quais apenas vamos referir
a que se relaciona com a partição do conjunto de arestas em ciclos.
Theorem 2.1.3 (Veblen, 1912 *). Um grafo ou multigrafo conexo G não
nulo (ou seja, com pelo menos uma aresta) é euleriano sse E(G) admite uma
partição em arestas.
2.2. CICLOS DE HAMILTON
17
Demonstração. Supondo que G é euleriano, vamos provar, por indução sobre o
número de arestas, que então G admite uma partição em ciclos, tendo em conta que
o resultado é trivialmente verdadeiro para |E(G)|=1 (lacete). Com efeito, suponhaŋse
que o resultado é verdadeiro para grafos ou multigrafos conexos com um número de
arestas, m, tal que 1 ≤ m < |E(G)|. Uma vez para todo o vértice v ∈ V (G) dG (v) ≥ 2,
é claro que G contém um ciclo C. Logo, G − E(C) = (V (G), E(G) \ E(C)), é um grafo
(ou multigrafo), possivelmente desconexo, cujas vértices das componentes G1 , . . . , Gq
têm todos grau par. Consequentemente, cada componente é euleriana e, por hipótese
de indução, cada uma delas é a união disjunta de um conjunto, possivelmente vazio (no
caso da componente ser constituída por um vértice isolado) de ciclos. Se à união destes
conjuntos de ciclos (que constituem uma partição para cada uma das componentes)
adicionarmos o ciclo C, obtémŋse a partição desejada para G.
Reciprocamente, suponha-se que E(G) é a união disjunta dos ciclos C1 , . . . , Cp . Logo,
para todo o vértice v ∈ V (G), v pertence à intersecção de kv (kv ∈ N) ciclos do
conjunto {C1 , . . . , Cp }, donde vem que dG (v) = 2kv e, consequentemente, todos os
vértices têm grau par.
Um exemplo de aplicação (lúdico) deste corolário, está relacionado com passatempos em jornais e revistas onde se convida o leitor a testar se uma dada
figura pode ser decalcada sem se levantar a caneta e sem se repetir qualquer dos
segmentos e/ou curvas que o constituem.
2.2
Ciclos de Hamilton
Um ciclo que contém todos os vértices de um grafo, designa-se ciclo de Hamilton
(ou hamiltoniano). Por sua vez, um caminho que contém todos os vértices do
grafo diz-se um caminho de Hamilton (ou hamiltoniano). Um grafo que admite
um ciclo de Hamilton diz-se um grafo hamiltoniano. Conforme já se referiu na
introdução, a associação do nome do matemático irlandês Hamilton 1 a estes
grafos, deve-se ao facto de ter sido ele a propor e a resolver (em 1857) um
problema que designou por viagem à volta do mundo que consiste em percorrer
todos os vértices de um dodecaedro (ver Figura 2) passando uma única vez em
cada um, com partida e chegada no mesmo vértice. De acordo com (Berge, 1991)
Hamilton resolveu este problema observando que quando o viajante chega a um
dado vértice, percorrendo uma certa aresta, tem três opções: ou (L) continua
pela aresta da esquerda, ou (R) continua pela aresta da direita, (ou) (1) fica no
vértice (o que acontece quando percorre um ciclo). A partir desta observação
definiu estes procedimentos à custa de operações com L e R, representando,
por exemplo, por L2 R procedimento de voltar duas vezes seguidas à esquerda
e posteriormente à direita. Adicionalmente, considerou que duas sequências de
operações têm o mesmo resultado se, a partir de um mesmo vértice, ambas
conduzem a esse vértice. Este produto, embora não seja comutativo (uma vez que
LR 6= RL) é um produto associativo (por exemplo, (LL)R = L(LR)). Devido
ao facto das faces serem pentagonais é claro que R5 = L5 = 1 e, por outro lado,
1 Sir
William Rowan Hamilton nasceu em Dublin na Irlanda em 1805 e faleceu em 1865.
18
Grafos de Euler e Grafos de Hamilton
com facilidade se verifica que LR3 L = R2 . Com base nestas conclusões vem que
1
= R5 = R2 R3 = (LR3 L)R3 = (LR3 )2 = (L(LR3 L)R)2 = (L2 R3 LR)2
= (L2 (LR3 L)RLR)3 = (L3 R3 LRLR)3 = LLLRRRLRLRLLLRRRLRLR.
A sequência obtida contém 20 operações e nenhuma subsequência dá resultado 1 (pelo que não determina subciclos), logo representa um ciclo de Hamilton.
Noteŋse ainda que este ciclo se pode iniciar em qualquer dos 20 vértices do dodecaedro.
Com facilidade se conclui que também os restantes 4 poliedros convexos regulares, ou seja, o tetraedro, hexaedro, octaedro e icosaedro (que, conjuntamente
com o dodecaedro constituem os designados sólidos platónicos) admitem ciclos
de Hamilton. Outro exemplo de grafo hamiltoniano é o que se obtém, a partir
de um tabuleiro de xadrez, associando a cada um dos seus 64 quadrados um
vértice de um grafo G cujas arestas ligam os vértices associados a quadrados
entre as quais é possível efectuar um movimento de cavalo. Neste grafo, os ciclos de Hamilton correspondem a movimentos sucessivos de um cavalo de forma
a que todos os quadrados (brancos e pretos) são visitados uma única vez. Na
Figura 2.1 representa-se um dos ciclos de Hamilton possíveis para o referido
grafo.
Figura 2.1: Circuito de Hamilton.
Encontrar um ciclo de Hamilton num grafo de pequena dimensão que o
admita é relativamente fácil. Porém, quando a dimensão cresce, provar que não
Ciclos de Hamilton
19
existe qualquer ciclo de Hamilton pode tornar-se muito difícil. Na tentativa de
obtenção de ciclos de Hamilton deve ter-se em conta as seguintes três regras
básicas:
1. Se um vértice tem grau 2, então ambas as arestas incidentes no vértice
devem fazer parte do ciclo.
2. Não se deve obter qualquer subciclo (ou seja, não se deve percorrer um
ciclo que não contém todos os vértices).
3. Uma vez que se visite um dado vértice, todas as arestas incidentes nesse
vértice que não foram utilizadas podem ser eliminadas.
É claro que os grafos completos são hamiltonianos, pelo que, dado um grafo G
não hamiltoniano, adicionando arestas a G, necessariamente se obtém um grafo
hamiltoniano. O teorema a seguir, dá-nos uma condição suficiente para que um
grafo admita um ciclo de Hamilton.
Theorem 2.2.1 (Ore, 1960). Seja G um grafo de ordem n. Se para quaisquer
dois vértices não adjacentes a soma dos respectivos graus é não inferior a n,
então G é hamiltoniano.
Demonstração. Suponha-se que G é um grafo que satisfaz as hipóteses mas não é
hamiltoniano. Suponha-se ainda que G é um grafo maximal (relativamente ao número
de arestas) com esta propriedade, ou seja, é tal que acrescentando uma aresta se obtém
um ciclo de Hamilton2 . Uma vez que G não é completo (caso contrário admitiria
um ciclo de Hamilton), existem dois vértices não adjacentes, x, y ∈ V (G), e dado
que G é maximal (não hamiltoniano), por adição da aresta xy obtém-se um ciclo
de Hamilton que contém xy. Logo, G contém um caminho, entre x e y, que percorre
todos os restantes vértices de G, i.e., (após, eventual, reordenação dos vértices) contém
o caminho (x = v1 , v2 , . . . , vn−1 , vn = y). Seja Q(y) = {vi : vi−1 ∈ NG (y)} (uma vez
que o vértice y não é adjacente a ele próprio, i.e., y ∈
/ NG (y), o conjunto Q(y) está
bem definido e |Q(y)| = |NG (y)|).
Por hipótese, |NG (x)| + |Q(y)| ≥ n e, dado que v1 = x ∈
/ NG (x) e v1 6∈ Q(y), então
|NG (x)∪Q(y)| ≤ n−1 e, consequentemente, |NG (x)∩Q(y)| ≥ 1. Seja vi ∈ NG (x)∩Q(y)
e, a partir de x = v1 , considere-se o caminho (v1 , . . . , vi−1 ), o qual (uma vez que
vi−1 ∈ NG (y)) se pode estender ao caminho P1 = (v1 , . . . , vi−1 , vn ). A partir de y = vn ,
pode obter-se o caminho (vn , vn−1 , . . . , vi ) que, por sua vez (dado que vi ∈ NG (x)) se
pode estender ao caminho P2 = (vn , vn−1 , . . . , vi , v1 ). A partir dos caminhos P1 e P2
podemos construir um ciclo de Hamilton, o que contraria a hipótese.
Note-se que qualquer grafo que satisfaça as hipóteses do Teorema 2.2.1 é um
grafo conexo. Com efeito, supondo que G é um grafo de ordem n com k componentes, Gj , para j = 1, . . . , k, dados dois vértices pertencentes a componentes
distintas, x ∈ V (Gp ) e y ∈ V (Gq ) (com p, q ∈ {1, . . . , k}), vem que x e y não
são adjacentes e, adicionalmente, dG (x) ≤ |V (Gp )| e dG (y) ≤ |V (Gq )|. Logo,
dG (x) + dG (y) ≤ |V (Gp )| + |V (Gq )| − 2 < |V (G)|, o que contraria a hipótese do
2 Note-se que uma tal situação pode sempre ser atingida sem se alterarem as hipóteses (com
efeito, ao acrescentarem-se arestas, unindo vértices previamente não adjacentes, não só não
se faz decrescer o grau de nenhum vértice, como não se criam novos pares de vértices não
adjacentes).
20
Grafos de Euler e Grafos de Hamilton
Teorema 2.2.1.
Como corolário do Teorema 2.2.1, pode concluir-se o resultado obtido por Dirac,
oito anos antes do teorema de Ore ter sido provado.
Theorem 2.2.2 (Dirac, 1952). Seja G um grafo tal que |V (G)| ≥ 3. Se
δ(G) ≥ |V (G)|
, então G é hamiltoniano.
2
Deve observar-se, porém, que a hipótese do teorema de Dirac não pode ser
relaxada para δ(G) ≥ b |V (G)|
c. Com efeito, o grafo da figura a seguir satisfaz
2
esta última condição e, no entanto, não é hamiltoniano.
1
6
7
3
2
5
4
Figura 2.2: Grafo G não hamiltoniano tal que δ(G) ≥ b |V (G)|
c.
2
É claro que a um circuito de Euler num grafo G corresponde um ciclo de
Hamilton em L(G). Consequentemente, se G é euleriano, então L(G) é hamiltoniano. Considerando como subgrafo dominante de G todo o subgrafo G0 relativamente ao qual não existem vértices adjacentes em V (G) \ V (G0 ), em (Harary
and Nash-Williams, 1965) relacionam-se os ciclos de Hamilton de L(G) com os
circuitos de Euler de G da seguinte forma:
Sendo G um grafo conexo tal que |E(G)| ≥ 3, L(G) é hamiltoniano
se e só se G tem um subgrafo euleriano dominante.
2.3
Código de Gray *
Segue-se uma aplicação directa, muito simples, dos ciclos de Hamilton. Certos
instrumentos contadores representam números reais por sequências de dígitos de
comprimento fixo (como, por exemplo, os conta-quilómetros dos automóveis).
Com estes dispositivos, na maioria dos casos, os números vão variando com a
modificação de um único dígito. Porém, em certas situações, a mudança do número obriga à troca de vários dígitos, como no caso da passagem de 189.999 para
190.000, operação que provoca alguns problemas mecânicos de difícil resolução.
Nestas passagens, qualquer avaria (mesmo que pontual) no dispositivo mecânico
pode provocar erros consideráveis. Para evitar estes erros, podemos definir uma
sequência de números de tal forma que de um número para outro apenas se
troca um dígito. Com estas sequências, uma avaria pontual (ausência atempada
de resposta do dispositivo mecânico) apenas provoca o erro de uma unidade. No
caso destas sequências se referirem a representações binárias de números, elas
Código de Gray
21
são conhecidas como códigos de Gray. Um grafo, cujos vértices são os n-uplos
xn−1 , xn−2 , . . . , x1 , x0 , de zeros e uns, tais que dois vértices são adjacentes se
diferem num único dígito designa-se, usualmente, por n-cubo e denota-se por
Qn (deve observar-se que, neste n-cubo, existem 2n vértices, cada um dos quais
associado a um número, entre 0 e 2n−1 , representado numa base binária). Na
Figura 2.3 apresentam-se os k-cubos, com k = 0, 1, 2, 3.
110
10
11
111
010
011
100
0
Q0
1
Q1
00
01
000
Q2
101
001
Q3
Figura 2.3: Representação dos k-cubos, com k = 0, . . . , 3.
Um código de Gray corresponde a um ciclo de Hamilton no n-cubo Qn e a
existência de um tal ciclo fica garantida pelo teorema que se segue.
Theorem 2.3.1. Se n ≥ 2, então o grafo Qn é hamiltoniano.
Demonstração. A prova será feita por indução sobre n, tendo em conta que, para
n = 2, Q2 é um ciclo com 4 arestas, pelo que o resultado é verdadeiro (uma vez que
se pode obter o ciclo de Hamilton (00, 01, 11, 10, 00)).
Supondo que existe o ciclo de Hamilton em Qn , (v0 , v1 , . . . , v2n −2 , v2n −1 , v0 ), é claro
que (0v0 , 0v1 , . . . , 0v2n −2 , 0v2n −1 , 1v2n −1 , 1v2n − 2, . . . , 1v1 , 1v0 , 0v0 ) é um ciclo de Hamilton em Qn+1 .
Na prática, para a codificação e descodificação dos números, é necessário
conhecer a posição de cada vértice no ciclo de Hamilton que define o código de
Gray. Um modo fácil de o conseguir, consiste em construir o código de Gray de
comprimento 2n+1 , a partir do código de Gray de comprimento 2n , tal como se
procedeu na demonstração do Teorema 2.3.1, primeiro percorrendo a sequência
de vértices do caminho de Hamilton de Qn , entre 0 e 2n−1 , colocando um 0 na
posição mais à esquerda e, posteriormente, percorrendo o mesmo caminho pela
ordem inversa, colocando 1 nessa mesma posição. O teorema a seguir indica um
modo sistemática para a obtenção das diferentes representações do código de
Gray com cadeias binárias de n de dígitos.
Theorem 2.3.2. Considerem-se os vértices do ciclo de Hamilton de Qn (construído tal como anteriormente se indicou), etiquetados com 0, 1, 2, . . . , 2n −
2, 2n − 1, segundo a ordem pela qual são visitados. Se 2k (com 0 ≤ k ≤ n − 1)
é a maior potência de 2 que divide p ∈ {1, 2, . . . , 2n−1 }, então no p-ésimo número binário representado, αp , o dígito que se modifica (em relação ao vértice
anterior, i.e., em relação ao vértice de ordem p − 1) é o k-ésimo a partir da
direita.
Demonstração. Esta prova vai ser feita por indução sobre n, tendo em conta que
para n = 2 se obtém a sequência representada na tabela a seguir.
22
Grafos de Euler e Grafos de Hamilton
p
0
1
2
3
αp
00
01
11
10
k
2k
0
1
0
1
2
1
Supondo que a afirmação anterior é verdadeira para 2 ≤ n ≤ N , vamos analisar o
comportamento da sequência de números binários para n = N + 1.
Para os primeiros p números representados, com 0 ≤ p ≤ 2N − 1, vem que
αp = 0aN −1 aN −2 . . . a1 a0 ,
logo, por hipótese de indução, se 2k é a maior potência de 2 que divide p, então, na
passagem de αp−1 para αp é o k-ésimo dígito binário (a contar da direita) que se
modifica. Para p = 2N , o dígito que se modifica é o N -ésimo, pelo que a afirmação
continua válida. Por sua vez, para p = 2N + τ , com 0 ≤ τ ≤ 2N − 1, verifica-se que
αp coincide com αp−2τ −1 em todos os dígitos à excepção do dígito mais à esquerda
(que para αp tem o valor 1 e para αp−2τ −1 tem o valor 0). Se 2k a maior potência
de 2 que divide p = 2N + τ , então p = 2k (2N −k + q), com τ = 2k q e p − 2τ − 1 =
2N − τ − 1 = 2k (2N −k − q) − 1, donde se pode concluir que 2k é a maior potência de 2
que divide (p − 2τ − 1) + 1 = p − 2τ . Como consequência, o k-ésimo dígito (a contar
da direita) do número αp−2τ alterou-se em relação a αp−2τ −1 , logo o k-ésimo dígito (a
contar da direita) de αp alterou-se em relação a αp−1 (uma vez que, com excepção do
dígito mais à esquerda, os dígitos de αp coincidem com os de αp−2τ −1 , e os de αp−1
coincidem com os de α(p−1)−2(τ −1)−1 = αp−2τ ).
A tabela a seguir dá-nos a sequência de representações binárias produzidas
pelo código de Gray, para n = 4 (com indicação, na primeira coluna, da ordem segundo a qual o código produz cada uma das cadeias de dígitos binários
obtidas).
p
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
αp
0000
0001
0011
0010
0110
0111
0101
0100
1100
1101
1111
1110
1010
1011
1001
1000
Com o processo de construção anteriormente referido, podemos obter as
regras de codificação e descodificação que o teorema a seguir indica.
Código de Gray
23
Theorem 2.3.3. O código de Gray obtido pelo ciclo de Hamilton que percorre
o n-cubo, conforme anteriormente se referiu, admite as seguintes regras de codificação e descodificação:
1. Se p = bn−1 . . . b0 , onde b0 , . . . , bn−1 são dígitos binários, então
αp = an−1 . . . a0 ,
com aj = bj + bj+1 (mod 2), convencionando-se que bn = 0, para j =
0, . . . , n − 1, ocupa a p-ésima posição.
2. Se αp = an−1 . . . a0 , onde a0 , . . . , an−1 são dígitos binários, então p =
bn−1 . . . b0 , com
bi =
n−1
X
aj (mod 2), para i = 0, . . . , n − 1.
j=i
Demonstração. Vamos fazer a prova de 1 por indução sobre n (número de dígitos
binários das cadeias produzidas pelo código), tendo em conta que para n = 1 a regra
1 é trivialmente válida.
Suponha-se que a regra 1 é válida para 1 ≤ n ≤ N e que dispomos de um código
com cadeias binárias de comprimento N + 1. Sendo αp uma dessas cadeias, se p ≤
2N − 1, então (a menos do zero mais à esquerda) a representação de αp coincide
com a representação produzida pelo código de comprimento N . Logo, por hipótese de
indução, a regra é válida.
Suponha-se que p ≥ 2N e seja p0 = 2N +1 − 1 − p (i.e., p = 2N +1 − 1 − p0 ). Então,
podemos concluir que a regra 1 se verifica para p0 , uma vez que p0 = 2N +1 − 1 − p ≤
2N +1 − 1 − 2N = 2N (2 − 1) − 1 = 2N − 1. Porém, os dígitos binários das cadeias que
representam αp = aN . . . a0 e αp0 = a0N . . . a00 , estão relacionados da seguinte forma:
aj
=
a0j , para j = 0, . . . , N − 1,
aN
=
1,
a0N
=
0,
pelo que aN = a0N + 1. Por outro lado, tendo em conta que p + p0 = 2N +1 − 1 =
11 . . . 111, sendo p = bN . . . b0 e p0 = b0N . . . b00 , vem que bi = b0i + 1 (mod 2) (ou
seja, se b0i = 0, então bi = 1 e se b0i = 1, então bi = 0). Como consequência, vem que
ai = a0i = b0i + b0i+1 (mod 2) = bi + bi+1 (mod 2), para i = 0, . . . , N − 1. Adicionalmente,
aN = a0N +1 (mod 2) = b0N +b0N +1 +1(mod 2) = bN +bN +1 (mod 2) (uma vez que b0N = 0,
b0N +1 = 0, bN = 1 e bN +1 = 0). Deste modo fica completa a prova de 1.
A prova de 2 obtém-se invertendo 1. Com efeito, tendo em conta a sequência de somas
24
Grafos de Euler e Grafos de Hamilton
0 = b0 + b1 (mod 2), a1 = b1 + b2 (mod 2), . . . , aN = bn + bN +1 (mod 2), vem que
ai (mod 2)
=
bi + bi+1 (mod 2)
⇓
ai + ai+1 (mod 2)
=
bi + bi+1 + bi+1 + bi+2 (mod 2) = bi + bi+2 (mod 2)
⇓
ai + ai+1 + ai+2 (mod 2)
=
bi + bi+2 + bi+2 + bi+3 (mod 2) = bi + bi+3 (mod 2)
⇓
..
.
⇓
ai + ai+1 + . . . + aN (mod 2) = bi + bN +1 (mod 2) = bi (uma vez que bN +1 = 0).
PN
Logo vem que bi =
j=1 aj (mod 2), para i = 0, . . . , N , conforme se pretendia
demonstrar.
2.4
Exercícios
2.4.1. Prove que se G é euleriano, então L(G) é hamiltoniano.
2.4.2. Dado um grafo G, sabendo que um conjunto S ⊆ V (G) é (k, τ )-regular se
induz um subgrafo k-regular tal que
∀v ∈ V (G) \ S
|NG (v) ∩ S| = τ,
prove que G é hamiltoniano se e só se o seu grafo linha tem um conjunto
de vértices (2, 4)-regular que induz um subgrafo conexo.
2.4.3. Indique os valores de p ∈ N para os quais Kp,p é hamiltoniano.
2.4.4. Um grafo sequencial é um grafo com m arestas (m ≥ 3) e1 , e2 , . . . , em , tais
que ei e ei+1 são adjacentes, para i = 1, . . . , m − 1 e em e e1 são também
adjacentes. Prove que todo o grafo hamiltoniano é sequencial.
Capítulo 3
Grafos Planares e
Generalizações
Os exemplos mais naturais de grafos são os que se referem à representação de
mapas de estradas. Em muitos casos, na ausência de viadutos, trata-se de grafos que apresentam a particularidade de se poderem representar numa folha de
papel sem que as arestas se cruzem, uma vez que aos cruzamentos e entroncamentos correspondem vértices. Quando um grafo, G, admite uma representação
numa superfície, S, sem que existam arestas que se intersectem, diz-se que G
é realizável em S. Um grafo diz-se planar se é realizável no plano. Note-se que,
apesar de um dado grafo admitir uma representação com arestas cruzadas, isso
não significa que esse grafo não seja planar. Com efeito, pode existir outro modo
de o representar onde não ocorram arestas cruzadas.
3.1
Duais de grafos e digrafos planares
Dado um grafo planar, G, designa-se por grafo dual1 de G e denota-se por G∗
o grafo (multigrafo) obtido de G por aplicação do seguinte procedimento:
1. A cada face de G faz-se corresponder um vértice de G∗ .
2. A cada aresta e ∈ E(G) faz-se corresponder uma aresta e∗ ∈ E(G∗ ) que
liga duas faces (vértices de V (G∗ )) vizinhas, cruzando a aresta e.
−
→
No caso de grafos orientados, G , com excepção dos lacetes, cujo sentido é arbi−
→
trário, o sentido de cada um dos arcos, a∗ ∈ A( G ∗ ), é determinado dividindo o
ciclo orientado C que limita a face correspondente ao vértice incidente v ∗ em C +
e C − (consoante os arcos estejam no sentido positivo ou negativo). Se a ∈ C + ,
1 Alguns autores designam este dual por dual geométrico para o distinguir do dual abstracto, do dual algébrico e do dual combinatório, tendo sido o primeiro proposto por Whitney
(Whitney, 1932) e por Lovasz (Lovasz, 1979), o segundo por Wilson (Wilson, 1972) e o terceiro
por Harary (Harary, 1969).
25
26
Grafos Planares e Generalizações
−
→
então o arco de A( G ∗ ) que o intersecta tem cauda em v ∗ , caso contrário esse
arco tem cabeça em v ∗ .
Theorem 3.1.1 (*). Sendo G um grafo planar e G∗ o correspondente dual,
podemos concluir o seguinte:
1. G∗ é conexo;
∗
2. se G é conexo, então (G∗ ) = G.
Demonstração.
1. Uma vez que podemos passar de uma face fi para qualquer outra face fj de G
ao longo das arestas de G∗ , conclui-se que existe um caminho entre quaisquer
dois vértices, vi∗ e vj∗ , de V (G∗ ).
2. Por construção de G∗ , sabe-se que |V (G∗ )| = |F0 (G)| e |E(G∗ )| = |E(G)|. Uma
vez que cada aresta da fronteira de cada elemento de F0 (G∗ ) é atravessada por
uma aresta de G, é claro que cada face de G∗ contém, pelo menos, um vértice de
G. Adicionalmente, tendo em conta que G é conexo, por aplicação da fórmula
de Euler, pode concluir-se que |F0 (G∗ )| = |V (G)|, pelo que cada elemento de
F0 (G∗ ) contém, exactamente, um vértice de G. Consequentemente, partindo-se
de G∗ e aplicando o procedimento de construção do dual de G∗ , obtém-se a
construção inicial, i.e., (G∗ )∗ = G.
3.2
Fórmula de Euler e aplicações
Dada uma representação plana de um grafo planar, a qual pode ser obtida pela
projecção estereográfica de uma realização do grafo na esfera, para além das
regiões ou faces limitadas, existe uma região ou face exterior ao grafo (i. e, a
porção de espaço que o envolve) que se designa por região ou face ilimitada.
Neste texto, F0 (G) denota o conjunto de faces de uma realização plana de um
grafo G.
O teorema que se segue consta (sem prova) numa carta enviada por Euler, em
1750, a Goldbach. De acordo com (Beineke, 1997), as primeiras demonstrações
da fórmula de Euler para grafos planares, foram obtidas por Legendre (em 1794),
l’Huilier em (1811 e 1812) e Cauchy em (1813).
Theorem 3.2.1 (da Fórmula de Euler, 1750). Se G é um grafo conexo e
planar então, para uma sua realização plana, verifica-se a igualdade
|F0 (G)| = |E(G)| − |V (G)| + 2.
Demonstração. Vamos fazer a prova por indução sobre o número de arestas, tendo
em conta que o resultado é verdadeiro para grafos conexos planares não nulos com
zero (0 − 1 + 2 = 1) ou uma aresta. No segundo caso se |E(G)| = 1 então |V (G)| = 2
e |F0 (G)| = 1 e obtém-se a igualdade 1 − 2 + 2 = 1.
Seja Gn um grafo obtido após a representação de n arestas. Em geral, para n > 1,
o grafo Gn obtém-se a partir de Gn−1 acrescentando a E(Gn−1 ) uma aresta, de uma
das seguintes formas:
Fórmula de Euler e aplicações
27
1. A nova aresta incide em vértices de Gn−1 (ou seja, liga dois vértices x, y ∈
V (Gn−1 ) = V (Gn )).
2. A nova aresta liga um vértice de Gn−1 a um novo vértice (pelo que x ∈ V (Gn−1 ) =
V (Gn ) \ {y}).
Seja n > 1 e, por hipótese de indução, vamos supor que a fórmula de Euler é verdadeira
para grafos conexos planares com menos do que n arestas.
Em 1, a nova arestas vai provocar o aparecimento de um novo ciclo, consequentemente,
uma nova face, pelo que |F0 (Gn )| = |F0 (Gn−1 )| + 1. Assim, dado que |E(Gn )| =
|E(Gn−1 )| + 1 e V (Gn ) = V (Gn−1 ), conclui-se que a fórmula de Euler continua válida
para Gn .
Em 2, a nova aresta não provoca o aparecimento de nenhuma face, pelo que |F0 (Gn )| =
|F0 (Gn−1 )|. Uma vez que |E(Gn )| = |E(Gn−1 )|+1 e |V (Gn )| = |V (Gn−1 )|+1, conclui-se que a fórmula de Euler também se verifica para Gn .
3.2.1
Condições necessárias para grafos planares
Embora o Teorema 3.2.1 seja válido para multigrafos, tal não acontece para o
corolário que se segue.
Corolário 3.2.2 (do teorema que estabelece a fórmula de Euler). Se G
é um grafo conexo e planar, com |E(G)| > 1, então |E(G)| ≤ 3|V (G)| − 6.
Demonstração. Defina-se o grau de uma região como sendo o número de arestas da
sua fronteira considerando-se que se uma aresta ocorre duas vezes ao longo da fronteira
de uma dada região (como acontece, por exemplo, com as arestas incidentes em vértices
de grau 1), então conta também duas vezes para a determinação do respectivo grau.
Uma vez que cada região de um grafo planar G (com |E(G)| > 1) tem grau não inferior
a 3, podemos concluir que a soma dos graus de todas as regiões r é não inferior a 3r. Por
outro lado, esta soma dos graus de todas as regiões é igual a 2|E(G)| (dado que cada
aresta conta duas vezes para esta soma). Como consequência, obtém-se a desigualdade
3r ≤ 2|E(G)|. Combinando esta desigualdade com a fórmula de Euler vem que
3(|E(G)| − |V (G)| + 2) ≤ 2|E(G)| ⇔ |E(G)| ≤ 3|V (G)| − 6.
Como consequência imediata deste corolário, podemos concluir que o grafo
completo de ordem 5 (que usualmente se denota por K5 ) não é um grafo planar.
Com efeito, |E(K5 )| = 10 > 9 = 3|V (K5 )| − 6.
Note-se, porém, que existem grafos não planares, G, que satisfazem a desigualdade |E(G)| ≤ 3|V (G)| − 6, conforme a figura a seguir ilustra.
Um outro modo de utilizar o Corolário 3.2.2 para se concluir se um grafo
é ou não planar, consiste em produzir alterações no grafo (as quais não devem
destruir a eventual propriedade de ser planar) e mostrar que o grafo obtido não
satisfaz o corolário. Uma das alterações mais usuais, utiliza a contracção de uma
das arestas do grafo G em estudo, a qual faz decrescer o número de aresta de
uma unidade e o número 3|V (G)| − 6 de 3 unidades, pelo que a desigualdade
do Corolário 3.2.2 poderá passar a ser não satisfeita. Com o recurso a estas
contracções, porém, deve ter-se o cuidado de não se produzirem lacetes nem
arestas paralelas, uma vez que o corolário não é válido para multigrafos.
28
Grafos Planares e Generalizações
1
6
3
5
2
4
Figura 3.1: Exemplo de um grafo G não planar que satisfaz a desigualdade
|E(G)| ≤ 3|V (G)| − 6.
O corolário a seguir vai permitir a conclusão de que o grafo bipartido completo K3,3 não é planar. Tal como o Corolário 3.2.2, este corolário também só é
válido para grafos.
Corolário 3.2.3 (do teorema que estabelece a fórmula de Euler). Se G é
um grafo conexo bipartido planar com |E(G)| > 1, então |E(G)| ≤ 2|V (G)| − 4.
Demonstração. Esta prova é idêntica à do Corolário 3.2.2, tendo em conta que,
desta vez, (de acordo com o Teorema 1.3.1) qualquer circuito de um grafo bipartido
tem comprimento par. Logo, cada região (ou face) de um grafo conexo bipartido planar
tem grau não inferior a 4. Como consequência, sendo r o número de regiões do grafo
conexo bipartido planar G, vem que
4r ≤ 2|E(G)| ⇔ 4(|E(G)| − |V (G)| + 2) ≤ 2|E(G)| ⇔ |E(G)| ≤ 2|V (G)| − 4.
Deste corolário decorre imediatamente que K3,3 é não planar. Com efeito,
|E(K3,3 )| = 9 > 8 = 2|V (K3,3 )| − 4. Como consequência, podemos afirmar que
dos Corolários 3.2.2 e 3.2.3 decorre a suficiência das condições de Kuratowski
para que um grafo não seja planar. A prova de que a condição de Kuratowski
(ver Teorema 3.2.5) é também necessária para que um grafo seja planar pode
ser encontrada em (Diestel, 1997).
Theorem 3.2.4. Todo o grafo conexo planar tem, pelo menos, um vértice de
grau não superior a 5.
Demonstração. Sendo G um grafo conexo planar e ni o número de vértices de grau
i (com δ(G) ≤ i ≤ ∆(G)), obtêm-se as equações:
∆(G)
2|E(G)|
=
X
i × n1 ,
i=δ(G)
∆(G)
|V (G)|
=
X
ni .
i=δ(G)
Fazendo as respectivas substituições na desigualdade obtida no Corolário 3.2.2, vem
que
∆(G)
∆(G)
∆(G)
X
1 X
1 X
i × n1 ≤ 3
ni − 6 ⇔
ni (6 − i) ≥ 6.
2
2
i=δ(G)
i=δ(G)
i=δ(G)
Fórmula de Euler e aplicações
29
Logo, existe pelo menos um vértice com grau inferior a 6.
Particularizando o resultado anterior para os grafos bipartidos planares, com
facilidade se conclui a existência, nestes grafos, de pelo menos um vértice de grau
não superior a 3 (ver Exercício 3.4.2)
3.2.2
Condições necessárias e suficientes para grafos planares *
Theorem 3.2.5 (Kuratowski, 1930). Se G é um grafo, então são equivalentes
as seguintes afirmações:
1. G é planar;
2. G não contém K5 nem K3,3 como menores combinatórios;
3. G não contém K5 nem K3,3 como menores topológicos.
Demonstração.
(1 ⇒ 2) Se G é um grafo planar, então qualquer dos seus menores, G0 , é um grafo planar
e, pelo Corolário 3.2.2, |E(G0 )| ≤ 3|V (G0 )| − 6. Logo, uma vez que K5 não é
planar (10 = |E(K5 )| > 3|V (K5 )| − 6 = 9), conclui-se que K5 não é um menor
de G. Identicamente, no caso de G admitir como menor um grafo bipartido, G0 ,
do Corolário 3.2.3 decorre a desigualdade |E(G0 )| ≤ 2|V (G0 )| − 4 e, uma vez que
K3,3 não a satisfaz (9 = |E(K3,3 )| > 2|V (K3,3 )| − 4 = 8), conclui-se que não é
um menor de G.
(2 ⇒ 3) Dado que qualquer menor topológico de um grafo G é também um menor combinatório, se G não admite K5 nem K3,3 como menores combinatórios, então
também não admite K5 nem K3,3 como menores topológicos, uma vez que estes
também são combinatórios.
(3 ⇒ 1) Esta prova pode ser consultada, por exemplo, em (Distel, 1995) ou (Parthasarathy, 1994).
Dado um grafo conexo G, designa-se por corte (ou cocircuito) de G todo o
conjunto de arestas que desconexa G. Assim, dada uma partição de V (G) nos
subconjuntos não vazios V1 e V2 , o subconjunto de aresta com um extremo em
V1 e outro em V2 é um corte (ou cocircuito) de G que se denota por E(V1 , V2 ).
Neste caso, usualmente, o corte E(V1 , V2 ) também se denota por ∂(V1 ) ou ∂(V2 )
que corresponde ao conjunto de arestas de G com um único extrema em V1 ou
com um único extremo em V2 , consoante o caso.
Tendo em conta que G∗ é um dual algébrico de G se existe uma função
φ : E(G) → E(G∗ ) tal que C é um ciclo de G se e somente se φ(C) é um
corte (cocircuito) de G∗ , Whitney introduziu a seguinte condição necessária e
suficiente para um grafo ser planar:
Theorem 3.2.6 (Whitney, 1932). Um grafo é planar se e somente se admite
um dual algébrico.
Demonstração. Ver [31] e [32].
30
Grafos Planares e Generalizações
3.2.3
Grafos platónicos
Um grafo diz-se platónico se é constituído por um único vértice, ou se é um grafo
com mais do que uma aresta, conexo, planar, regular, no qual todas as faces
têm o mesmo grau. São grafos platónicos, o grafo constituído por um vértice
isolado (K1 ), os grafos cíclicos (que correspondem aos polígonos regulares), e os
grafos formados pelas arestas dos 5 poliedros convexos regulares: o tetraedro, o
hexaedro (ou cubo), o octaedro, o dodecaedro e o icosaedro. Um polígono regular
é uma figura poligonal fechada limitada por um número finito de segmentos
(arestas) com igual comprimento e com os mesmos ângulos. Existe um número
infinito de polígonos regulares, aos quais correspondem grafos cíclicos.
O teorema a seguir estabelece a existência de apenas 5 poliedros regulares
distintos com mais do que duas faces (aos quais correspondem cinco grafos
platónicos).
Theorem 3.2.7. Existem somente 5 grafos platónicos distintos de K1 e dos
grafos cíclicos.
Demonstração. Seja G um grafo d-regular (i.e., qualquer que seja v ∈ V (G) dG (v) =
d), onde cada face tem grau f . Uma vez que G 6= K1 , podemos concluir que d > 0 e,
dado que |E(G)| > 1, podemos concluir ainda que d > 1. Adicionalmente, dado que G
não é um grafo cíclico, conclui-se que d > 2, ou seja, d ≥ 3 e é claro que f ≥ 3,
f |F0 (G)| = 2|E(G)| = d|V (G)| ⇒ |E(G)| =
d|V (G)|
,
2
. Como consequência, uma vez que G é planar, por aplicação da
e |F0 (G)| = 2|E(G)|
f
fórmula de Euler, vem que
2|E(G)|
d|V (G)|
=
− |V (G)| + 2
f
2
⇔
⇔
⇔
d|V (G)|
d|V (G)|
=
− |V (G)| + 2
f
2
d
d
|V (G)|( + 1 − ) = 2
f
2
|V (G)|(2d + 2f − f d) = 4f
(3.1)
Da igualdade (3.1) decorre a inequação
2d + 2f − f d > 0 ⇔ −2d − 2f + f d + 4 < 4 ⇔ (f − 2)(d − 2) < 4,
a qual, para f ≥ 3 e d ≥ 3, apresenta como possíveis soluções apenas os pares de
valores (d, f ): (3, 3), (3, 4), (3, 5), (4, 3) e (5, 3) que correspondem, respectivamente, ao
tetraedro, ao hexaedro, ao dodecaedro, ao octaedro e ao icosaedro.
4f
Utilizando a igualdade (3.1), da qual se conclui que |V (G)| = 2f +2d−f
d,
podemos obter a tabela a seguir, onde se apresentam os graus dos vértices (d),
os graus das faces (f), o número de vértices, o número de arestas e o número de
faces, para cada um dos poliedros convexos regulares associados aos diferentes
grafos platónicos.
3.3. GRAFOS EM VARIEDADES COMPACTAS ORIENTÁVEIS
d
3
3
3
4
5
f
3
4
5
3
3
|V (G)|
4
8
20
6
12
|E(G)|
6
12
30
12
30
|F0 (G)|
4
6
12
8
20
31
Designação
Tetraedro
Hexaedro
Dodecaedro
Octaedro
Icosaedro
Na Figura 3.2 representam-se os 5 grafos platónicos. Na primeira linha o
tetraedro, o hexaedro e o octaedro e na segunda linha o dodecaedro e o icosaedro.
Figura 3.2: Grafos platónicos.
3.3
Grafos em variedades compactas orientáveis
Uma vez que a projecção estereográfica converte figuras do planar em figuras
da esfera e reciprocamente, podemos afirmar que um grafo é planar se e só se é
realizável na esfera. Nesta secção, excepção feita ao planar (que não é compacto),
vamos considerar unicamente realizações de grafos em variedades compactas de
dimensão 2 orientáveis. Uma variedade compacta de dimensão 2 é uma superfície
S com as seguintes propriedades:
1. cada ponto de S tem uma vizinhança homeomorfa a uma bola aberta;
2. toda a cobertura de S, com bolas abertas, tem uma subcobertura finita.
Adicionalmente, dizemos que esta superfície S é orientável se é possível definir
um referencial tridimensional (com dois eixos no planar tangente à superfície)
que se desloque ao longo de qualquer curva fechada representada em S, sem
alterar o sentido dos eixos quando regressa ao ponto inicial.
Mais particularmente, nesta secção, apenas vamos considerar a esfera (S0 ), torus
(S1 ), duplo torus (S2 ), triplo torus (S3 ), etc., ou superfícies topologicamente
equivalentes a estas. Tais superfícies serão denotadas, genericamente, de agora
32
Grafos Planares e Generalizações
em diante, por Sg , onde g denota o genus da superfície. A realização de um
grafo G numa superfície Sg , implica que cada vértice de G corresponda a um
ponto de Sg e cada aresta corresponda a uma curva simples (ver definição mais
adiante), ligando dois vértices e que nenhum par de curvas se intersecte em
nenhum ponto com excepção dos respectivos pontos extremos (vértices). Assim,
do ponto de vista topológico, um grafo G é um par (V (G), E(G)), onde E(G)
denota um conjunto finito de curvas simples de Sg (que também se designam por
arestas), tais que duas quaisquer delas ou têm intersecção vazia ou se intersectam
numa das suas extremidades, e V (G) denota o conjunto de vértices, os quais
correspondem às extremidades das curvas. Neste contexto, diz-se que um grafo,
G, é conexo, se quaisquer dois vértices se podem ligar por uma curva ou por
concatenação de várias curvas (arestas) de E(G). Uma curva em E2 (espaço
euclidiano de dimensão 2) é um subconjunto de E2 , C, para o qual existe uma
aplicação contínua injectiva c : [0, 1] → E2 tal que c([0, 1]) = C. Se c é apenas
injectiva em [0, 1[ e c(0) = c(1), diz-se que C é uma curva fechada de Jordan.
Nestas condições, uma curva é um subconjunto de E2 homeomorfo ao intervalo
[0, 1] e uma curva fechada de Jordan é um subconjunto de E2 homeomorfo à
circunferência. Qualquer destas curvas, C, se designa por curva simples e a
respectiva aplicação, c, por parametrização de C.
Tendo em conta que um subconjunto C de um espaço E separa esse espaço, se
E \ C tem mais do que uma componente conexa, Camille Jordan (1838-1922)
provou, nos anos de 1887-1893, o teorema de separação para E2 que a seguir se
apresenta.
Theorem 3.3.1 (da curva fechada de Jordan). Se C é uma curva fechada
de Jordan em E2 , então C separa E2 .
Demonstração. Ver, por exemplo, (Armstrong, 1997), pag. 112-113.
Deste teorema decorre que sendo C uma curva fechada de Jordan em E2 ,
então E2 \ C é a união disjunta de dois conjuntos abertos, dint(C) (domínio
interior a C) e dext(C) (domínio exterior a C), tais que dint(C) é limitado,
dext(C) é ilimitado e tanto dint(C) como dext(C) são conexos por caminhos2 .
Por outro lado, toda a curva que liga um ponto de dint(C) a um ponto de
dext(C) tem pelo menos um ponto comum com C. A realização de um grafo
(ou multigrafo) numa superfície Sg proporciona a partição dessa superfície nas
componentes conexas de Sg \ C que se designam por regiões, algumas das quais
celulares, no sentido em que são homeomorfas a uma bola aberta de E 2 .
Sendo (V (G), E(G)) uma realização de um grafo em Sg , designa-se por célula ou
face toda a componente conexa do complementar de E(G) em E 2 homeomorfa
a uma bola aberta. Uma realização diz-se celular se todas as regiões criadas
por essa realização são células ou faces. O conjunto das faces criadas por uma
realização celular de G em Sg denota-se por Fg (G). Como regra prática para
a detecção de faces (ou células) de um grafo, G, realizado numa superfície Sg ,
pode adoptar-se a seguinte:
2 Note-se que todo o espaço topológico conexo por caminhos é conexo (o recíproco, porém,
em geral, não é verdadeiro).
Grafos em variedades compactas orientáveis
33
Uma região de G é uma face (ou célula) se e só se a sua fronteira
é contractível a um ponto, ou seja, se e só se é possível "reduzi-la",
continuamente, até a transformar num ponto.
Note-se que de entre as representações de K4 , apresentadas na Figura 3.3,
apenas a primeira é uma representação celular.
Figura 3.3: Três representações de K4 no torus, onde só a primeira é celular.
3.3.1
Menores combinatórios e menores topológicos
Existem algumas operações sobre grafos que é conveniente destacar nesta altura,
a saber:
1. a eliminação de arestas,
2. a eliminação de vértices,
3. a contracção de arestas,
4. e a subdivisão de arestas.
Seja G um grafo, e ∈ E(G) e E 0 = {e1 , . . . , ek } ⊂ E(G).
1. Denota-se por G \ e a operação de eliminação da aresta e, obtendo-se o
grafo tal que V (G \ e) = V (G) e E(G \ e) = E(G) \ {e}. Mais geralmente,
considerando o subconjunto de arestas E 0 , G \ E 0 corresponde ao grafo
obtido de G por eliminação sucessiva (independentemente da ordem) das
arestas e1 , . . . , ek .
2. De um modo semelhante se define a operação de eliminação de vértices,
tendo em conta que, neste caso, ao eliminar-se um vértice (ou conjunto de
vértices) também se eliminam (automaticamente) as arestas que lhe(s) é
(são) incidente(s).
3. A operação de contracção de e em G denotaŋse por G/e e corresponde
ao grafo obtido pela sobreposição dos vértices extremos de e e pela eliminação dos lacetes e arestas repetidas, eventualmente produzidas. Mais
geralmente, dado um subconjunto de arestas, E 0 , G/E 0 corresponde ao
grafo obtido após a contracção sucessiva (independentemente da ordem)
das arestas e1 , . . . , ek .
34
Grafos Planares e Generalizações
4. Designa-se por subdivisão de G a adição de um vértice de grau dois a uma
aresta e. Esta operação também se designa por expansão de G.
Verifica-se que as operações de eliminação e contracção de arestas comutam, i.
e, se E 0 e E” são dois subconjuntos disjuntos de arestas de um grafo G, então
verifica-se a igualdade
(G \ E 0 )/E” = (G/E”) \ E 0 .
3
1
3
4
3
1
4
2
(a)
1
4
2
(c)
(b)
Figura 3.4: Grafos (a) G, (b) G/23 e (c) G \ 14.
Quando um grafo H é obtido de G por sucessivas contracções de arestas
diz-se que G é contractível a H ou que H é uma contracção de G.
Um grafo obtido, a partir de um subgrafo de G, por sucessivas operações de
eliminação e/ou contracção de arestas diz-se um menor de G ou menor combinatório de G. Note-se que, de acordo com esta definição, todo o subgrafo de um
grafo é também um seu menor.
Se H é uma expansão de G e se H é um subgrafo de um grafo Y , então diz-se
que G é um menor topológico de Y . Nestas condições, G é um menor topológico
de um grafo Y se existe um subgrafo de Y que é uma expansão de G.
A figura a seguir exemplifica a subdivisão de várias arestas do grafo G da
Figura 3.4, obtendo-se um grafo H que corresponde a uma expansão de G.
3
5
1
6
7
4
2
Figura 3.5: Expansão do grafo G da Figura 3.1 (a).
Se H é uma expansão de G e um subgrafo de um grafo Y , então diz-se
que G é um menor topológico de Y (e dado que todo o grafo é subgrafo de si
próprio, G é também um menor topológico do grafo H). De um modo equivalente
diz-se que G é um menor topológico de um grafo Y se existe um subgrafo
Grafos em variedades compactas orientáveis
35
de Y que é uma expansão de G. Das definições de menor topológico e menor
combinatório decorre que todo o menor topológico de um grafo Y é também um
menor combinatório de Y . O recíproco, porém, em geral, não é verdadeiro.
Dados dois grafos X e Y , se X é um menor de Y , denota-se esse facto por
X ¹ Y e com facilidade se prova que esta relação, ¹, é uma relação de ordem
parcial no conjunto dos grafos.
Um critério muito utilizado na verificação se um grafo é planar ou não,
consiste na utilização dos seguinte resultado de Kuratowski:
Um grafo é não planar se e só se contém pelo menos uma das configurações não planas básicas, a saber, K5 e/ou K3,3 , como menores
ou como menores topológicos.
Mais adiante, far-se-à a prova da suficiência das condições de Kuratowski. Antes,
porém, vamos introduzir a fórmula de Euler para grafos planares.
3.3.2
Genus de um grafo e fórmula de Euler generalizada
Designa-se por genus de um grafo G e denota-se por gG (não confundir com a
cintura de G que se denota por g(G)) o menor índice da sucessão de superfícies
S0 , S1 , S2 , . . . , em que G é realizável e onde o índice de Sj denota o genus da
superfície Sj . Como consequência, pode concluir-se que para os grafos planares
G, gG = 0.
Theorem 3.3.2. Todo o grafo tem genus.
Demonstração. Seja G um grafo. Se G é planar, então gG = 0. Suponha-se que G não
é planar e, mesmo assim, desenhe-se esse grafo no planar e transfira-se, por projecção
estereográfica, esse desenho para a esfera (superfície S0 ). Seguidamente, adicionem-se
tantas anças tubulares quantas as necessárias para que, fazendo passar as arestas que
intersectam outras arestas através dessas anças tubulares (uma em cada), não existam
arestas cruzadas (i.e. não existam arestas que se intersectem em pontos distintos dos
vértices). Sendo p o número de anças tubulares adicionadas, é claro que p ≤ |E(G)|.
Deformando, continuamente, a superfície obtida é possível produzir um torus com p
buracos, Sp , onde G se realiza. Consequentemente, tendo em conta que Sp pertence à
sequência S0 , S1 , . . . , Sp , Sp+1 , . . . , conclui-se que G tem genus gG ≤ p.
Deve observar-se que uma esfera com p anças tubulares é topologicamente
equivalente (i.e., homeomorfa) a um torus com p buracos. É claro que se um
grafo, G, tem genus gG , então G pode realizar-se em qualquer superfície Sj , com
j ≥ gG . No que se segue, sem perda de generalidade, assumiremos que se G é
um grafo conexo de genus g, então G é realizável em Sg de tal forma que através
de cada buraco de Sg passa pelo menos um anel, formado por vértices e arestas
de G, que não é contractível em Sg . Com efeito, se G tem genus g, então G não
admite qualquer realização em nenhuma das superfícies S0 , S1 , . . . , Sg−1 . Consequentemente, cada buraco de Sg é essencial para a realização de G. Logo, cada
buraco deve ser atravessado por, pelo menos, uma aresta de G, de tal forma que
ligada a outras arestas forme um anel nas condições referidas. Em alternativa,
poder-se-ão obter aneis não contractíveis que contornem buracos. Esta situação,
36
Grafos Planares e Generalizações
porém, é topologicamente equivalente à anterior no sentido em que conduz aos
mesmos resultados, com a metodologia a adoptar na prova do teorema a seguir,
onde se estabelece a generalização da fórmula de Euler, para a um grafo, G,
com realização numa superfície SgG . Note-se que cortar uma superfície, Sg , ao
longo de um anel não contractível que atravessa um buraco ou que contorna um
buraco produz, em ambos os casos, uma superfície topologicamente equivalente
a uma superfície esférica à qual faltam dois círculos.
Theorem 3.3.3 (l’Huilier, 1812/1813). 3 Se G é um grafo conexo com genus
g, então |V (G)| + |Fg (G)| − |E(G)| = 2(1 − g).
Demonstração. Seja G um grafo conexo de genus g. Então G é realizável em Sg
de tal forma que para cada buraco de Sg existe um anel, não contractível, formado
pela concatenação de arestas. Corte-se o torus ao longo de cada um desses g aneis,
dupliquem-se os aneis e, consequentemente, as arestas e vértices que definem as fronteiras das regiões circulares que se formaram e colem-se círculos, de modo a tapar
todos essas regiões. Por deformação contínua da superfície deste modo obtida, pode
construir-se uma superfície esférica, S0 , que lhe é topologicamente equivalente, onde
o grafo conexo produzido, H, se realiza. Consequentemente, aplicando a fórmula de
Euler a H, vem que |V (H)| + |F0 (H)| − |E(H)| = 2. Tendo em conta que os novos
vértices, que agora aparecem em H, V (H) \ V (G), são os que se produziram com a
duplicação de ciclos provocada pelos cortes efectuados em cada um dos g aneis e tendo
em conta que nos ciclos o número de arestas é igual ao número de vértices, conclui-se
que |V (H)| − |V (G)| = |E(H)| − |E(G)|. Por outro lado, dado que as novas faces em H
são as limitadas pelos 2g aneis, conclui-se que |F0 (H)| = |Fg (G)| + 2g. Logo, fazendo
x = |V (H)| − |V (G)| = |E(H)| − |E(G)|, vem que
|V (G)| + |Fg (G)| − |E(G)|
=
(|V (H)| − x) + (|F0 (H)| − 2g) − (|E(H) − x)
=
|V (H)| + |F0 (H)| − |E(H)| − 2g
=
2 − 2g.
A Figura 3.6 ilustra a demonstração do Teorema 3.3.3.
Supondo que G é um grafo conexo tal que |V (G)| ≥ 3, então
3|FgG (G)| ≤ 2|E(G)|
e, por aplicação do Teorema 3.3.3 gG ≥ 61 |E(G)| − 12 (|V (G)| − 2). Consequentemente, tendo em conta que gG é inteiro, conclui-se que
1
1
gG ≥ d |E(G)| − (|V (G)| − 2)e.
6
2
(3.2)
Theorem 3.3.4 (Heawood, 1890). Se n ≥ 3, então gKn ≥ d (n−3)(n−4)
e.
12
3 Embora muitas publicações designem este resultado por fórmula de Heawood ou por
segunda fórmula de Euler, de acordo com (Biggs et al, 1986), ele foi publicado pela primeira
vez por l’Huilier em 1812/1813.
Grafos em variedades compactas orientáveis
37
Figura 3.6: Transformação do duplo torus numa superfície homeomorfa à superfície esférica.
Demonstração. Uma vez que n ≥ 3 e Kn é conexo, tendo em conta a desigualdade
(3.2), vem que
gKn
≥
=
=
1
1
d |E(Kn )| − (|V (Kn )| − 2)
6
2
n(n − 1
n−2
d
−
e
12
2
(n − 3)(n − 4)
d
e.
12
A desigualdade recíproca gKn ≤ d (n−3)(n−4)
e e, consequentemente, a igual12
dade, embora tenha sido conjecturada por Heawood em 1890, apenas foi provada
em 1968 em (Ringel e Youngs, 1968).
Como corolário do Teorema 3.3.4, tendo em conta a desigualdade (3.2) e que se
H é um supergrafo de um grafo conexo G, então gH ≥ gG e ainda que, sendo
n = |V (G)|, Kn é um supergrafo de G, para n ≥ 4, concluem-se as desigualdades
1
1
(n − 3)(n − 4)
d |E(G)| − (n − 2)e ≤ gG ≤ d
e.
6
2
12
Embora nem sempre estes minorante e majorante sejam boas aproximações para
gG , existem grafos para os quais eles coincidem. Por exemplo, sendo G um grafo
conexo de ordem 52 e dimensão 1.321, 1.322, 1.323, 1.324, 1.325 ou 1.326 vem
que
1
(n − 3)(n − 4)
1
= 196.
196 = d |E(G)| − (n − 2)e ≤ gG ≤
6
2
12
38
Grafos Planares e Generalizações
3.3.3
Grafos g-platónicos
Um grafo G diz-se g-platónico se tem genus g, é conexo, regular e na sua realização em Sg , toda a aresta está na fronteira de duas faces e todas as faces têm o
mesmo grau. Nestas condições, os grafos platónicos são grafos 0-platónicos. Denotando por d o grau dos vértices e por f o grau das faces de um grafo G, da definição de grafo g-platónico vem que, se G é g-platónico, então |E(G)| = d|V 2(G)|
e |Fg (G)| = d|V f(G)| . Por outro lado, se g > 0, então d ≥ 3 e f ≥ 3.
Theorem 3.3.5. 4 Sendo d o grau dos vértices e f o grau das faces de um grafo
1-platónico, verifica-se que o par (d, f ) é igual a (3, 6) ou (4, 4) ou (6, 3)
Demonstração. Seja G um grafo 1-platónico, d ≥ 3, f ≥ 3, |E(G)| =
|F1 (G)| = d|Vf(G)| e |V (G)| + |F1 (G)| − |E(G)| = 2(1 − g). Então,
|V (G)| +
d|V (G)|
,
2
d|V (G)|
d|V (G)|
−
= 2(1 − g) = 0 ⇔ |V (G)|(2f + 2d − df ) = 0.
f
2
Uma vez que a ordem de G é positiva, conclui-se que
2f + 2d − df = 0 ⇔ df − 2d − 2f + 4 = 4 ⇔ (f − 2)(d − 2) = 4
e, consequentemente, que apenas os pares (d, f ): (3, 6), (4, 4) e (6, 3) satisfazem esta
igualdade, com d ≥ 3 e f ≥ 3.
Theorem 3.3.6. Se existe um grafo g-platónico, G, tal que g > 1, então
4f (g−1)
|V (G)| = d(f
−2)−2f , onde d denota o grau dos vértices e f o grau das faces.
Demonstração. Seja G um grafo g-platónico, com g > 1, então
|E(G)| =
d|V (G)|
d|V (G)|
, |Fg (G)| =
e |V (G)| + |Fg (G)| − |E(G)| = 2((1 − g),
2
f
pelo que
|V (G)| +
d|V (G)|
d|V (G)|
−
= 2(1 − g)
f
2
⇔
|V (G)|(2f + 2d − df ) = 4f (1 − g)
⇔
|V (G)| =
4f (g − 1)
.
d(f − 2) − 2f
Como corolário imediato deste teorema, conclui-se que, para cada g > 1,
existe um número finito de grafos g-platónicos. Com efeito, sendo g > 1, se não
existem grafos g-platónicos, então o resultado é verdadeiro para g. Supondo que
existe um grafo g-platónico G, cujo grau dos vértices é d e cujo grau das faces
é f , uma vez que g > 1, d ≥ 3 e f ≥ 3,
|V (G)| > 0 ⇒
4f (g − 1)
> 0 ⇔ df − 2d − 2f > 0 ⇔ df − 2d − 2f + 4 > 4,
d(f − 2) − 2f
ou seja, conclui-se que (d − 2)(f − 2) > 4. Como consequência, o estudo reduz-se
aos seguintes casos:
4 Embora só existam grafos 1-platónicos com os pares (d, f ) indicados, o seu número não é
finito.
3.4. EXERCÍCIOS
39
1. Se f = 3, então (d−2)(3−2) > 4 ⇒ d ≥ 7 ⇒ |V (G)| =
12(g−1)
d−6
16(g−1)
2d−8
2. Se f = 4, então (d − 2)(4 − 2) > 4 ⇒ d ≥ 5 ⇒ |V (G)| =
3. Se f = 5, então (d−2)(5−2) > 4 ⇒ d ≥ 4 ⇒ |V (G)| =
≤ 12(g−1).
20(g−1)
3d−10
4. Se f = 6, então (d − 2)(6 − 2) > 4 ⇒ d ≥ 4 ⇒ |V (G)| =
≤ 8(g − 1).
≤ 10(g−1).
24(g−1)
4d−12
≤ 6(g − 1).
5. Se f ≥ 7, então (d − 2)(f − 2) > 4 ⇒ d ≥ 3 ⇒
|V (G)| =
4f (g − 1)
4f (g − 1)
4f (g − 1)
≤
≤
≤ 28(g − 1).
d(f − 2) − 2f
3(f − 2) − 2f
f −6
Logo, todos os grafos g-platónicos (com g > 1) têm ordem não superior a
28(g − 1), pelo que o seu número é finito.
3.4
Exercícios
3.4.1. Determine os duais do grafo e digrafo planar, representados na figura a
seguir.
1
6
3
f
5
a
-c
6
2
b
4
3
s
-
6
d
Figura 3.7: Grafo e digrafo planares.
3.4.2. Prove que se G é um grafo bipartido e planar, então δ(G) ≤ 3.
3.4.3. Considere uma circunferência representada no plano, conjuntamente com
n (n ∈ N) rectas que se intersectam duas a duas num único ponto do
interior do círculo limitado pela circunferência. Supondo que não existem
três rectas que se intersectem no mesmo ponto, determine o número de
regiões definidas pelas rectas e pela circunferência.
3.4.4. Prove que se G é um grafo planar de ordem n ≥ 3 tal que g(G) < ∞,
então
|E(G)| ≤
g(G)(n − 2)
.
g(G) − 2
(3.3)
40
Grafos Planares e Generalizações
3.4.5. Prove que o grafo de Petersen (grafo representado na capa destes apontamentos) não é planar.
3.4.6. Supondo que G é uma triangulação do plano (ou seja, um grafo plano
(onde todas as faces têm grau 3) e sendo ni o número de vértices de grau
i, para i = δ(G), . . . , ∆(G), prove que
∆(G)
X
(6 − i)ni = 12.
i=δ(G)
3.4.7. Prove que um grafo G de ordem n e genus g tem no máximo 3(n − 2 + 2g)
arestas.
• Sugestão: Admita que G está representado celelularmente num gtorus e que acrescenta tantas arestas quantas as necessárias para que
cada face tenha grau 3. Nestas condições aplique a fórmula de Euler
generalizada.
Capítulo 4
Digrafos e Espaços Vectoriais
Associados.
4.1
Espaço dos vértices e espaço dos arcos
A matriz de adjacência de um grafo G tal que V (G) = {v1 , . . . , vn }, é uma
matriz n × n, AG , tal que
½
(AG )ij =
1
0
se vi vj ∈ E(G),
caso contrário.
Por sua vez, a matriz de adjacência de um digrafo DG de ordem n é uma matriz
n × n, ADG , tal que
½
(ADG )ij =
1
0
se (vi , vj ) ∈ A(DG),
nos outros casos.
A matriz de incidência aresta vértice de um grafo de ordem n e dimensão m é
uma matriz n × m, BG , tal que
½
(BG )ij =
1
0
se ej = vi vk , para algum vk ∈ V (G),
caso contrário.
Por sua vez, a matriz de incidência arco vértice de um digrafo de ordem n e
dimensão m é uma matriz n × m, BDG , tal que


(BDG )ij =
1
−1

0
se
se
se
aj = (vi , vk ),
aj = (vk , vi ),
aj = (vp , vq ),
41
para algum vk ∈ V (DG),
para algum vk ∈ V (DG),
e vi ∈
/ {vp , vq }.
42
Digrafos e Espaços Vectoriais Associados
a
e1
b
f
e6
1
e2
e3
c
a1
e
e4
e7
e5
a6
6
a2
a8
2
d
4
- ¾
3 k
a3
?
¾
3
DG
-
G
6
a7
a4
a9
6
a5
5
Figura 4.1: Grafo G e digrafo DG.
Considerando o grafo G e o digrafo DG, representados na Figura 4.1, obtémse:
AG
=
a

a 0
b
1
c
0
d
0
e 0
f 1
e1
a
1
b
1
c
0
d
0
e0
f
0

BG
=
1
1 0
2
1
3
0
4
0
50
6 0

ADG
BDG
=
=
b
1
0
0
1
0
0
e2
0
0
1
0
0
1
c
0
0
0
1
0
1
d
0
1
1
0
1
0
e3
0
0
0
0
1
1
e
0
0
0
1
0
1
e4
0
0
1
1
0
0
f

1
0

1
,
0

1
0
e5
0
0
0
1
1
0
e6
1
0
0
0
0
1
e7

0
1

0
,
1

0
0
2 3 4 5 6

0 0 1 0 0
0 1 1 0 0

0 0 0 0 0
,
0 1 0 0 0

0 1 1 0 1
0 0 1 0 0
a
a2 a3 a4
 1
1 −1 0
0
0
2
1
1
0
0

3
0 −1 0
 0
4
0
−1
1 −1

5 0
0
0
1
6
0
0
0
0
a5 a6 a7
0
1
0
0
0
0
0
0
0
0 −1 −1
1
0
0
−1 0
1
a8 a9

0
0
1
0 

−1 −1 
.
0
0 

0
1 
0
0
Dado um grafo G, designa-se por grafo linha de G e denota-se por L(G) o
grafo que se obtém de G, considerando como vértices as arestas de G e como
Espaço dos vértices e espaço dos arcos
43
relação de adjacência entre os seus vértices a respectiva relação de adjacência
entre arestas. Assim, dois vértices de L(G) são adjacentes se e só se as correspondentes arestas em G são adjacentes (ou seja, têm um vértice comum). Como
consequência desta definição, com facilidade se conclui que dado um grafo arbitrário G, com n vértices,
T
BG
BG = 2In + AL(G) ,
onde In denota a matriz identidade de ordem n e que
T
BG BG
= DG − AG ,
onde DG denota a matriz diagonal DG = diag(µ1 , . . . , µn ), cujos elementos
diagonais µi são os graus dos vértices vi , para i = 1, . . . , n.
Dado um digrafo DG, designa-se por espaço dos vértices de DG o espaço
vectorial sobre o corpo K de todas as funções de V (DG) em K (onde K denota um dos conjuntos R ou C) que se denota por K V (DG) . De modo análogo, designa-se por espaço dos arcos de DG, o espaço vectorial sobre K de
todas as funções de A(DG) em K que se denota por K A(DG) . Se o digrafo
DG é tal que V (DG) = {v1 , v2 , . . . , vm } e A(DG) = {a1 , a2 , . . . , an }, então
V (DG)
dim(K V (DG) ) = m e dim(K A(DG)
são usualPn ) = n. Os elementos x ∈ K
mente escritos na forma x = j=1 αj vj . Neste somatório devemos interpretar
cada vj como sendo uma função de V (DG) em K que é nula em todo os pontos à excepção de vj , para o qual toma o valor 1. Nestas condições, o conjunto
{v1 , v2 , . . . , vm } constitui uma base para K V (DG) e o somatório anterior pode
interpretar-se como uma representação de x nesta base. Analogamente,
um elePm
mento arbitrário y ∈ A(DG) pode representar-se por y = i=1 βi ai . Designamos < v1 , v2 , . . . , vm > e < a1 , a2 , . . . , an > como sendo as bases canónicas,
respectivamente, de K V (DG) e K A(DG)
P.pPodemos munir estes espaços vectoriais
do produto interno usual < u, w >= k=1 uk wk , onde p corresponde a m ou n,
consoante se trate de K V (DG) ou K A(DG) . Considerando a norma induzida por
este produto interno e tendo em conta a definição usual de ortogonalidade, com
facilidade se conclui que as bases anteriormente referidas são ortonormais.
Antes de prosseguirmos convém recordar o conceito de corte (ou cocircuito),
−
→
agora no contexto dos grafos orientados. Dado um grafo orientado conexo G ,
−
→
→
−
designa-se por corte de G e denota-se por ∂(V1 )o subconjunto de arcos de G
−
→
com um único no subconjunto de vértices V1 , onde ∅ 6= V1 6= V ( G ). Neste
+
−
caso, podemos partir ∂(V1 ) nos subconjuntos ∂ (V1 ) e ∂ (V1 ), onde o primeiro
subconjunto corresponde aos arcos com cauda em V1 e cabeça no complementar
de V1 e o segundo conjunto corresponde aos arcos com cauda no complementar
de V1 e cabeça em V1 . Também se diz que ∂ + (V1 ) é o subconjunto dos arcos para
a frente e ∂ − (V1 ) é o subconjunto dos arcos para trás do corte ∂ ( V1 ). Note-se
que dado uma arco (x, y), x é a cauda e y é a cabeça.
Dados dois vértices x e y de um grafo conexo G, designa-se por x-y-corte,
todo o corte ∂(V1 ) de G tal que x ∈ V1 e y ∈ V (G) \ V1 .
44
Digrafos e Espaços Vectoriais Associados
4.2
Variantes do lema de Farkas para grafos
−
→
Theorem 4.2.1 (Lema de Farkas para grafos e multigrafos). Seja G um
→
−
grafo (ou multigrafo) orientado conexo e sejam x, y ∈ V ( G ). Então
1. existe um caminho orientado P entre x e y, ou seja, tal que P − = ∅, ou
2. existe um x-y-corte ∂(V1 ), com x ∈ V1 , tal que ∂ + (V1 ) = ∅,
mas não ambos.
Demonstração. A prova é construtiva. Vamos construindo o subconjunto V1 , formado pelos vértices que podem ser alcançados a partir de x por um caminho orientado,
por intermédio do algoritmo que se segue.
• Algoritmo
1. Iniciar V1 = {x};
2. Enquanto ∂ + (V1 ) 6= ∅ e y ∈
/ V1 faz
(a) escolher a = (s, t) ∈ ∂ + (V1 );
(b) fazer V1 = V1 ∪ {t};
(c) fazer predecessor(t) = s;
fim faz;
• Fim do algoritmo.
−
→
É claro que o algoritmo termina no máximo em |V ( G )| passos. Se termina com
y ∈ V1 , então existe um caminho orientado entre x e y e este caminho pode ser obtido
por intermédio da função predecessor do algoritmo. Se o algoritmo termina com y ∈
/ V1 ,
então ∂(V1 ) = ∂ − (V1 ) é um corte que está de acordo com 2.
Este resultado, constitui o principal teorema da dualidade no contexto dos
grafos e, apesar da sua simplicidade, tem implicações muito interessantes. O
corolário a seguir apresenta una nova versão do lema de Farkas para grafos, na
qual se estabelecem condições de existência, mutuamente exclusivas, de circuitos
e cortes, com determinadas características.
Corolário 4.2.2 (do Lema de Farkas para grafos ou multigrafos). Seja
−
→
−
→
G um digrafo (ou multidigrafo) conexo. Então, para todo o arco a ∈ A( G ), ou
→
−
1. Existe um circuito X ⊆ E( G ) tal que a ∈ X e X − = ∅, ou
→
−
2. Existe um corte Y ⊆ E( G ) tal que a ∈ Y e Y + = ∅,
mas não ambos.
Demonstração. Seja a = (x, y) e aplique-se o Teorema 4.2.1 ao digrafo (ou multidi−
→
grafo) G − a. A existência de um caminho orientado entre x e y no grafo G − a garante
−
→
a existência de um circuito X em G que contém o arco a e para o qual se verifica
X − = ∅. Por sua vez, a não existência de um caminho orientado entre x e y implica
a existência de um x-y-corte Y , tal que a ∈ Y e Y + = ∅.
4.3. SUBESPAÇOS DE CIRCUITOS E DE COCIRCUITOS
4.3
45
Subespaços de circuitos e de cocircuitos
−
→
Seja C um circuito do digrafo G , o qual vamos considerar munido de uma
→
−
certa orientação. Por exemplo, supondo C = (v1 , v2 , . . . , vk , v1 ), dado um arco
a deste circuito, se, para um certo j, a = (vj , vj+1 ) então dizemos que a tem a
−
→
orientação de C se a = (vj+1 , vj ) dizemos que tem a orientação contrária. Este
→
−
−
→
circuito C pode definir-se à custa de um elemento de K A( G , ou seja, de um
vector u, designado por vector de circuito que corresponde à seguinte aplicação
−
→
de A( G ) em {0, 1, −1}:



1,
u(a) =
−1,


0,
−
→
se a ∈ A( C )
−
→
se a ∈ A( C )
−
→
se a ∈
/ A( C ).
−
→
e tem a orientação de C ;
→
−
e tem a orientação contrária à de C ;
Por exemplo o vector uT = (1, 0, 0, 0, −1, 1, −1, −1, 1) ∈ K 9 é o vector do cir→
−
cuito C = (1, 4, 6, 5, 3, 2, 1) do digrafo da Figura 4.1, cuja orientação tem o
sentido dos ponteiros do relógio. Nestas condições, podemos partir o conjunto
−
→
−
→
−
→
A( C ) nos conjuntos C + = {a1 , a6 , a9 } e C − = {a5 , a7 , a8 }, onde o primeiro
corresponde ao conjunto dos arcos positivos e o segundo corresponde ao conjunto
dos arcos negativos.
→
−
O subespaço de K A( G ) gerado pelos vectores de circuitos designa-se por
→
−
subespaço de circuitos e denota-se por Circuitos( G ).
−
→
Por sua vez, um corte ∂(V1 ) de G , pode definir-se à custa de um elemento
→
−
de K A( G ) , ou seja, de um vector v, designado por vector de corte (ou cocircuito)
−
→
que corresponde à seguinte aplicação de A( G ) em {0, 1, −1}:



1,
v(a) =
−1,

 0,
se cauda(a) ∈ V1
se cabeca(a) ∈ V1
se a ∈
/ ∂(V1 ).
e
e
−
→
cabeca(a) ∈ V ( G ) \ V1 ;
−
→
cauda(a) ∈ V ( G ) \ V1 ;
Por exemplo, o vector v T = (1, 1, −1, 1, 1, 0, 0, 0, 0) ∈ K 9 é o vector do corte
∂({2, 3, 5}) do digrafo da Figura 4.1, o qual se pode partir nos subconjuntos
∂ + ({2, 3, 5}) = {a1 , a2 , a4 , a5 } e ∂ − ({2, 3, 5}) = {a3 }.
→
−
O subespaço de K A( G ) gerado pelos vectores de cortes designa-se por subes→
−
paço de cortes ou subespaço de cocircuitos e denota-se por Cortes( G ) ou por
−
→
Circuitos( G ).
Lema 4.3.1. Os espaços de circuitos e cocircuitos de um digrafo (ou multidi→
−
grafo) G são ortogonais.
46
Digrafos e Espaços Vectoriais Associados
Demonstração. Seja X um circuito que se parte em X + e X − e seja Y um cocircuito
−
→
−
→
−
→
que desconexa G nos subdigrafos G 1 e G 2 . Suponha-se que Y + é o subconjunto de
−
→
−
→
arcos de Y com cauda em G 1 e cabeça em G 2 e seja Y − o subconjunto de arcos com
→
−
−
→
−
→
cauda em G 2 e cabeça em G 1 . Sejam x e y os correspondentes vectores de K A( G )
associados, respectivamente, a X e a Y . É fácil ver que o produto interno xT y é o
−
→
−
→
número de vezes que vamos de G 1 para G 2 menos o número de vezes que vamos de
−
→
−
→
G 2 para G 1 , quando se percorre o circuito X, pelo que se obtém xT y = 0. Logo, x
e y são ortogonais, o que completa a prova, uma vez que estes espaços são gerados,
respectivamente, pelos vectores de circuitos e cocircuitos.
Para se provar que os espaços de circuitos e cocircuitos são complementares,
teremos de investigar as respectivas dimensões.
−
→
→
−
Dado um digrafo (ou multidigrafo) G , um subconjunto de arcos A0 ⊆ A( G )
−
→
diz-se um conjunto independente de arcos de G , se não contém circuitos. Um
conjunto independente maximal (no sentido d inclusão) designa-se por base de
−
→
G . Quando um grafo é conexo, uma base coincide com uma árvore abrangente e
quando uma base tem várias componentes coincide com uma floresta abrangente.
→
−
Theorem 4.3.2. Seja G um digrafo (ou multidigrafo) com k componentes.
−
→
−
→
Então, qualquer base de G tem precisamente |V ( G )| − k elementos.
−
→
−
→
Demonstração. Suponha-se que G tem k componentes conexas e sejam G i , para
−
→
i = 1, . . . , k, os correspondentes subdigrafos. Uma vez que em G i uma base é uma
−
→
−
→
árvore abrangente, vem que sendo Ei uma base para G i , |Ei | = |V ( G i )| − 1. Logo,
−
→
dado que qualquer base de G corresponde à união dos arcos que, em cada componente,
−
→
formam
Sk uma árvore abrangente, podemos concluir que uma base E de G é tal que
E = i=1 Ei e, consequentemente,
|E| =
k
X
i=1
k
X
−
→
−
→
−
→
(|V ( G i )| − 1) =
|V ( G i )| − k = |V ( G )| − k.
i=1
→
−
Lema 4.3.3. Seja G um digrafo (ou multidigrado) com k componentes. Então
−
→
−
→
→
−
a dimensão de Circuitos( G ) é pelo menos |A( G )| − |V ( G )| + k e a dimensão
→
−
−
→
de Cocircuitos( G ) é de pelo menos |V ( G )| − k
−
→
Demonstração. Suponha-se que G é conexo, ou seja, k = 1. Seja E uma base para
−
→
−
→
G , pelo que |E| = |V ( G )| − 1.
−
→
• Pela maximalidade de E, qualquer arco de A( G ) \ E adicionado a E produz
−
→
−
→
um circuito. Para um arco arbitrário a ∈ A( G ) \ E seja X(a) o circuito de G
−
→
constituído pelo único caminho do subgrafo (V ( G ), E) que liga os dois vértices
→
−
de a mais o próprio a. Sendo x(a) ∈ K A( G ) o respectivo vector de circuito,
−
→
−
→
−
→
obtém-se um conjunto de |A( G )\E| = |A( G )|−|V ( G )|+1 vectores linearmente
independentes do espaço dos circuitos. Com efeito, note-se que para cada arco
−
→
particular a ∈ A( G ) \ E, x(a) tem a a-ésima componente não nula, enquanto os
−
→
restantes a têm igual a zero. Como consequência, a dimensão de Circuitos( G )
−
→
−
→
é não inferior a |A( G )| − |V ( G )| + 1.
Subespaços de circuitos e de cocircuitos
47
−
→
• Vamos considerar agora os cocircuitos de G . Se a ∈ E, então o subdigrafo
−
→
−
→
−
→
(V ( G ), E \ {a}) é constituído por duas componentes, a saber, G 1 (a) e G 2 (a).
−
→
Para cada a ∈ E seja Y (a) o cocircuito de G constituído pelos arcos que ligam
−
→
−
→
−
→
G 1 (a) a G 2 (a) em G . Todos estes cocircuitos Y (a), com a ∈ E, dão origem a
−
→
um conjunto de |E| = |V ( G ) − 1| vectores de circuitos y(a) linearmente independentes. Com efeito, para cada a ∈ E, y(a) tem a a-ésima componente não
nula, enquanto os vectores representativos dos restantes cocircuitos a têm igual
−
→
−
→
a zero. Logo, a dimensão de Circuitos( G ) é não inferior a |V ( G )| − 1.
−
→
No caso de G ter mais componentes, o resultado obtém-se, facilmente, escolhendo
circuitos e cocircuitos independentes em cada componente.
Theorem 4.3.4. Os subespaços de circuitos e cocircuitos de um digrafo (mul−
→
tidigrafo) G , formam um par de subespaços complementares e ortogonais de
→
−
−
→
→
−
K A( G ) , ou seja, se Circuitos( G ) = L, então Cocircuitos( G ) = L⊥ .
Demonstração. A prova decorre de modo imediato, combinando o Lema 4.3.1 com
o Lema 4.3.3.
− ) denota o subespaço nulo da matriz B→
− , então
Lema 4.3.5. Se Ker(B→
G
G
−
→
− ),
Circuitos( G ) ⊆ Ker(B→
G
Demonstração. Considere-se o caminho P = (v0 , . . . , vk ) e seja A(P ) = {a1 , . . . , ak
→
−
o conjunto dos arcos deste caminho. Seja p ∈ K A( G ) o vector do espaço dos arcos que
representa P , pelo que cada componente de p é igual a +1 se o arco que lhe corresponde
pertence a P e tem o sentido favorável ao caminho (de v0 para vk ), é igual a −1 se
pertence ao caminho mas tem o sentido contrário ao favorável e igual a zero se não
pertence ao caminho. Nestas condições, supondo que ûa = êi − êj denota o vector
− associado ao arco a = (vi , vj ), vem que
coluna de B→
G
−p =
B→
G
X
→
−
a∈A( G )
pa ûa =
k−1
X
(êr − êr+1 ) = ê0 − êk .
r=0
Note-se que dada a sequência de . . . , vr−1 , vr , vr+1 , . . ., existem quatro possibilidades
para par uar + par+1 uar+1 , ou seja, par uar + par+1 uar+1 =
• (+1)(êvr−1 − êvr ) + (+1)(êvr − êvr+1 ) = êvr−1 − êvr+1 , se ar = (vr−1 , vr ) e
ar+1 = (vr , vr+1 );
• (−1)(êvr − êvr−1 ) + (+1)(êvr − êvr+1 ) = êvr−1 − êvr+1 , se ar = (vr , vr−1 ) e
ar+1 = (vr , vr+1 ;
• (+1)(êvr−1 − êvr ) + (−1)(êvr − êvr+1 ) = êvr−1 − êvr+1 , se ar = (vr−1 , vr ) e
ar+1 = (vr+1 , vr );
• (−1)(êvr − êvr−1 ) + (−1)(êvr − êvr+1 ) = êvr−1 − êvr+1 , se ar = (vr , vr−1 ) e
ar+1 = (vr+1 , vr ).
Como consequência, pode concluir-se que se X é um circuito composto pelo caminho
P mais um arco que liga os vértices vk e v0 , e q é o vector do espaço de circuitos que
− q = 0.
o representa, então B→
G
48
Digrafos e Espaços Vectoriais Associados
− ) denota o subespaço imagem da matriz B→
− , então
Lema 4.3.6. Se Im(B→
G
G
−
→
T
Cocircuitos( G ) ⊆ Im(B→
− ),
G
−
→
Demonstração. Seja Y um cocircuito de G e seja V1 o subconjunto de vértices que
→
−
−
→
−
→
define partição de V ( G ) associada ao corte ∂(V1 ) (∅ 6= V1 6= V ( G )). Seja u ∈ K V ( G )
o vector do espaço dos vértices correspondente a V1 , ou seja, a v-ésima componente de
u é igual a 1 se v ∈ V1 e igual a zero no caso contrário. Logo, a a-ésima componente do
− é determinada pelo somatório das componentes
vector do espaço dos arcos y T = uT B→
G
− (que representa o arco a) associadas aos vértices de
da a-ésima coluna da matriz B→
G
V1 . Assim temos quatro casos:
• ya = (+1) + (−1) = 0, se a liga dois vértices de V1 ;
−
→
• ya = 0, se a liga dois vértices de V ( G ) \ V1 ;
−
→
• ya = 1, se a tem cauda em V1 e cabeça em V ( G ) \ V1 ;
−
→
• ya = −1, se a tem cabeça em V1 e cauda em V ( G ) \ V1 .
Assim, vem que y é um vector do espaço dos arcos que determina o subconjunto dos
−
→
−
→
arcos que ligam V1 a V ( G ) \ V1 . Logo, qualquer que seja o cocircuito de G definido
T
pelos arcos ∂(V1 ), existe um vector u (vector característico de V1 ) tal que y = B→
−u é
G
T
o correspondente vector de cocircuito, ou seja, y ∈ Im(B→
− ).
G
−
→
Theorem 4.3.7. Se G é um digrafo (ou multidigrafo) então os espaços de
→
−
T
− ) e Im(B→
circuitos e cocircuitos de G são Ker(B→
− ), respectivamente.
G
G
Demonstração. A prova é consequência imediata do Teorema 4.3.4, combinado com
os Lemas 4.3.5 e 4.3.6.
4.4
Exercícios
4.4.1. Prove que o menor valor próprio da matriz de adjacência de um grafo
linha é não inferior a −2.
4.4.2. Determine os espaços de circuitos e cocircuitos do digrafo representado na
Figura 4.1.
Capítulo 5
Independentes, Cliques e
Colorações
Dado um grafo G, convém, nesta altura, introduzir os conceitos de estável,
estável máximo, número de estabilidade, clique, clique máxima e número de
clique.
• Um subconjunto de vértices S ⊆ V (G) diz-se um estável (ou conjunto independente de vértices) de G se entre quaisquer pares de vértices distintos
de S não existe uma aresta. Um estável de G de cardinalidade máxima
diz-se um estável máximo de G.
• A cardinalidade de um estável máximo de G designa-se por número de
estabilidade de G e denota-se por α(G).
• Um subconjunto de vértices C ⊆ V (G) diz-se uma clique de G se entre
quaisquer pares de vértices distintos de C existe uma aresta. Uma clique
de G de cardinalidade máxima designa-se por clique máxima.
• A cardinalidade de uma clique máxima de G designa-se por número de
clique de G e denota-as por ω(G).
Tendo em conta as definições de estável e clique e de número de estabilidade
e número de clique, conclui-se imediatamente que se um conjunto de vértices T
é um estável para um grafo G então o mesmo conjunto é uma clique para o grafo
complementar Ḡ e, adicionalmente, α(G) = ω(Ḡ). Assim sendo o problema da
determinação de um estável máximo é equivalente ao problema da determinação
de uma clique máxima.
5.1
Formulações analíticas para estáveis máximos
A determinação de um estável máximo de um grafo G de ordem n pode formular-se pelo seguinte problema de optimização, conhecido por formulação baseada
49
50
Independentes, Cliques e Colorações
nas arestas:
n
X
max
xk
(5.1)
k=1
s. a
xi + xj ≤ 1, ∀ij ∈ E(G)
xi , xj ∈ {0, 1}.
(5.2)
(5.3)
Em alternativa, o problema da determinação de um estável máximo pode ter a
formulação analítica, introduzida em [28]:
n
X
max
xk
(5.4)
k=1
s. a
xi xj = 0, ∀ij ∈ E(G)
x2k − xk = 0, k = 1, . . . , n.
(5.5)
(5.6)
Existem ainda outras formulações analíticas para a determinação de um
estável máximo, como é o caso da formulação quadrática de Motzkin-Straus
[23] orientada, na sua versão inicial, para a determinação do número de clique
de um grafo.
Theorem 5.1.1. [23] Considerando o programa quadrático
f (G)
=
1
max{ xT AG x : x ∈ ∆},
2
onde ∆ = {êT x = 1, x ≥ 0}, verifica-se que f (G) = 21 (1 −
(5.7)
1
ω(G) ).
Demonstração. Dado um grafo G de ordem n, sem perda de generalidade, suponha-se que 1, 2, . . . , k são os vértices de uma clique máxima. Seja x∗ ∈ ∆ tal que x∗1 =
x∗2 = . . . = x∗k = k1 e x∗k+1 = x∗k+2 = . . . = x∗n = 0. Assim, vem que
à !
X
1 ∗T
k 1
1
1
x AG x∗ =
x∗i x∗j =
= (1 − ),
2
2 k2
2
k
ij∈E(G)
onde ij = ji, ou seja,
1
1
(1 −
).
(5.8)
2
ω(G)
A prova da desigualdade recíproca de (5.8) vai ser feita por indução sobre n, tendo em
conta que, para n = 1, se obtém k = 1 e f (G) = 0. Supondo que a desigualdade
f (G) ≥
f (G) ≤
1
1
(1 −
)
2
ω(G)
(5.9)
é válida para grafos com menos do que n vértices, com n > 1, fazendo F (x) = 21 xT AG x,
vamos considerar dois casos:
1. Se o maxx∈∆ F (x) é atingido num ponto x∗ da fronteira do simplex ∆, então ∃j
tal que x∗j = 0 e, consequentemente, f (G) = f (G − {j}). Logo, por hipótese de
indução, vem que
f (G) = f (G − {j}) ≤
1
1
1
1
(1 −
) ≤ (1 −
),
2
ω(G − {j})
2
ω(G)
uma vez que ω(G − {j}) ≤ ω(G).
Formulações analíticas para estáveis máximos
51
2. Se o maxx∈∆ F (x) é atingido no interior relativo do simplex ∆, ou seja, num
ponto x∗ cujas componentes são todas positivas, então a função ϕ(x) = (PnF (x)x )2
j=1
j
atinge também o seu máximo no interior do ortante não negativo,1 mais particularmente em x∗ , pelo que ∇ϕ(x∗ ) = 0. Nestas condições, vamos considerar
dois subcasos:
(a) Suponha-se que o grafo G não é completo e considere-se a equação ∇ϕ(x) = 0,
a partir da qual, cada uma das derivadas parciais em ordem a xi , para
i = 1, . . . , n, determina as equações
n
n
X
X
∂ϕ(x)
∂F (x)
∂F (x)
2F (x)
=0⇔(
xj )2
− 2(
xj )F (x) = 0 ⇔
= Pn
.
∂xi
∂x
∂x
i
i
j=1 xj
j=1
j=1
(x)
∗
∗ = 2F (x ), para i = 1, . . . , n.
Consequentemente, vem que ∂F
|
∂xi x=x
Suponha-se, sem perda de generalidade, que a aresta 12 não pertence a
E(G). Logo, qualquer que seja a constante c,
F (x∗1 −c, x∗2 +c, x∗3 , . . . , x∗n ) = F (x∗ )−c(
∂F (x)
∂F (x)
|x=x∗ −
|x=x∗ ) = F (x∗ ).
∂x1
∂x2
Em particular, para c = x∗1 , F (0, x∗1 + x∗2 , x∗3 , . . . , x∗n ) = F (x∗ ), ou seja,
o máximo é também atingido na fronteira, pelo que, tal como se provou
anteriormente, a desigualdade (5.9) verifica-se.
(b) Suponha-se que o grafo G é completo. Então
F (x∗ )
=
=
≤
=
n
n
1 X ∗ 2 X ∗2
[(
xj ) −
xj ]
2 j=1
j=1
1
(1 − ||x∗ ||2 )
2
1
(1 −
min
||x||2 )
|x1 |+···+|xn |=n
2
1
1
(1 − ).
2
n
Tendo em conta a formulação quadrática de Motzkin-Straus, deve observar1 Uma
vez que ∀x ∈ ∆ ϕ(x) = F (x), podemos concluir que maxx∈∆ F (x) ≤ maxx≥0 ϕ(x).
Por outro lado, dado que ∀λ > 0
maxx≥0 ϕ(x) =
ϕ(x0 ),
então existe
λ0
ϕ(λx) =
> 0 tal que
F (λx)
Pn
2
j=1 λxj )
λ0 x 0 ∈ ∆ e
(
=
F (λ0 x0 ) = ϕ(λ0 x0 ) = ϕ(x0 ) ≥ max F (x).
x∈∆
Consequentemente, podemos considerar, x∗ = λ0 x0 .
λ2 F (x)
P
2
λ2 ( n
j=1 xj )
= ϕ(x), se
52
Independentes, Cliques e Colorações
-se que
1
1
(1 −
) =
2
ω(G)
1
max xT AG x
x∈∆ 2
X
= max
xi xj
x∈∆
= max
x∈∆
ij∈E(G)
X
X
xi xj −
ij∈E(Kn )
xr xs
rs∈E(Ḡ)
n
1 X
= max [(
xj )2 − ||x||2 ] −
x∈∆ 2
j=1
X
xr xs
rs∈E(Ḡ)
1
= max (1 − ||x||2 − xT AḠ x)
x∈∆ 2
1
1
=
+ max − xT (I + AḠ )x
2 x∈∆ 2
1
1
=
− min xT (I + AḠ )x.
2 x∈∆ 2
Logo, vem que
1
1
min xT (AḠ + I)x =
x∈∆ 2
2ω(G)
⇔
min xT (AḠ + I)x =
x∈∆
1
α(Ḡ)
Nesta condições, podemos concluir que a formulação quadrática de Motzkin-Straus para a determinação do número de clique do complementar Ḡ de um
grafo G é equivalente à formulação quadrática para a determinação do número
de estabilidade de G, ou seja,
1
= min xT (AG + I)x,
α(G) x∈∆
(5.10)
onde ∆ = {x : êT x = 1, x ≥ 0}.
No que segue, vamos abordar uma família de formulações quadráticas, relativamente à qual, como veremos mais tarde, a formulação (5.10) é um caso
particular. Assim, considere-se o programa quadrático
1
(PG (τ )) υG (τ ) = max{2êT x − xT ( AG + In )x : x ≥ 0},
τ
com τ > 0, onde ê é o vector de componentes unitárias e In a matriz identidade
de ordem n. Então podemos concluir o seguinte resultado.
Theorem 5.1.2. ∀τ > 0, se x∗ (τ ) é uma solução óptima para (PG (τ )) então
∀i ∈ V (G) [x∗ (τ )]i = max{0, 1 −
aiG x∗
},
τ
onde [x∗ (τ )]i é a i-ésima componente de x∗ (τ ) e aiG é a i-ésima linha da matriz
AG .
Formulações analíticas para estáveis máximos
53
Demonstração. Seja x∗ uma solução óptima para (PG (τ )) e seja ē, x̄∗ e x̄ os subvectores de ê, x∗ e x, respectivamente, sem a i-ésima componente. Seja ainda
1
fG−{i} (x̄) = 2ēT x̄ − x̄T ( AG−{i} + In−1 )x̄.
τ
Primeiramente, deve observar-se que
υG (τ )
=
max fG−{i} (x̄) + 2xi − x2i − 2xi
x̄,xi ≥0
=
∗
fG−{i} (x̄∗ ) + 2x∗i − x∗2
i − 2xi
=
fG−{i} (x̄∗ ) + ψ(x∗i )
=
fG−{i} (x̄∗ ) + max ψ(xi ),
onde ψ(xi ) = 2xi − x2i − 2xi
aiG x
τ
aiG x∗
τ
xi ≥0
aiG x∗
.
τ
Dado que
d
ψ(xi )
dxi
= 2(1 − xi −
aiG x∗
)
τ
e
d2
ψ(xi )
dx2
i
=
−2, podemos concluir que ψ(xi ) é estritamente côncava e atinge o seu máximo num
ponto crítico, ou seja, na solução da equação
d
ai x∗
ψ(xi ) = 0 ⇔ xi = 1 − G .
dxi
τ
Logo, uma vez que ψ(x∗i ) = maxxi ≥0 ψ(xi ), vem que x∗i = max{0, 1 −
aiG x∗
}.
τ
Como consequência imediata deste teorema, temos os seguintes resultados.
1. Se x∗ (τ ) é uma solução óptima para (PG (τ )) então
∀i ∈ V (G) 0 ≤ [x∗ (τ )]i ≤ 1.
2. Por outro lado, uma vez que ∀τ > 0
0 ≤ x ≤ ê ⇒ 2êT x − xT (
AG
+ In )x ≤ 2êT x − ||x||2 ≤ n
τ
e dado que 2êT êj − êTj ( AτG + In )êj = 1 (onde êj denota o j-ésimo vector
da base canónica de Rn ), conclui-se que 1 ≤ υG (τ ) ≤ n.
3. Adicionalmente, o majorante e o minorante obtidos em 2 são os mais
favoráveis para υG (τ ), uma vez que υG (τ ) = 1 se G é um grafo completo
e υG (τ ) = n se G não tem arestas.
O próximo teorema introduz as principais propriedades de υG (τ ) e (PG (τ )).
Antes, porém, convém lembrar que uma solução óptima x∗ de (PG (τ )) se designa
por espúria, quando υG (τ ) = α(G) mas x∗ não define o vector característico de
um estável máximo.
Theorem 5.1.3 ([10]). Dado um grafo G, a função υG :]0, +∞[7→ [1, n] tem
as seguintes propriedades:
5.1.3.1. ∀τ > 0 α(G) ≤ υG (τ ).
54
Independentes, Cliques e Colorações
5.1.3.2. 0 < τ1 < τ2 ⇒ υG (τ1 ) ≤ υG (τ2 ).
5.1.3.3. ∀τ ≥ −λmin (AG ) (PG (τ )) é um programa convexo.
5.1.3.4. Supondo τ ∗ > 0, as seguintes afirmações são equivalentes.
a) ∃τ̄ ∈]0, τ ∗ [ tal que υG (τ̄ ) = υG (τ ∗ );
b) υG (τ ∗ ) = α(G) e ∀τ ∈]0, τ ∗ [ (PG (τ )) não tem soluções espúrias;
c) ∀τ ∈]0, τ ∗ ] υG (τ ) = α(G).
5.1.3.5. ∀U ⊂ V (G) ∀τ > 0 υG−U (τ ) ≤ υG (τ ).
Demonstração.
5.1.3.1. Para qualquer vector característico, x̄, de um estável máximo de G, x̄T AG x̄ = 0.
Logo, se x̄, é o vector característico de um estável máximo, então
∀τ > 0 2êT x̄ − x̄T (
AG
+ In )x̄ = 2êT x̄ − ||x̄||2 = α(G) ≤ υG (τ ).
τ
5.1.3.2. Supondo 0 < τ1 < τ2 , então ∀x ≥ 0
xT AG x
τ2
≤
m
A
G
2êT x − xT (
+ In )x ≤
τ1
xT AG x
τ1
2êT x − x(
AG
+ In )x.
τ2
Consequentemente,
υG (τ1 ) = max 2êT x − xT (
x≥0
AG
AG
+ In )x ≤ max 2êT x − xT (
+ In )x = υG (τ2 ).
x≥0
τ1
τ2
5.1.3.3. ∀τ ≥ −λmin (AG ), o menor valor próprio de AτG + In não é menor do que zero e,
consequentemente, a matriz Hessiana da função objectivo de (PG (τ )) é definida
seminegativa.
5.1.3.4.
– Vamos provar a implicação a) ⇒ b).
Assumindo que τ̄ ∈]0, τ ∗ [ e x(τ̄ ) é uma solução óptima de (PG (τ̄ )), então
υG (τ̄ ) =
≤
≤
AG
+ In )x(τ̄ )
τ̄
AG
2êT x(τ̄ ) − x(τ̄ )T ( ∗ + In )x(τ̄ )
τ
υG (τ ∗ ).
2êT x(τ̄ ) − x(τ̄ )T (
Logo, υG (τ̄ ) = υG (τ ∗ ) implica que x(τ̄ ) é uma solução óptima para (PG (τ ∗ ))
e também que
x(τ̄ )T AG x(τ̄ )
x(τ̄ )T AG x(τ̄ )
=
.
τ̄
τ∗
Uma vez que τ̄ < τ ∗ , a partir da igualdade anterior, podemos concluir que
x(τ̄ )T AG x(τ̄ ) = 0.
Formulações analíticas para estáveis máximos
55
Isto equivale a afirmar que o suporte de x(τ̄ ) (ou seja, o subconjunto de
índices {j : x(τ̄ )j > 0}) define o vector característico de um estável de G
e, então (dado que x(τ̄ ) é uma solução óptima pata (PG (τ̄ ))) é o vector
característico de um estável máximo de G.
Consequentemente, υG (τ ∗ ) = α(G) e ∀τ ∈]0, τ ∗ [ (PG (τ )) não tem soluções
espúrias.
– Vamos agora provar a implicação b) ⇒ c)
Assumindo que υG (τ ∗ ) = α(G), de acordo com 5.1.3.2,
∀τ ∈]0, τ ∗ ]
α(G) ≤ υG (τ ) ≤ υG (τ ∗ ) = α(G).
– A implicação c) ⇒ a) é óbvia.
5.1.3.5. Seja U ⊂ V (G) e x̄∗ uma solução óptima para (PG−U (τ )), com τ > 0. Seja
x∗ ∈ Rn tal que
½ ∗
x̄i , if i 6∈ U
x∗i =
0,
caso contrário.
Então υG−U (τ ) = 2êT x∗ − x∗T ( AτG + In )x∗ ≤ υG (τ ).
Sendo τ ∗ = maxυG (τ )=α(G) τ (e, consequentemente, como veremos mais
tarde, τ ∗ ≥ 1), podemos concluir que ∀τ ∈]0, τ ∗ [ (PG (τ )) não tem soluções
óptimas espúrias e ∀τ ≤ τ ∗ υG (τ ) = α(G).
A Figura 5.1 ilustra o gráfico da função υG (τ ), para o grafo G representado na
Figura 5.2.
u G (t)
3.7
3 .7
3.6
3 .6
3.5
3 .5
3.4
3 .4
3.3
3 .3
3.2
3 .2
3.1
3 .1
3
3
t
2.9
2 .9
1
1
1.5
1 .5
2
2
2.5
2 .5
3
3
3.5
3 .5
Figura 5.1: Gráfico de υG (τ ), onde G é o grafo representado na Figura 5.2.
O próximo teorema permite concluir que o programa quadrático de Motzkin-Straus [23], na sua versão (5.10), é um caso particular da família de programas
quadráticos (PG (τ )).
56
Independentes, Cliques e Colorações
4
6
5
3
1
2
Figura 5.2: Grafo G, com λmin (AG ) = −1.7566, para o qual υG (2) = 3 = α(G)
e S = {1, 3, 6} é um único estável máximo.
Theorem 5.1.4 ([10]). Considere-se o programa quadrático
νG (τ ) = min{z T (
(QG (τ ))
AG
+ In )z : êT z = 1, z ≥ 0},
τ
com τ > 0, e sejam x∗ e z ∗ soluções óptimas para PG (τ ) e QG (τ ), respectiva∗
∗
mente. Então νGz(τ ) e υGx(τ ) são soluções óptimas para PG (τ ) e QG (τ ), respectivamente, e υG (τ ) = νG1(τ ) .
Demonstração. Da optimalidade de x∗ para PG (τ ), pelas condições de KarushKhun-Tucker [26], ∃y ∗ ≥ 0 tal que
AG x ∗ =
∗T
x
Então x
∗T
( AτG
∗
T
y
∗
=
τ (ê − x∗ ) + y ∗ ,
(5.11)
0,
(5.12)
∗
+ In )x = ê x = υG (τ ) e, consequentemente,
1
x∗T AG
x∗
=
(
+ In )
.
υG (τ )
υG (τ ) τ
υG (τ )
Por outro lado, tendo em atenção que
de z ∗ para (QG (τ )), vem que
z ∗T (
x∗
υG (τ )
é admissível para (QG (τ )), da optimalidade
AG
x∗T AG
x∗
+ In )z ∗ ≤
(
+ In )
.
τ
υG (τ ) τ
υG (τ )
Logo,
AG
AG
+ In )υG (τ )z ∗ ≤ x∗T (
+ In )x∗
τ
τ
m
AG
T ∗
∗T AG
∗
T
υG (τ ) = 2ê x − x (
+ In )x ≤ 2ê (υG (τ )z ∗ ) − (υG (τ )z ∗ )T (
+ In )(υG (τ )z ∗ ),
τ
τ
uma vez que êT x∗ = υG (τ ) e êT z ∗ = 1. Consequentemente, υG (τ )z ∗ é uma solução
óptima para (PG (τ )) e υG (τ ) = (υG (τ ))2 z ∗T ( AτG +In )z ∗ ⇔ υG (τ ) = νG1(τ ) . A partir da
υG (τ )z ∗T (
Formulações analíticas para estáveis máximos
57
∗
última igualdade, também concluímos que νGz(τ ) é uma solução óptima para (PG (τ )).
Por outro lado, a optimalidade de x∗ para (PG (τ )) implica
υG (τ ) = 2êT x∗ − x∗T (
AG
AG
+ In )x∗ ≥ 2êT (υG (τ )z ∗ ) − (υG (τ )z ∗ )T (
+ In )(υG (τ )z ∗ ).
τ
τ
Uma vez que êT x∗ = êT (υG (τ )z ∗ ), vem que
(υG (τ )z ∗ )T (
AG
AG
+ In )(υG (τ )z ∗ ) ≥ x∗T (
+ In )x∗ = υG (τ )
τ
τ
m
νG (τ ) = z
∗T
AG
x∗T AG
x∗
1
(
+ In )z ∗ ≥
(
+ In )
=
.
τ
υG (τ ) τ
υG
υG (τ )
Tendo em conta a igualdade (5.10), sabe-se que
1
= α(G).
T
G + In )z : ê z = 1, z ≥ 0}
min{z T (A
(5.13)
Logo, combinando este resultado com o Teorema 5.1.4, obtém-se a igualdade
υG (1) =
1
= α(G).
νG (1)
Se x∗ é uma solução óptima para (PG (τ )), com τ ≥ 1, então
2êT x∗ − x∗T (AG + In )x∗ ≤ υG (1) = α(G) ≤ υG (τ )
e, uma vez que υG (τ ) = êT x∗ e x∗T AG x∗ = τ (υG (τ ) − ||x||2 ), obtém-se também
um minorante para o número de estabilidade de G, ou seja,
υG (τ ) −
τ − 1 ∗T
x AG x∗ ≤ α(G) ≤ υG (τ ).
τ
O majorante υG (τ ) para o número de estabilidade de G, com τ = −λmin (AG ),
foi introduzido em [22], com a seguinte condição necessária e suficiente para a
obtenção da igualdade.
• Supondo que G tem pelo menos uma aresta, α(G) = υG (−λmin (AG )) se
e somente se para um estável máximo S de G (e, consequentemente, para
todos),
−λmin (AG ) ≤ min{|NG (i) ∩ S| : i 6∈ S}.
(5.14)
Podemos, no entanto, considerar a seguinte generalização, a qual se pode
deduzir aplicando as condições de Karush-Khun-Tucker, com uma prova semelhante à de (5.14) apresentada em [22].
Theorem 5.1.5. Seja G uma grafo com pelo menos uma aresta. Então ∀τ ≥
−λmin (AG ), α(G) = υG (τ ) se e somente se para um estável S ⊂ G,
τ ≤ min |NG (i) ∩ S|.
i∈S
/
(5.15)
58
Independentes, Cliques e Colorações
Demonstração. Seja τ ≥ −λmin (AG ), pelo que (PG (τ )) é um programa convexo.
• Suponha-se que α(G) = υG (τ ) pelo que, sendo S ⊂ V (G) um estável máximo de
G, o seu vector característico, x∗ = x(S), é uma solução óptima para (PG (τ )).
Logo, por aplicação das condições de Karush-Khun-Tucker (5.11)-(5.12), existe
y ∗ ≥ 0 tal que x∗T y ∗ = 0 e AG x∗ = τ (ê − x∗ ) + y ∗ . Nestas condições, uma vez
que ∀i ∈ V (G) (AG x∗ )i = |NG (i) ∩ S|, vem que
½
|NG (i) ∩ S| = 0,
se i ∈ S,
|NG (i) ∩ S| = τ (1 − x∗i ) + yi∗ ⇔
|NG (i) ∩ S| = τ + yi∗ , se i ∈
/ S,
donde se conclui que τ ≤ |NG (i) ∩ S| ∀i ∈
/ S e, consequentemente, que
τ ≤ min |NG (i) ∩ S|.
i∈S
/
• Reciprocamente, suponha-se que existe um estável S ⊂ V (G), para o qual se
∗
verifica a desigualdade τ ≤ mini∈S
/ |NG (i) ∩ S|. Então, sendo x = x(S) o vector
característico de S, vem que (AG x∗ )i = |NG (i) ∩ S| ∀i ∈ V (G) e, consequentemente,
AG x∗ = τ (ê − x∗ ) + y ∗ ,
com yi∗ = 0 se i ∈ S e yi∗ = |NG (i) ∩ S| − τ se i ∈
/ S. Nestas condições, x∗
∗
e y verificam as condições de Karush-Khun-Tucker (5.11)-(5.12), pelo que x∗
é uma solução óptima para (PG (τ )). Logo, uma vez que α(G) ≤ υG (τ ) = |S|,
conclui-se que S é um estável máximo para G e que α(G) = υG (τ ).
Existe uma infinidade de grafos G para os quais o programa quadrático de
Motzkin-Straus (QG (1)) tem soluções óptimas espúrias (conforme se prova em
[25]), e então o mesmo acontece para (PG (1)). Consequentemente, de acordo
com o Teorema 5.1.2, para tais grafos não existe τ > 1 tal que υG (τ ) = α(G).
Dado um grafo G e τ ∈]1, −λmin (AG )[, permanece por saber se a condição
(5.15), quando verificada para todo o estável máximo de G, é suficiente para
se obter a igualdade υG (τ ) = α(G). O grafo G representado na Figura 5.3,
para o qual λmin (AG ) = −2.1774, mostra que a existência de um estável
máximo S tal que τ ≤ min{|NG (j) ∩ S| : j 6∈ S}, com τ ∈]1, −λmin (AG )[,
não é suficiente para a obtenção da igualdade υG (τ ) = α(G). Note-se que
S = {1, 4} é um estável máximo para o grafo G representado na Figura 5.3,
tal que 2 ≤ min{|NG (i) ∩ S| : i 6∈ S} e α(G) = 2 < 73 ≤ υG (2) (deve notar-se,
porém, que existem outros estáveis máximos S 0 = {2, 3} e S 00 = {5, 2}, para os
quais a desigualdade (5.15), com τ = 2, não se verifica).
Tendo em atenção o Teorema 5.1.3, podemos concluir que se S é um estável
máximo de G, λmin (AG ) não é inteiro e |NG (v) ∩ S| ≥ −λmin (AG ) ∀v 6∈ S
(como é o caso do grafo representado na Figura 5.2), então S é o único estável
máximo de G. Com efeito, em tal caso, para τ ≥ −λmin (AG ), o programa
quadrático (PG (τ )) é convexo. Consequentemente, a combinação convexa de
soluções óptimas de (PG (τ )) são também soluções óptimas. Por outro lado,
Formulações analíticas para estáveis máximos
59
2
3
1
4
5
Figura 5.3: Grafo, G, com λmin (AG ) = −2.1774, onde existe um estável máximo,
S = {1, 4}, para o qual a condição (5.15) se verifica para τ = 2, mas υG (2) >
α(G).
fazendo τ1 = −λmin (AG ) e τ2 = d−λmin (AG )e (onde dδe denota o menor inteiro
não inferior a δ), uma vez que
τ1 ≤ min{|NG (v) ∩ S| : v 6∈ S} ⇒ τ2 ≤ min{|NG (v) ∩ S| : v 6∈ S},
por(5.15), obtém-se υG (τ1 ) = α(G) = υG (τ2 ). Logo, assumindo que existem dois
estáveis máximos em G, os correspondentes vectores característicos são soluções
óptimas tanto para (PG (τ1 )) como para (PG (τ2 )), e uma qualquer combinação
convexa destas duas soluções é também solução óptima para ambos os programas. Consequentemente, existem soluções óptimas espúrias para (PG (τ1 )), o que
entra em contradição com o Teorema 5.1.3.
Tendo em conta que um emparelhamento é um conjunto de arestas sem vértices comuns, podemos concluir que a um emparelhamento de G corresponde
um conjunto independente de vértices de L(G). Adicionalmente, dado que um
grafo G para o qual L(G) não é completo, tal como se prova em [9], tem um
emparelhamento perfeito (ou seja, um emparelhamento que contém todos os
vértices do grafo) se e só se α(L(G)) = υL(G) (2), conclui-se ainda que se uma
árvore, com mais do que uma aresta, tem um emparelhamento perfeito, então
esse emparelhamento perfeito é único. Note-se que o menor valor próprio de
uma árvore é superior a −2.
Quando τ ∈]1, −λmin (AG )[, podemos estabelecer a seguinte condição necessária para a igualdade υG (τ ) = α(G).
Theorem 5.1.6. Dado um grafo G, se υG (τ ) = α(G), então para qualquer
estável máximo S
|NG (v) ∩ S| ≥ τ
∀v ∈ V (G) \ S.
Demonstração. Se υG (τ ) = α(G), então o vector característico de qualquer estável
máximo de G é uma solução óptima para (PG (τ )). Logo, sendo x̄ o vector característico
60
Independentes, Cliques e Colorações
de um estável máximo S de G, pelas condições de Karush-Khun-Tucker [26], ∃ȳ ≥ 0
tal que ȳ T x̄ = 0, e AG x̄ = τ (ê − x̄) + ȳ. Consequentemente, para cada vértice v 6∈ S,
obtém-se a seguinte igualdade
|NG (v) ∩ S| = τ (1 − x̄v ) + ȳv ⇔ |NG (v) ∩ S| = τ + ȳv ,
e então |NG (v) ∩ S| ≥ τ.
Apesar da condição (5.15) não ser suficiente para a obtenção da igualdade
υG (τ ) = α(G), quando τ ∈]1, −λmin (AG )[, assumindo que certas componentes
dos vectores complementares de uma solução optima de (PG (τ )) têm valor nulo,
esta igualdade verifica-se.
Theorem 5.1.7. Seja x∗ uma solução óptima para (PG (τ )) e y ∗ o correspondente vector complementer. Se existe um estável máximo S de G, tal que yi∗ = 0
∀i ∈ S e τ ≤ min{|NG (i) ∩ S| : i 6∈ S} então υG (τ ) = α(G).
Demonstração. De acordo com a hipótese AG x∗ = τ (ê − x∗ ) + y ∗ . Então, sendo x̄
o vector característico de S, vem que
X ∗
X ∗
x̄T AG x∗ = τ (α(G) −
xj ) +
yj
j∈S
j∈S
m
X
x∗j +
j∈S
Se
P
j∈S
X |NG (j) ∩ S| ∗
xj
τ
=
j6∈S
yj∗ = 0 e
|NG (j)∩S|
τ
υG (τ ) ≤
α(G) +
1X ∗
yj .
τ j∈S
≥ 1 ∀j 6∈ S, então
X
j∈S
x∗j +
X |NG (j) ∩ S| ∗
xj = α(G) ≤ υ(G).
τ
j6∈S
Note-se que esta prova também implica que se ∃j 6∈ S tal que |NG (j)∩S| > τ,
então x∗j = 0.
Combinando os Teoremas 5.1.7 e 5.1.6, segue-se que dado um grafo arbitrário
G, ∀τ > 0, se existe uma solução óptima para (PG (τ )) que é um ponto crítico
para a respectiva função objectivo, então
α(G) = υG (τ ) se e somente se τ ≤ min{|NG (i) ∩ S| : i 6∈ S}.
5.2
Grafos com número de estabilidade quadrático convexo
Vamos passar a designar os grafos G para os quais o número de estabilidade
coincide com o valor óptimo do programa quadrático convexo (PG (τ )), com
τ = −λmin (AG ), por grafos com número de estabilidade quadrático convexo e
denotar o conjunto destes grafos por Q.
Grafos com número de estabilidade quadrático convexo
61
Antes de prosseguirmos, convém lembrar que dado um grafo arbitrário G,
se U ⊆ V (G), então λmin (AG ) ≤ λmin (AG−u ). Como consequência, tendo em
conta as propriedades de υG (τ ), podemos concluir que
∀U ⊆ V (G)
υG−U (−λmin (AG−U )) ≤ υG (−λmin (AG )),
(5.16)
uma vez que υG−U (−λmin (AG−U )) ≤ υG−U (−λmin (AG )) ≤ υG (−λmin (AG )).
Theorem 5.2.1 ([9]). Se G ∈ Q e U ⊆ V (G) é tal que α(G) = α(G − U ),
então G − U ∈ Q.
Demonstração. Dado que U ⊆ V (G) é tal que α(G) = α(G − U ), das desigualdades
α(G − U ) ≤ υG−U (−λmin (AG−U )) ≤ υG (−λmin (AG )), vem que
α(G) = υG (−λmin (AG )) ⇒ α(G − U ) = υG−U (−λmin (AG−U )).
Os próximos resultados permitem desenvolver uma estratégia algorítmica
para o reconhecimento de grafos com número de estabilidade quadrático convexo.
Theorem 5.2.2 ([9]). Dado um grafo arbitrário G, se existe v ∈ V (G) tal que
υG (−λmin (AG )) 6= max{υG−{v} (−λmin (AG−{v} )), υG−NG (v) (−λmin (AG−NG (v) ))}
então G ∈
/ Q.
Demonstração. Tendo em conta a desigualdade (5.16), a hipótese do teorema implica
que se tenha
υG (−λmin (AG )) > max{υG−{v} (−λmin (AG−{v} )), υG−NG (v) (−λmin (AG−NG (v) ))}.
Seja S ⊆ V (G) um estável máximo de G.
• Se v ∈
/ S, então
α(G) = α(G − {v}) ≤ υG−{v} (−λmin (AG−{v} ) < υG (−λmin (AG )).
• Se v ∈ S, então
α(G) = α(G − NG (v)) ≤ υG−NG (v) (−λmin (AG−NG (v) )) < υG (−λmin (AG )).
Como consequência imediata deste teorema, se G ∈ Q, então ∀v ∈ V (G),
max{υG−{v} (−λmin (AG−{v} ), υG−NG (v) (−λmin (AG−NG (v) ).
Theorem 5.2.3 ([9]). Suponha-se que para o grafo G e para um vértice v ∈
V (G) se verifica a igualdade
υG (−λmin (AG ) = max{υG−{v} (−λmin (AG−{v} )), υG−NG (v) (−λmin (AG−NG (v) ))}
e que υG−{v} (−λmin (AG−{v} )) 6= υG−NG (v) (−λmin (AG−NG (v) )).
62
Independentes, Cliques e Colorações
1. Se υG (−λmin (AG ) = υG−{v} (−λmin (AG−{v} ) então
G ∈ Q ⇔ G − {v} ∈ Q.
2. Se υG (−λmin (AG ) = υG−NG (v) (−λmin (AG−NG (v) ) então
G ∈ Q ⇔ G − NG (v) ∈ Q.
Demonstração.
1. Supondo G ∈ Q, dado que
α(G) = υG (−λmin (AG ) > υG−NG (v) (−λmin (AG−NG (v) ) ≥ α(G − NG (v)),
podemos concluir que α(G) > α(G − NG (v)). Logo, se S é um estável máximo
de G, então NG (v) ∩ S 6= ∅ e, consequentemente, v ∈
/ S. Nestas condições,
α(G−{v}) = α(G) = υG (−λmin (AG )) = υG−{v} (−λmin (AG−{v} )) ⇒ G−{v} ∈ Q.
Reciprocamente, supondo G − {v} ∈ Q e tendo em conta que
α(G − {v}) ≤ α(G) ≤ υG (−λmin (AG )) = υG−{v} (−λmin (AG−{v} )),
obtém-se G ∈ Q.
2. Supondo G ∈ Q, tendo em conta a hipótese
α(G) = υG (−λmin (AG )) > υG−{v} (−λmin (AG−{v} )) ≥ α(G − {v}),
vem que α(G − {v}) < α(G). Como consequência, se S é um estável máximo,
então v ∈ S, NG (v) ∩ S = ∅ e α(G − NG (v)) = α(G). Logo,
α(G) = α(G − NG (v)) ≤ υG−NG (v) (−λmin (AG−NG (v) )) ≤ υG (−λmin (AG ))
e a hipótese implica α(G − NG (v)) = υG−NG (v) (−λmin (AG−NG (v) )).
Reciprocamente, supondo G − NG (v) ∈ Q, de acordo com a hipótese, sabemos
que α(G − NG (v)) ≤ α(G) ≤ υG (−λmin (AG )) = υG−NG (v) (−λmin (AG−NG (v) )),
donde α(G) = υG (−λmin (AG )).
Finalmente, o próximo teorema permite desenvolver uma estratégia de ramificação, na presença de grafos que ∀v ∈ V (G) verificam as igualdades
υG (−λmin (AG )) = υG−{v} (−λmin (AG−{v} )) = υG−NG (v) (−λmin (AG−NG (v) ))
que são os únicos para os quais não se pode aplicar nenhum dos resultados
anteriores.
Theorem 5.2.4 ([9]). Se ∃v ∈ V (G) tal que
υG (−λmin (AG )) = υG−{v} (−λmin (AG−{v} )) = υG−NG (v) (−λmin (AG−NG (v) ),
então

 G − NG (v) ∈ Q
ou
G∈Q⇔

G − {v} ∈ Q.
5.3. EMPARELHAMENTOS E COBERTURAS DE ARESTAS POR VÉRTICES63
Demonstração. Suponha-se que G ∈ Q e que S é um estável máximo de G. Se v ∈ S
então α(G) = α(G − NG (v)) ≤ υG−NG (v) (−λmin (AG−NG (v) )) = υG (−λmin (AG )), o
que implica α(G − {v}) = υG−{v} (−λmin (AG−{v} )).
Reciprocamente, suponha-se G − U ∈ Q, com U = {v} ou U = NG (v). Então, uma
vez que
α(G − U ) ≤ α(G) ≤ υG (−λmin (AG )) ≤ υG−U (−λmin (AG−U )),
podemos concluir que α(G) = υG (−λmin (AG )).
Existe uma grande variedade de grafos com número de estabilidade quadrático convexo. Com efeito, tal como se prova em [9], um grafo G, para o qual L(G)
não é completo, admite um emparelhamento perfeito se e só se υL(G) (2) = α(G).
Como consequência, todos os grafos linha de grafos com emparelhamentos perfeitos são grafos com número de estabilidade quadrático convexo.
5.3
Emparelhamentos e coberturas de arestas por
vértices
Antes de prosseguirmos convém introduzir o conceito de matriz totalmente unimodular, bem como alguns resultados que lhe estão associados. Assim, uma matriz quadrada B, com entradas inteiras, designa-se por unimodular se det(B) =
±1. Por sua vez, uma matriz A, com entradas inteiras, designa-se por totalmente
unimodular se toda a submatriz quadrada não singular de A é unimodular. Como
consequência, da definição de matriz unimodular, podemos concluir que o sistema Bx = b̂, onde B é uma matriz unimodular de ordem m e b̂ ∈ Zm , tem
uma solução de componentes inteiras. Com efeito, sendo B = [b̂1 . . . b̂m ], onde b̂j
denota a j-ésima coluna de B, para j = 1, . . . m, aplicando a regra de Cramer,
para se obter a solução x = B −1 b, vem que
xi
=
det([b̂1 . . . b̂i−1 b̂ b̂i+1 . . . b̂m ])
, i = 1, . . . , m.
det(B)
(5.17)
Logo, tendo em conta que o numerador de (5.17) é inteiro e o denominador é
±1, podemos concluir que xi tem valor inteiro, para i = 1, . . . , m.
Theorem 5.3.1. Dado um politopo definido pelo conjunto S = {x ∈ Rn : Ax =
b̂, x ≥ 0}, onde A é uma matriz totalmente unimodular, se as componentes de
b̂ são inteiras, então os vértices de S (ou seja, as soluções básicas admissíveis
para S) têm componentes inteiras.
Demonstração. A prova decorre da análise anterior.
Theorem 5.3.2. Se uma matriz A, com entradas aij ∈ {0, +1, −1}, não tem
mais do que duas componentes não nulas em cada coluna e se se os seus índices
linha podem partir-se em dois subconjuntos I1 e I2 tais que
1. se uma coluna tem duas componentes com o mesmo sinal, então as linhas
correspondentes têm os seus índices em subconjuntos diferentes,
64
Independentes, Cliques e Colorações
2. se uma coluna tem duas componentes de sinal diferente, então as linhas
correspondentes têm os sues índices no mesmo subconjunto,
então A é totalmente unimodular.
Demonstração. Vamos fazer a prova por indução sobre a ordem das submatrizes
quadradas de A, tendo em conta que qualquer submatriz de ordem 1 é submodular.
Suponha-se que o resultado é verdadeiro para matrizes quadradas de ordem inferior a
k, com k > 1 e seja B uma submatriz quadrada de A de ordem k. Vamos considerar
três casos distintos.
a) Se B tem uma coluna de zeros, então é sigular.
b) Se B tem uma coluna com uma única componente não nula, então podemos
expandir o respectivo determinante ao longo dessa coluna, pelo que o resultado
pretendido decorre da hipótese de indução.
c) Suponha-se que em B todas as colunas têm duas componentes não nulas. Então
as condições (1) e (2), implicam que para qualquer índice coluna de B, j, se
verifica a igualdade
X
X
aij =
aij .
i∈I1
i∈I2
Logo, podemos concluir que as linhas de B são linearmente dependentes e, consequentemente, B é singular.
Deste teorema decorre que as matrizes de incidência arco vértice dos grafos
orientados são totalmente unimodulares e, por sua vez, as matrizes de incidência aresta vértice de grafos não orientados bipartidos são, também, totalmente
unimodulares.
Theorem 5.3.3. Se G é um grafo bipartido, então o invólucro convexo dos
vectores característicos dos emparelhamentos de G ("matching polytope"de G)
fica definido pelas seguintes desigualdades
X
xe ≤ 1, ∀v ∈ V (G),
(5.18)
e∈∂(v)
xe
≥
0, ∀e ∈ E(G),
(5.19)
onde, para cada v ∈ V (G), ∂(v) denota o conjunto de arestas incidentes em v,
ou seja, o corte definido por v.
Demonstração. Seja M (G) o conjunto dos vectores característicos representativos
dos emparelhamentos de G (ou seja, M (G) = {x(M ) : M é um emparelhamento de G})
e seja X o subconjunto de RE(G) que verifica as restrições (5.18)-(5.19).
(i) Dado um emparelhamento M de G, é claro que o seu vector característico x(M )
verifica as restrições (5.18)-(5.19) e, deste modo, podemos concluir que M (G) ⊆
X.
(ii) Se às restrições (5.18) acrescentarmos as variáveis de desvio, obtém-se um sistema de |V (G)| equações a |E(G)|+|V (G)| variáveis, cuja matriz dos coeficientes
Emparelhamentos e coberturas de arestas por vértices
65
[A, I] verifica as hipóteses do Teorema 5.3.2. Logo, trata-se de uma matriz totalmente unimodular, pelo que as suas submatrizes quadradas não singulares
têm determinante igual a ±1. Logo, as soluções básicas admissíveis para (5.18)(5.19) têm componentes pertencentes ao conjunto {0, 1} e, consequentemente,
são vectores característicos de emparelhamentos. Assim, podemos concluir que
X ⊆ M (G).
Tendo em conta (i) e (ii), vem que M (G) = X.
É fácil verificar que as inequações (5.18)-(5.19) não são suficientes para caracterizarem emparelhamentos em grafos não bipartidos. Por exemplo, se considerarmos o grafo G não bipartido da figura a seguir, vem que xT = 21 (1, 1, 1)
é um vértice do politopo (5.18)-(5.19).
2
1
3
Figura 5.4: Grafo não bipartido.
Com efeito, a partir da figura, com facilidade se verifica que o conjunto de
restrições (5.18)-(5.19) relativo ao grafo representado, corresponde ao conjunto
restrições:
x12
+
x12
x12 ,
x23
x23
+
+
x23 ,
x13
x13
x13
≤
≤
≤
≥
1,
1,
1,
0,
para o qual xT = 12 (1, 1, 1) é admissível.
Theorem 5.3.4. Se A é uma matriz totalmente unimodular e c é um vector
de componentes inteiras, então os vértices do poliedro convexo P = {y : y T A ≥
ĉT , y ≥ 0} têm componentes inteiras.
Demonstração. Uma vez que A é totalmente unimodular, é claro que AT é uma
matriz totalmente unimodular e, consequentemente, a matriz [AT , I] também é. Logo,
do Teorema 5.3.1, podemos concluir que os vértices de P têm componentes inteiras.
Como consequências dos Teoremas 5.3.1 e 5.3.4, dada uma matriz totalmente
unimodular A, um vector de inteiros b̂ e um vector de inteiros ĉ, podemos
concluir que a relação de dualidade
max
Ax≤b̂,x≥0
ĉT x =
min
y T A≥ĉT ,y≥0
y T b̂,
é válida para vectores de inteiros x∗ e y ∗ , desde que os respectivos programas
lineares tenham óptimo finito. Na verdade, basta garantir que ambos os poliedros sejam não vazios ou que pelo menos um deles tenha óptimo finito.
66
Independentes, Cliques e Colorações
Do Teorema 5.3.1 combinado com o Teorema 5.3.3 decorre ainda que para
determinarmos um emparelhamento de cardinalidade máxima de um grafo bipartido G, basta resolver o programa linear (P)
X
max
xe
e∈E(G)
s. a
X
xe
≤ 1, ∀v ∈ V (G),
xe
≥ 0, ∀e ∈ E(G),
e∈∂(v)
cujo dual (D)
min
X
yv
v∈v(G)
s. a
X
yv
≥
1, ∀e ∈ E(G),
yv
≥
0, ∀v ∈ V (G),
v∈V (e)
permite determinar o vector característico de um conjunto de cobertura de arestas por vértices de G (que a seguir se define) com cardinalidade mínima.
Designa-se por conjunto de cobertura de arestas por vértices (ou, simplesmente, conjunto de cobertura) de um grafo G, todo o subconjunto de vértices
T ⊆ V (G) tal que qualquer aresta de G é incidente em pelo menos um vértice
de T . Um conjunto de cobertura diz-se conjunto de cobertura mínima, se não
existe outro conjunto de cobertura de menor cardinalidade. A cardinalidade de
um conjunto de cobertura mínima de um grafo H designa-se por número de
cobertura de H e denota-se por β(H). Por exemplo, o subconjunto de vértices
T = {1, 4, 5}, constitui um conjunto de cobertura mínima para o grafo G representado na Figura 5.3, pelo que β(G) = 3.
Tendo em conta que o número de cobertura de um grafo G se denota por
β(G) e denotando a cardinalidade de um emparelhamento máximo de G por
τ (G), estamos agora em condições de estabelecer os seguinte teorema obtido
por König, cuja prova é consequência, imediata, das considerações anteriores.
Theorem 5.3.5 (König). Se G é um grafo bipartido, então β(G) = τ (G).
Os conceitos de conjunto independente de vértices e de conjunto de cobertura
de arestas por vértices aparecem em muitas aplicações. Por exemplo, suponha
que pretende armazenar várias substâncias químicas em diferentes salas. É claro
que é aconselhável armazenar em salas diferentes as substâncias químicas que
são incompatíveis entre si (ou seja, aquelas que na presença umas das outras
podem provocar reacções com consequências indesejáveis). Seja G um grafo cujos vértices são as substâncias químicas e onde dois vértices são adjacentes se
e somente se as correspondentes substâncias são incompatíveis. Logo, qualquer
conjunto de vértices representando substâncias compatíveis forma um conjunto
5.4. COLORAÇÕES DE VÉRTICES E ARESTAS
67
independente de vértices em G. Por outro lado, sendo H um grafo cujos vértices são as salas e dois vértices são adjacentes se existe um corredor entre as
respectivas salas, o qual pode ser iluminado por uma fonte de luz colocada à
entrada de uma das salas, podemos concluir que um conjunto de fontes de luz
que ilumine todos os corredores constitui um conjunto de cobertura.
Theorem 5.3.6. Dado um grafo G, um subconjunto de vértices S ⊆ V (G) é
independente se e somente se T = V (G) \ S é um conjunto de cobertura de G.
Demonstração. Um subconjunto S ⊆ V (G) é um independente se e somente se não
existem vértices adjacentes em S. Logo qualquer aresta de G é incidente num vértice
de T = V (G) \ S, pelo que T é um conjunto de cobertura.
Corolário 5.3.7. Dado um grafo G, α(G) + β(G) = n.
Demonstração. Seja S um estável máximo para o grafo G. Pelo Teorema 5.3.6,
V (G) \ S é um conjunto de cobertura e, consequentemente, |V (G) \ S| = n − α(G) ≥
β(G). De modo semelhante se conclui que, sendo T um conjunto de cobertura mínima
de arestas por vértices de G, V (G) \ T é um conjunto independente de vértices de G e,
consequentemente, |V (G) \ T | = n − β(G) ≤ α(G). Tendo em conta as desigualdades
obtidas, vem que n = α(G) + β(G).
5.4
Colorações de vértices e arestas
Um dos mais velhos problemas relacionados com a Teoria dos Grafos diz respeito à coloração de mapas. Com este problema, pretende-se saber qual o menor
número de cores necessárias para pintar um mapa de modo que não existam países, com fronteira comum, pintados da mesma cor. Uma forma de modelar este
problema (ignorando situações particulares em que os países se distribuem por
diferentes componentes conexas e ainda a possibilidade de consideração de fronteiras pontuais) consiste na construção de um grafo com tantos vértices quantos
os países do mapa a colorir e ligar (com uma aresta) todos os pares de vértices
aos quais correspondam países com fronteira comum. Nestas condições, teremos
que atribuir cores aos vértices de modo que não existam vértices adjacentes com
a mesma cor.
Mais geralmente, dado um grafo arbitrário, G, designaŋse por coloração dos
vértices de G, a determinação de uma função
φ : V (G) → C,
onde C denota um conjunto finito de cores, sobrejectiva tal que φ(u) 6= φ(v) se
uv ∈ E(G). Se |C| = k, então diz-se que G é k-colorável, ou que o seu número
cromático que se denota por χ(G) e se define como sendo
χ(G) = min{|C|, φ : V (G) → C é uma coloração de vértices em G}
é uma coloração dos vértices de G, é não superior a k, i.e., χ(G) ≤ k. Em tais
condições V (G) admite uma partição nos subconjuntos V1 , . . . , Vk tal que para
68
Independentes, Cliques e Colorações
todo o i ∈ {1, . . . , k}, se x, y ∈ Vi , então xy ∈
/ E(G).
Analogamente à coloração de vértices, definemŋse colorações de arestas e de
faces, embora, no caso destas últimas, apenas para grafos planares. Sendo X o
conjunto das arestas (faces) de um grafo (grafo planar), G, dizemos que dois
elementos de X, x e y, são adjacentes se incidem no mesmo vértice (se as
fronteiras de ambos têm uma aresta em comum). A partir deste conceito de
adjacência, a função θ : X → C, onde C denota um conjunto finito de cores,
dizŋse uma coloração de arestas (faces) de G, com |C| cores, se θ é sobrejectiva
e x, y ∈ X são duas arestas adjacentes (i.e., com um vértice comum), então
theta(x) 6= θ(y). De um modo equivalente, podemos dizer que G admite uma
coloração das arestas (faces), com k = |C| cores se, sendo X o conjunto das
suas arestas (faces), X admite uma partição nos subconjuntos X1 , . . . , Xk tal
que para todo o i ∈ {1, . . . , k}, Xi não tem vértices adjacentes. Em tais condições, diz-se que G é |C|ŋcolorável nas arestas (faces). O menor |C| para o qual
G é |C|ŋcolorável nas arestas (faces) designaŋse por índice cromático (número
cromático das faces) e denotaŋse por c0 (G) (c”(G)). É claro que se G é não
nulo, então c0 (G) = c(L(G)), onde L(G) denota o grafo linha de G. Por outro
lado, se G é planar, então c(G) = c”(G∗ ) e c(G∗ ) = c”(G), onde G∗ denota o
respectivo dual. Um resultado publicado em (Vizing, 1964) estabelece limites
muito apertados para a coloração das arestas de grafos arbitrários. Com efeito,
de acordo com o teorema de Vizing, dado um grafo, G,
∆(G) ≤ χ0 (G) ≤ ∆(G) + 1.
Desde muito cedo se conjecturou que 4 cores bastariam para resolver o problema da coloração dos vértices de grafos planares. O cartógrafo inglês Francis
Guthrie, já em 1852, reclamava a suficiência de 4 cores para distinguir os países
num mapa plano e foi precisamente nesse ano (1852) que A. de Morgan, numa
carta que enviou a W. R. Hamilton, afirmou ter tomado conhecimento deste
problema, que designou por problema das 4 cores, através de um seu aluno,
Frederick Guthrie (irmão de Francis Guthrie). Em 1878, numa comunicação
apresentada na "London athematical Society", Cayley referiuŋse ao problema
das 4 cores como sendo um problema em aberto. Em 1879, Kempe propôs uma
pretensa solução que só em 1890 foi refutada por Heawood, no seu primeiro
trabalho escrito onde provou a suficiência de cinco cores para a coloração dos
vértices de grafos planares. O teorema que se segue estabelece, precisamente,
o resultado obtido por Heawood, com base no método utilizado por Kempe 11
anos antes.
Theorem 5.4.1 (Heawood, 1890). Todo o grafo planar admite uma coloração
dos vértices com 5 cores.
Colorações de vértices e arestas
69
Demonstração. A prova será feita por indução sobre o número de vértices do grafo.
Suponhaŋse que G é um grafo planar não nulo e que o resultado é valido para grafos
planares com menor número de vértices do que |V(G)|. Pelo Teorema 3.2.4, existe
v ∈ V (G) tal que dG (v) ≤ 5 e, por hipótese de indução, G[V (G) \ {v}] admite uma
coloração com 5 cores. Se nem todas as 5 cores são utilizadas nos vértices adjacentes
a v, então uma das que ficam livres pode ser utilizada em v e, consequentemente,
G admite uma coloração de vértices com 5 cores. Suponhaŋse que todos os vértices
adjacentes a v, v1 , v2 , v3 , v4 e v5 têm cores distintas (as quais vamos identificar
por 1, 2, 3, 4 e 5 e supôr distribuídas segundo uma ordem contrária aos ponteiro do
relógio).
Seja V1;3 o conjunto de vértices que podem ser alcançados a partir de v1 por um
caminho que utiliza unicamente vértices com as cores 1 e 3. Então, podemos trocar
estas duas cores, entre si, em V1;3 ∪{v1 }, sem que vértices adjacentes deixem de ter cores
distintas. Se v3 ∈
/ V1;3 então, após a troca de cores, nenhum dos vértices adjacentes a
v tem a cor 1, pelo que a podemos utilizar para v.
Suponhaŋse que v3 ∈ V1;3 e seja (v1 , u1 , . . . , uk , v3 ) um caminho (entre v1 e v3 ) com
cores, alternadamente, 1 e 3. Acrescentando v a este caminho obtémŋse um ciclo, C1;3
homeomorfo a uma curva de Jordan fechada que, consequentemente, divide o plano
em duas componentes conexas por caminhos e, de acordo com esta construção, fica
claro que v2 e v4 pertencem a componentes distintas.
Seja V2;4 o conjunto dos vértices alcançados, a partir de v2 , por trajectos que utilizam,
unicamente, as cores 2 e 4. Então, nenhum destes trajectos cruza o ciclo C1;3 , pelo
que V2;4 está na componente que contém v2 , cuja fronteira é C1;3 e v4 ∈
/ V2;4 . Logo,
trocando as cores 2 e 4, entre si, em V2;4 ∪ {2}, a cor 2 fica livre para o vértice v.
Um grafo G diz-se k-conexo (k ∈ N ∪ {0}) se a ordem de G é superior a k
e G − X é conexo para todo o X ⊂ V (G), com |X| < k. Por outras palavras,
G é k-conexo se não existem dois vértices de G separáveis por menos do que k
outros vértices. Todo o grafo não vazio é 0-conexo e todos os grafos conexos não
triviais são 1-conexos. O maior inteiro k tal que G é k-conexo designa-se por
conectividade de G e denota-se por k(G). Consequentemente, k(G) = 0 se e só
se G é desconexo ou G = K1 . É claro que, para todo o n ∈ N k(Kn ) = n − 1.
Designa-se por triangulação do plano (ou planar) todo o grafo conexo planar
cujas faces têm como fronteira K3 (ou seja, triângulos). Uma triangulação do
plano também se designa por grafo conexo planar maximal. Esta designação
deve-se ao facto de um tal grafo, G, apresentar a particularidade de ter um
número de arestas igual a 3|V (G)|6. Com efeito, de acordo com o Corolário 3.2.2,
para qualquer grafo conexo planar H, |E(H)| ≤ 3|V (H)|6 e, por outro lado, se
todas as faces de H têm K3 como fronteira, então 3|F0 (H)| = 2|E(H)|, pelo
que, tendo em conta a própria fórmula de Euler, |E(H)| = 3|V (H)|6. Verifica-se
ainda que qualquer triangulação planar, G, tal que |V (G)| ≥ 4, é um grafo, pelo
menos, 3-conexo. Tendo em conta que um grafo cúbico é um grafo regular com
vértices de grau 3, pode concluir-se que se G é um grafo 2-conexo planar, então
um grafo G é uma triangulação se e só se o seu dual, G∗ , é um grafo
cúbico e G é um grafo cúbico planar se e só se G∗ é uma triangulação.
Para se provar o teorema das quatro cores é suficiente provar que qualquer
grafo planar maximal (triangulação do plano) tem número cromático não superior a 4.
70
Independentes, Cliques e Colorações
Theorem 5.4.2. Se G é um grafo cúbico que admite um ciclo de Hamilton,
então G admite uma coloração das arestas com 3 cores (i.e χ0 (G) ≤ 3).
Demonstração. Dado que, de acordo com a hipótese, todos o vértices têm grau
3, podemos concluir que a ordem de G é par (i.e., |V (G)| = 2k). Logo, sendo C =
(x1 , x2 , . . . , x2k , x1 ) um ciclo de Hamilton para G, então |V (G)| = |V (C)| = |E(C)|,
pelo que |E(C)| é também par. Como consequência, atribuindo-se a cor 1 às arestas
x2j−1 x2j , para j = 1, . . . , k, a cor 2 à aresta x2k , x1 e às arestas x2j x2j+1 , para j =
1, . . . , k − 1 e a cor 3 às restantes, obtém-se uma coloração das arestas de G sem que
existam arestas incidentes no mesmo vértice com a mesma cor.
Uma outra tentativa falhada para a resolução do problema das quatro cores
(a adicionar à de Kempe) foi apresentada em 1880 por Tait que, por essa altura,
estava convencido que qualquer grafo cúbico 2-conexo planar admitiria um ciclo
de Hamilton e, consequentemente, pelo Teorema-5.4.2, admitiria uma coloração
de arestas com três cores. Esta pretensa majoração para o índice cromático dos
grafos cúbicos planares, veio a ser refutada, em 1946, por Tutte que, então,
exibiu um grafo cúbico 2-conexo planar não hamitoniano com 69 arestas, 46
vértices e 25 faces), (Tutte, 1946).
Relativamente aos grafos cúbicos 2-conexos não hamiltonianos, deve observar-se ainda que já em 1891 Peterson tinha encontrado um grafo cúbico 2-conexo
(o famoso grafo de Peterson2 , representado na capa) com um índice cromático
superior a 3 (logo, não hamiltoniano). No entanto, trata-se de um grafo não
planar.
Ambas as tentativas de resolução do problema das quatro cores, porém,
tiveram contributos positivos. Kempe introduziu o conceito, que actualmente
se designa por cadeia de Kempe (que corresponde a uma componente conexa
induzida pelos vértices coloridos, unicamente, com duas cores, e que é utilizada
na redutibilidade de configurações a que se recorre na prova, até ao momento
obtida, para o teorema das quatro cores) e Tait mostrou (com o teorema que
se segue) que o problema da coloração dos vértices de triangulações do plano
com quatro cores é equivalente à coloração das arestas do correspondente grafo
dual com apenas com 3 cores. Note-se que colorir as arestas do grafo dual de
uma triangulação do plano com três cores, é equivalente a etiquetar as arestas
que constituem as fronteiras triangulares de cada face com as cores das arestas
duais que as cruzam, de tal forma que cada triângulo contenha as três cores.
Theorem 5.4.3 (Tait,1878-80). Sendo G uma triangulação do plano, χ(G) ≤
4 se e só se as arestas de G podem ser etiquetadas com três etiquetas distintas
de tal modo que na fronteira de cada face existam as três etiquetas.
Demonstração. Suponha-se que G admite a coloração de vértices f : V (G) →
{(0, 0), (1, 0), (0, 1), (1, 1)} e que, a partir dela, se define a etiquetação de arestas determinada pela aplicação ψ : E(G) → {(1, 0), (0, 1), (1, 1)} tal que se uv ∈ E(G) então
2 O grafo de Peterson, K(5,2), é um caso particular dos grafos de Kneser, K(n,k), que se
definem, para n ≥ 2k, pelos vértices correspondentes a subconjuntos de k elementos de um
conjunto de n elementos, em que dois vértices são adjacentes sse correspondem a subconjuntos
disjuntos. Deve observarŋse ainda que o grafo de Perterson corresponde ao complementar de
L(K5 ).
Colorações de vértices e arestas
71
f (u) = (ux , uy ), f (v) = (vx , vy ) e
ψ(uv) = f (u) + f (v) = (ux + vx mod 2, uy + vy mod 2).
Nestas condições ψ(uv) associa às arestas de cada triângulo, as etiquetas (1, 0), (0, 1)
e (1, 1).
Reciprocamente, seja ψ : E(G) → {(1, 0), (0, 1), (1, 1)} uma função de etiquetação das
arestas de G, de tal forma que cada face contenha as três etiquetas. Seja v1 um vértice
arbitrário e seja f : V (G) → {(0, 0), (1, 0), (0, 1), (1, 1)} tal que
X
f (x) =
ψ(e) mod 2,
e∈Pv1 x
onde Pv1 x é um caminho (ou passeio) arbitrário entre v1 e x. Assim, resta provar que
a função f está bem definida, ou seja, o seu valor é independente do caminho (ou
passeio) escolhido entre v1 e x (o que é equivalente a afirmar que o seu valor é nulo
para x = v, considerando qualquer circuito) e ainda que f (x) 6= f (y) se xy ∈ E(G).
Um vez que a segunda parte é imediata, vamos provar apenas a primeira parte.
Seja C um ciclo arbitrário de G, pelo que ou é um triângulo ou o domínio interno
da curva de Jordam que lhe está associada está dividido em triângulos Ti . Então,
procedendo à adição módulo 2 das etiquetas das arestas que constituem os triângulos,
obtémŋse (1, 0)+(0, 1)+(1, 1) = (0, 0) e, sendo T o conjunto dos triângulos do domínio
interno de C (incluindo os que têm uma aresta em C), vem que
X
X
X
0=
ψ(e) =
ψ(e) +
ψ(e).
e∈E(T )
e∈E(C)
e∈E(T )\E(C)
Dado que as arestas de E(T ) \ E(C) estão
P associadas a dois triângulos (logo contam duas vezes), podemos concluir que e∈E(T )\E(C) ψ(e) = 0 e, consequentemente,
P
e∈E(C) ψ(e) = 0.
Com facilidade se conclui que se um grafo planar, G, admite um ciclo de
Hamilton, então as faces do domínio interior da curva de Jordan associada a
esse ciclo podem ser coloridas, alternadamente, com as cores 1 e 2 e as faces
do domínio exterior coloridas, alternadamente, com as cores 3 e 4, pelo que
χ(G) ≤ 4. Um resultado relativamente recente, publicado em (Grimberg, 1968),
tornou mais fácil a construção de contraŋexemplos para a conjectura de Tait
(de que todos os grafos cúbicos 2ŋconexos planares seriam hamiltonianos).
Theorem 5.4.4 (Grimberg, 1968). Seja G é um grafo planar hamiltoniano,
CH um ciclo hamiltoniano para G, F0int (CH) e F0ext (CH) os subconjuntos
de faces de G pertencentes, respectivamente, ao domínio interior e exterior da
curva de Jordan definida por CH. Denotando por fiint e fiext o número de faces
de grau i existentes, respectivamente, em F0int (CH) e F0ext (CH), então
X
(i − 2)(fiint − fiext ) = 0,
i
onde o somatório é estendido a todos os graus das faces de G.
Demonstração. Suponhaŋse que o grafo G é realizado na esfera, pelo que CH separa
a superfície esférica em duas componentes conexas, uma que contém as faces do subconjunto F0int (CH) e outra que contém as faces do subconjunto F0ext (CH), as quais continuaremos a designar, respectivamente, por domínio interior e exterior de CH. Sendo
72
Independentes, Cliques e Colorações
E(G) = E(CH) ∪ Eint (CH) ∪ Eext (CH), onde Eint e Eext (CH) denotam os subconjuntos de arestas que não estão em E(CH) e pertencem, respectivamente, ao domínio
interior e exterior de CH (pelo que |E(G)| = |E(CH)| + |E int (CH)| + |E ext (CH)|),
com facilidade se conclui que |F0int | = |E int (CH)| + 1 e |F0ext | = |E ext (CH)| + 1. Logo,
vem que
X int
|F0int (CH)| =
fi = |E int (CH)| + 1
(5.20)
i
|F0ext (CH)|
=
X
fiext = |E int (CH)| + 1
(5.21)
i
e, por outro lado,
X
ifiint
=
|E(CH)| + 2|E int (CH)|
(5.22)
ifiint
=
|E(CH)| + 2|E int (CH)|
(5.23)
i
X
i
Combinando as igualdades (5.20) e (5.22) e as igualdades (5.21) e (5.23) decorre que
X
X
(i − 2)fiint = |E(CH)| − 2 e
(i − 2)fiext = |E(CH)| − 2
i
e, consequentemente,
i
P
i
(i −
2)(fiint
−
fiext )
= 0.
Como consequência deste teorema, Grinberg construiu vários contraŋexemplos, para a conjectura de Tait.
Se χ(G) = k, mas χ(G0 ) < k, para qualquer subgrafo próprio de G (ou
seja, ⊆ G0 e |V (G0 )| + |E(G0 )| < |V (G)| + |E(G)| ⇒ χ(G0 ) < cχ(G)), então G
dizŋse kŋcríticoŋcolorável. Por outro lado, x ∈ V (G) ∪ E(G) diz-se um elemento
crítico de G se χ(G − {x}) < χ(G). Consequentemente, G é crítico se todos
os seus vértices e todas as suas arestas são elementos críticos. Os únicos grafos
k-crítico-coloráveis, para k ∈ {1, 2} são os grafos completos K1 e K2 . Parece
não existir qualquer caracterização razoável para os grafos 4-crítico-coloráveis,
ou equivalentemente, para os grafos 3-coloráveis, o mesmo não acontecendo,
porém, relativamente aos grafos bi-coloráveis que são grafos bipartidos.
Theorem 5.4.5 (Appel e Haken, 1977). χ(S0 ) = 4.
Designa-se por bloco todo o grafo sem vértices de corte, pelo que, com excepção do bloco trivial K2 , também não tem arestas de corte. Por sua vez, designaŋse por bloco de um grafo G, todo o subgrafo maximal que define um bloco
(i.e., sem vértices de corte). Logo, todo o bloco de um grafo G, ou é um subgrafo
maximal 2-conexo, ou uma ponte ou um vértice isolado. Tendo em conta a propriedade de maximalidade, dois blocos diferentes de um mesmo grafo conexo, G,
apenas se sobrepõem num único vértice que, em tais condições, é um vértice de
corte de G. Consequentemente, pode concluir-se que cada aresta pertence a um
único bloco e que um grafo é união dos seus blocos, podendo interpretar-se os
blocos como sendo as componentes 2-conexas que constituem o grafo. Designa-se por bloco extremo todo o bloco que contém, unicamente, um vértice de corte
de G.
Colorações de vértices e arestas
73
Theorem 5.4.6. Qualquer que seja o grafo G,
χ(G) ≤ max{δ(G[U ]) : U ⊆ V (G)} + 1.
Demonstração. Suponhaŋse que G tem ordem n e seja k = max{δ(G[U ]) : U ⊆
V (G)}. Seja vn um vértice de G tal que dG (vn ) ≤ k e Hn−1 = G − {vn }. Por hipótese,
Hn−1 tem um vértice de grau não superior a k. Seja vn−1 um desses vértices e seja
Hn−2 = Hn−1 − {vn−1 }, i.e, Hn−2 = G − {v1 , v2 }. Continuando este processo obtém-se uma sequência de vértices de G, v1 , . . . , vn , tal que vj é adjacente a um máximo
de k vértices que o precedem. Consequentemente, para os colorir, no máximo, são
necessárias k + 1 cores.
Se G é um grafo conexo não regular, então max{δ(G[U ]) : U ⊆ V (G)} ≤
∆(G) − 1 e, consequentemente, por aplicação do Teorema 5.4.6, χ(G) ≤ ∆(G).
O teorema a seguir generaliza esta desigualdade para os grafos conexos regulares
que não são completos nem ciclos de comprimento ímpar.
Theorem 5.4.7 (Brooks, 1941). Sendo G um grafo conexo, se G não é completo nem um ciclo de comprimento ímpar, então χ(G) ≤ ∆(G).
Demonstração. No caso de G ser não regular já se concluiu que χ(G) ≤ ∆(G), pelo
que vamos fazer a prova para o caso de G ser regular. Adicionalmente, sem perda de
generalidade, vamos assumir que G é pelo menos 2ŋconexo 3 e que δ(G) = ∆(G) ≥ 3,
uma vez que um grafo regular tal que δ(G) = ∆(G) = 2, nas condições da hipótese, é
um ciclo de comprimento par, logo com número cromático igual a 2.
No caso de G ser 3ŋconexo, considere-se vn como sendo um vértice de G com dois
vizinhos, v1 e v2 , não adjacentes (um tal vértice existe uma vez que G não é completo).
Caso G seja 3ŋconexo, considere-se vn como sendo um vértice tal que G − {vn } é um
grafo separável, pelo que tem pelo menos dois blocos e dado que G é 2ŋconexo, cada
bloco extremo do subgrafo G − {vn } tem um vértice adjacente a vn , respectivamente,
v1 e v2 .
Em qualquer dos casos os vértices v1 , v2 e vn são tais que G − {v1 , v2 } é conexo, v1 v2 ∈
/
E(G), mas v1 vn , v2 vn ∈ E(G). Consideremŋse os vértices de N (vn ) = NG−{v1 ,v2 } (vn ),
como sendo vn1 , . . . , vn−k1 , onde k1 = |NG−{v1 ,v2 } (vn )|, seguidamente consideremŋse
os vértices do conjunto
N (vn−k1 ) = NG−{v1 ,v2 } (vn−1 ) ∪ . . . ∪ NG−{v1 ,v2 } (vn−k1 ) \ {vn , . . . , vn−k1 }
como sendo vn−k1 −1 , . . . , vn−k1 −k2 , onde k2 = |N (vn−k1 )|, e assim sucessivamente.
Com o procedimento referido, obtémŋse a sequência de vértices v1 , v2 , . . . , vn−1 , em
que, com com excepção de vn , todos os vértices são adjacentes a pelo menos um dos
seguintes. Uma vez que v1 e v2 têm a mesma cor, vn é adjacente a ambos e vj , com
j ∈ {3, . . . , n − 1} tem no máximo ∆(G) − 1 vizinhos na subsequência v1 , v2 , . . . , vj−1 ,
quando muito, serão necessárias ∆(G) cores, para colorir os vértices de G.
À primeira vista tudo indica que a existência de grafos com elevado número
cromático está directamente relacionada com a existência, nesses grafos, de subgrafos completos de elevada cardinalidade. O teorema a seguir, porém, contraria
uma tal relação, ao garantir a existência de grafos com cintura superior a 3 (i.e.,
sem triângulos) e com número cromático arbitrário.
3 No caso dos grafos 1ŋconexos, G, sendo G = G ∪ . . . ∪ G , onde G , . . . , G são os seus
p
p
1
1
blocos, χ(G) = max{χ(Gj ), j = 1, . . . , p}.
74
Independentes, Cliques e Colorações
Theorem 5.4.8 (Zykov, 1949). ∀k ∈ N, existe um grafo Gk tal que g(Gk ) > 3
e χ(Gk ) = k.
Demonstração. Vamos fazer a prova por indução sobre k, assumindo que o resultado
é verdadeiro G1 , . . . , Gk−1 . Consideremŋse cópias disjuntas destes grafos e seja V =
|V (G1 )| × . . . × |V (Gk−1 )| um conjunto de novos vértices definidos pelos (k − 1)-uplos
de vértices obtidos pela selecção de um vértice de cada um dos grafos G1 , . . . , Gk−1 .
Assim, Gk é obtido de G1 , . . . , Gk−1 e V , ligando cada vértice de V aos k − 1 vértices
que lhe correspondem em G1 , . . . , Gk−1 , um em cada Gi , pelo que χ(G) ≤ k (a). Por
outro lado, em G1 existe um vértice v1 com uma certa cor c1 , em G2 existe um vértice
v2 com uma cor c2 6= c1 (dado que χ(G2 ) = 2), em G3 existe um vértice v3 com
uma cor c3 ∈
/ {c1 , c2 } (dado que χ(G2 ) = 3), etc. Consequentemente, o vértice v ∈ V
adjacente a v1 , . . . , vk1 , tem de ter uma cor distinta de c1 , . . . , ck−1 , pelo que χ(G) ≥ k
(b). Tendo em conta as desigualdades (a) e (b) concluiŋse que cχ(Gk ) = k.
Segueŋse a conjectura, ainda em aberto, formulada por Hadwiger em 1943.
Conjectura 5.4.1 (Hadwiger, 1943). Dado um grafo arbitrário, G, para
todo o inteiro positivo p, χ(G) ≥ p ⇒ Kp ≤ G, onde S ≤ T denota que S é um
menor de T .
Esta conjectura está provada para p ∈ {1, 2, 3, 4, 5, 6}. Para p = 7, no entanto, a conjectura continua em aberto e a sua prova ou refutação constitui um
dos grandes desafios da Teoria dos Grafos. A conjectura de Hadwiger (Hadwiger, 1943) é trivialmente verdadeira para p ∈ {1, 2}. Para p = 3, decorre da
implicação de que se G não contém K3 como menor, então G não contém ciclos
(pelo que é uma floresta), logo G é bipartido e, consequentemente, é bi-colorável,
i.e., χ(G) < 3. Para p = 4, a prova pode ser consultada em (Diestel, 1997) pag.
181-182. Por sua vez, o teorema das 4 cores implica a conjectura de Hadwiger
para p = 5, i.e., χ(G) ≥ 5 ⇒ K5 ≤ G, podendo a respectiva demonstração ser
consultada em (Parathasarathy, 1994) pag. 306-307 ou (Diestel, 1997) pag. 182183. A prova da conjectura de Hadwiger para p = 6 decorre de um estudo sobre
grafos não contractíveis a K6 , desenvolvido em (Robertson, Seymour e Thomas,
1993), onde, assumindo a validade do teorema das quatro cores, se conclui que
tais grafos são 5-coloráveis e, consequentemente, que a conjectura de Hadwiger
é verdadeira para p=6. Com facilidade se prova ainda que se a conjectura de
Hadwiger é verdadeira para p = q, então também é verdadeira para p < q. Com
efeito, supondo que a conjectura é verdadeira para p = q e que χ(G) ≥ q − 1,
então, fazendo
G ⊕ v = (V (G) ∪ {v}, E(G) ∪ {xv : x ∈ V (G)})
com v ∈
/ V (G), vem que χ(G ⊕ v) = χ(G) + 1 ≥ q e, uma vez que por hipótese
Kp ≤ G ⊕ v, conclui-se que Kq−1 ≤ G. Desta última conclusão, ou seja, da
implicação
(χ(G) ≥ p ⇒ Kp ≤ G) ⇒ (χ(G) ≥ p − 1 ⇒ Kp−1 ≤ G)
decorre, ainda, que a prova da validade da conjectura de Hadwiger para p ≥ 5,
Colorações de vértices e arestas
75
implica a validade do teorema das 4 cores. Com efeito, para p = 5 + k, vem que
(χ(G) ≥ 5 + k ⇒ K5+k ≤ G) ⇒ (χ(G) ≥ 5 + k − 1 ⇒ K5+k−1 ≤ G)
⇒ (χ(G) ≥ 5 + k − 2 ⇒ K5+k−2 ≤ G)
..
.
⇒ (χ(G) ≥ 5 ⇒ K5 ≤ G).
Logo, se G é plano, então G não é contractível a K5 (i.e., K5 não é um menor
de G) e, da última das implicações obtidas conclui-se que χ(G) < 5.
Tendo em conta que do Teorema 3.3.4 combinado com a desigualdade gKn ≤
(n−3)(n−4)
d
e, obtida em (Ringel and Youngs, 1968), se obtém a igualdade gKn =
12
d (n−3)(n−4)
e e ainda que χ(Kp ) = p, pode agora concluir-se que ∀n > 0
12
√
7 + 1 + 48n
χ(Sn ) ≥ b
c.
2
√
Com efeito, sendo p = b 7+
1+48n
c,
2
√
gKp
=
=
≤
=
(b 7+
dado que gKp = d (n−3)(n−4)
e, vem que
12
√
1+48n
c
2
− 3)(b 7+ 1+48n
c − 4)
2
d
e
12
√
√
b 7+ 1+48n
− 3cb 7+ 1+48n
− 4c
2
2
d
e
12
−1+1+48n
c
b
4
d
e
12
n.
(5.24)
(5.25)
(5.26)
Note-se que a igualdade (5.24) se obtém, tendo em conta que bxc − m = bx −
mc ∀m ∈ Z e a desigualdade (5.25) decorre da desigualdade bxcbyc ≤ bxyc.
Logo, podemos concluir que Kp é realizável em Sn , donde decorre que
√
7 + 1 + 48n
χ(Sn ) ≥ χ(Kp ) = p = b
c
(5.27)
2
√
Em 1890, Heawood conjecturou a identidade χ(Sn ) = b 7+ 1+48n
c ∀n > 0,
2
tendo apenas provado a desigualdade recíproca da desigualdade (5.27). Combinando estas duas desigualdades fica feita a prova da conjectura de Heawood.
√
Theorem 5.4.9. ∀g ≥ 0 χ(Sg ) = b 7+
1+48g
c.
2
Demonstração. Uma vez que, de acordo com o teorema das quatro cores, χ(S0 ) = 4
e, para g = 0, se obtém
√
√
7 + 1 + 48g
7+ 1+0
b
c=b
c = 4 = χ(S0 ),
2
2
resta fazer a prova para g > 0.
√
Tendo em conta a desigualdade (5.27), sabe-se que χ(Sg ) ≥ b 7+ 1+48g
c, para g ≥ 1.
2
76
Independentes, Cliques e Colorações
Logo, para g ≥ 1, pode concluir-se que χ(Sg ) ≥ 7. Seja G um grafo com genus g ≥ 1
tal que χ(G) = k ≥ 7. Tendo em conta que |V (G)| ≥ 3, cada face de G é limitada por,
pelo menos, 3 arestas e, consequentemente, 3|Fg (G)| ≤ 2|E(G)|. Logo, por aplicação
da fórmula de Euler generalizada (|V (G)| + |Fg (G)| − |E(G)| = 2(1 − g)),
|E(G)|
≤
3|V (G)| − 6(1 − g).
(5.28)
Sendo G0 um subgrafo de G k-critico-colorável, então δ(G0 ) ≥ k − 14 e, tendo em conta
(5.28), δ(G0 )|V (G0 )| ≤ 6|V (G0 )| − 12(1 − g). Consequentemente, (k − 1)|V (G0 )| ≤
6|V (G0 )| − 12(1 − g). Dado que esta última inequação é equivalente a (k − 7)|V (G0 )| +
12(1 − g) ≤ 0 e que 7 ≤ k ≤ |V (G0 )|, conclui-se que (k − 7)k + 12(1 − g)) ≤ 0 ⇔
k2 − 7k + 12(1 − g) ≤ 0. Logo, vem que
p
√
√
7 + 49 − 48(1 − g)
7 + 1 + 48g
7 + 1 + 48g
k≤
=
⇔b
c.
2
2
2
Deve observar-se que a demonstração deste teorema vai contra a nossa intuição de que seria mais simples determinar χ(S0 ) do que χ(Sn ), para n > 0.
Com efeito, embora se tenham obtido ambos os resultados, as técnicas até ao
momento utilizadas para se chegar à determinação do primeiro são bem mais
elaboradas do que as utilizadas na determinação do segundo.
Theorem 5.4.10 (Gaddum, Nordthaus, 1960). Sendo Ḡ o grafo complementar de G verifica-se que χ(Ḡ) + χ(G) ≤ |V (G)| + 1.
Demonstração. Vamos fazer a prova por indução sobre o número de vértices, tendo
em conta que o resultado é trivialmente verdadeiro para grafos de ordem 1 e 2.
Suponha-se que o resultado é verdadeiro para grafos com menos vértices do que os
de G e que |V (G)| ≥ 2. Sendo G0 o subgrafo obtido de G por eliminação de um vértice
x, vem que
χ(G)
χ(Ḡ)
≤
≤
χ(G0 ) + 1,
0
χ(Ḡ ) + 1
(5.29)
(5.30)
Se a igualdade se verifica em (5.29) e em (5.30), então dG (x) ≥ χ(G0 ) e dḠ (x) ≥ χ(Ḡ0 ).
Consequentemente,
χ(Ḡ) + χ(G) = χ(G0 ) + χ(Ḡ0 ) + 2 ≤ dḠ (x) + dG (x) + 2 = |V (G)| + 1.
Suponha-se que a igualdade não se verifica em ambas a inequações (5.29) e (5.30).
Então χ(Ḡ) + χ(G) ≤ χ(Ḡ0 ) + χ(G0 ) + 1 ≤ |V (G0 )| + 1 + 1 = |V (G)| + 1.
Para se concluir que o majorante determinado no Teorema 5.4.10 é atingido,
basta exibir um par de grafos complementares, para o qual se obtém a igualdade
(o que não é difícil).
Corolário 5.4.11. Sendo Ḡ o grafo complementar de G, verifica-se a desigual2
dade χ(G)χ(Ḡ) ≤ b (|V (G)|+1)
c
2
4 Note-se que se v ∈ V (G0 ) é um vértice k-crítico-colorável, então χ(G0 −{v}) = χ(G0 )−1 ≤
dG (v) e, consequentemente, se G0 é k-crítico-colorável, então χ(G0 ) − 1 ≤ δ(G0 ).
Colorações de vértices e arestas
77
Demonstração.
4χ(G)χ(Ḡ) ≤ 4χ(G)χ(Ḡ) + (χ(G) − χ(Ḡ))2 = (χ(G) + χ(Ḡ))2 ≤ (|V (G)| + 1)2 .
Tal como anteriormente, neste caso, também se verifica que o majorante é
atingido.
Theorem 5.4.12. Dado um grafo arbitrário G, verificam-se as seguintes desigualdades:
χ(G) + α(G) − 1 ≤ |V (G)| ≤ χ(G)α(G).
Demonstração. Seja χ(G) = k e atribuamŋse aos vértices de G as cores c1 , . . . , ck .
Sendo Si ⊂ V (G) o subconjunto de vértices com a cor ci , para i = 1, . . . , k, cada
subconjunto Si é um estável para G. Logo, α(G) ≥ |Si | ∀i ∈ {1, . . . , k} e
|V (G)| = |S1 ∪ . . . ∪ Sk | =
k
X
|Si | ≤ kα(G) = χ(G)α(G).
i=1
Adicionalmente, supondo que aos vértices de um estável máximo, S, é atribuída uma
cor, então aos restantes |V (G)| − α(G) vértices poder-se-ão atribuir |V (G)| − α(G)
cores, pelo que χ(G) ≤ |V (G)| − α(G) + 1 ⇔ χ(G) + α(G) − 1 ≤ |V (G)|.
Theorem 5.4.13. Se G é um grafo de ordem n e dimensão m, então
χ(G) ≥
n2
n2
.
− 2m
Demonstração. Seja χ(G) = k e sejam S1 , . . . , Sk os conjuntos de vértices com as
cores c1 , . . . , ck . Ordenando os vértices convenientemente e denotando os conjuntos de
índices associados aos vértices de Si , para i = 1, . . . , k, por J(Si ), verifica-se que a
matriz de adjacência de G, AG , toma o seguinte aspecto:
J(S1 )
J(S1 )
0
J(S2 ) 
 ···
AG = .
 .
..
 ..
J(Sk )
···

J(S2 )
···
0
..
.
···
···
···
···
..
.
···
J(Sk )

···
··· 

.. .
. 
0
Seja ni o número de vértices do conjunto Si (ni = |Si |), para i = 1, . . . , k e seja N0 e
N1 , respectivamente, o número de entradas nulas e entradas unitárias da matriz AG .
Então, por um lado, tendo em conta a desigualdade de Chebishev,
P
k
X
( ki=1 ni )2
n2
N0 ≥
n2i ≥
=
k
k
i=1
e, por outro lado, N1 = 2m, uma vez que a soma das componentes unitárias de cada
linha (ou coluna) da matriz corresponde ao grau do vértice que lhe está associado.
Consequentemente, o número total de entradas da matriz AG vem dado por
n2 = N0 + N1 ≥
n2
n2
+ 2m ⇔ χ(G) = k ≥ 2
.
k
n − 2m
78
5.5
Independentes, Cliques e Colorações
Exercícios
5.5.1. Dado um grafo G de ordem n e o programa quadrático
min xT AG x,
(P Q)
x∈∆
P
onde ∆ = {x : j xj = 1, x ≥ 0}, prove que se x∗ é solução óptima para
o problema de optimização
xT AG x
,
06=x≥0 xT AKn x + ||x||2
min
então existe λ∗ > 0 tal que λ∗ x∗ é uma solução óptima para (PQ).
5.5.2. Sendo G um grafo p-regular, prove que se o programa quadrático convexo
(PG (τ ))
υG (τ ) = max 2êx − xT (
x≥o
AG
+ I)x,
τ
onde τ = −λmin (AG ), atinge o seu valor óptimo num ponto crítico da
função objectivo, então todas as soluções óptimas são pontos críticos para
a função objectivo.
5.5.3. Prove que se uma árvore tem um emparelhamento perfeito, então esse
emparelhamento é único.
5.5.4. Dado um grafo bipartido G, com matriz de incidência aresta vértice BG ∈
Rn×m , considere os pares de problemas primal dual:
X
X
(P )
max
xij
(D)
min
yv
ij∈E(G)
s. a BG x ≤ ê,
v∈V (G)
T
s. a y BG ≥ ē,
x ≥ 0,
y ≥ 0,
onde ê e ē denotam vectores de componentes unitárias de Rn e Rm , respectivamente. Prove que uma solução óptima de (P) define o vector característico de um emparelhamento máximo e uma solução óptima de (D)
define o vector característico de um conjunto de cobertura mínima de
arestas por vértices.
5.5.5. Dado um grafo arbitrário G de ordem n, prove a desigualdade
χ(G) ≤
(n + 1)2
.
2α(G)
Capítulo 6
Resultados Algébricos
Associados a Grafos
6.1
Polinómios cromáticos
Birkhoff e Lewis [6] introduziram os polinómios cromáticos, tendo como objectivo a resolução do problema das quatro cores. Para um grafo G, dado um
conjunto de λ cores, a função f (G; λ) define-se como sendo o número de colorações (adequadas, ou seja, colorações de vértices sem vértices adjacentes com a
mesma cor.) dos vértices que é possível realizar em G, com λ cores e designa-se
por polinómio cromático de G. Logo, se λ < χ(G), então f (G; λ) = 0 e
χ(G) =
min
f (G;λ)>0
λ.
É fácil concluir que f (Kn ; λ) = λ(λ−1) · · · (λ−(n−1)), para λ ≥ n. Com efeito,
começando por escolher um vértice arbitrário, podemos colori-lo com qualquer
das λ cores, para o segundo vértice escolhido a sua coloração pode ser feita com
qualquer das λ − 1 cores que restam, etc. Por exemplo,
f (K3 ; λ)
f (Knc ; λ)
= λ(λ − 1)(λ − 2)
= λn .
No que se segue uma coloração de vértices designa uma coloração adequada
de vértices.
Theorem 6.1.1. Se G é um grafo, então ∀e ∈ E(G)
f (G; λ) = f (G \ e; λ) − f (G/e; λ).
Demonstração. Seja e = uv uma aresta de G. Tendo em atenção que f (G \ e; λ)
denota o número de colorações de G \ e, utilizando λ cores, podemos concluir que esse
número é igual é soma do número de colorações de G \ e, com u e v recebendo a mesma
cor (o qual é igual ao número de colorações de G/e) mais o número de colorações de
G \ e, com u e v recebendo cores distintas (o qual é igual ao número de colorações de
G). Logo, vem que f (G \ e; λ) = f (G; λ) + f (G/e; λ).
79
80
Resultados Algébricos Associados a Grafos
É imediato concluir que dados dois grafos disjuntos G e H, denotando por
G + H a sua união, vem que f (G + H; λ) = f (G; λ)f (H; λ).
Denotando por Cr um ciclo com r vértices, por Ps um caminho com s vértices e por kH a união de k cópias de H, como exemplo de aplicação, vamos
determinar o polinómio cromático do grafo C4 , representado na figura a seguir, utilizando dois métodos distintos.
y
y
x
z
x
z
x
z
w
C4
w
P4 = C4 \ xy
w
K3 = C4 /xy
y
y
y
x
z
w
2K2 = P4 \ wz
x
x
w
P3 = P4 /wz
w
K2 + K1 = P3 \ yw
Figura 6.1: Grafos C4 , P4 , K3 , 2K2 , P3 e K2 + K1 .
1.
f (C4 ; λ) = f (G \ xy; λ) − f (G/xy; λ)
= f (P4 ; λ) − f (K3 ; λ)
= f (P4 \ wz; λ) − f (P4 /wz) − f (K3 ; λ)
= f (2K2 ; λ) − f (P3 ; λ) − f (K3 ; λ)
= f (2K2 ; λ) − (f (P3 \ yw; λ) − f (P3 /yw; λ)) − f (K3 ; λ)
= f (2K2 ; λ) − f (K2 + K1 ; λ) + f (K2 ; λ) − f (K3 ; λ)
= (f (K2 ; λ))2 − f (K2 ; λ)f (K1 ; λ) + f (K2 ; λ) − f (K3 ; λ)
=
=
(λ(λ − 1))2 − λ(λ − 1)λ + λ(λ − 1) − λ(λ − 1)(λ − 2)
λ4 − 4λ3 + 6λ2 − 3λ.
Polinómios cromáticos
81
y
y
x
z
x
z
w
C4 = G \ yw
w
G = K4 \ xz
y
y
x
z
w
K4
x
y
x
P3 = G/yw
y
x
w
K3 = K4 /xz
z
K2 = K3 /xz
Figura 6.2: Grafos C4 , K4 \ xz, P3 , K4 , K3 e K2 .
2.
f (G \ yw; λ) =
=
=
=
=
=
f (G; λ) + f (G/yw; λ)
f (K4 \ xz; λ) + f (P3 ; λ)
f (K4 ; λ) + f (K4 /xz; λ) + f (K3 \ xz; λ)
f (K4 ; λ) + f (K3 ; λ) + f (K3 ; λ) + f (K3 /xz; λ)
f (K4 ; λ) + 2f (K3 ; λ) + f (K2 ; λ)
λ4 − 4λ3 + 6λ2 − 3λ.
Note-se que a função f (C4 ; λ), anteriormente calculada, é um polinómio
mónico com coeficientes inteiros de grau 4, no qual o coeficiente de λ3 é −m =
−4, o termo constante é nulo e os coeficientes alternam em sinal. O teorema a
seguir estabelece que estas características não são coincidência.
Theorem 6.1.2. Para um grafo simples G de ordem n e dimensão m, f (G; λ) é
um polinómio mónico de grau n em λ com coeficientes inteiros e termo constante
nulo. Adicionalmente, cada coeficiente alterna em sinal e o coeficiente de λn−1
é −m.
Demonstração. Vamos fazer a prova por indução sobre o número de arestas m, tendo
em conta que para m = 0 o resultado é trivialmente verdadeiro (F (Knc ; λ) = λn ).
Suponhamos que o resultado é verdadeiro para grafos com menos do que m arestas,
com m ≥ 1 e seja G um grafo de ordem n, dimensão m e e ∈ E(G). Então,
f (G \ e; λ)
=
λn − a1 λn−1 + a2 λn−2 + · · · + (−1)n−1 an−1 λ
f (G/e; λ)
=
λn−1 − b1 λn−1−1 + b2 λn−1−2 + · · · + (−1)n−2 bn−2 λ
82
Resultados Algébricos Associados a Grafos
onde a1 , . . . , an−1 e b1 , . . . , bn−2 são inteiros não negativos cujos coeficientes alternam
em sinal, a1 = m − 1 e b1 = m − 1. Dado que F (G; λ) = f (G \ e; λ) − f (G/e; λ), vem
que
f (G; λ) = λn − (a1 + 1)λn−1 + (a2 + b1 )λn−2 − · · · + (−1)n−1 (an−1 + bn−2 )λ.
Tendo em conta que a1 + 1 = m, podemos concluir que f (G; λ) tem todas as propriedades pretendidas.
Theorem 6.1.3. Um grafo G é uma árvore de ordem n se e só se f (G; λ) =
λ(λ − 1)n−1 .
Demonstração. Vamos fazer a prova da implicação se G é uma árvore então f (G; λ) =
λ(λ − 1)n−1 , por indução sobre n, tendo em conta que para n = 1 o resultado é trivialmente verdadeiro. Suponha-se que o resultado é verdadeiro para árvores com menos
do que n vértices e que n ≥ 2. Seja G uma árvore de ordem n e seja e ∈ E(G) uma
aresta pendente. Então, f (G; λ) = f (G \ e; λ) − f (G/e; λ) e G \ e é uma floresta com
duas componentes, uma de ordem 1 e outra de ordem n − 1. Logo, f (G \ e; λ) =
λ(λ(λ − 1)n−2 ) = λ2 (λ − 1)n−2 e, consequentemente,
f (G; λ)
=
λ2 (λ − 1)n−2 − λ(λ − 1)n−2
=
(λ2 − λ)(λ − 1)n−2
=
λ(λ − 1)n−1 .
Reciprocamente, suponha-se que G é um grafo simples tal que f (G; λ) = λ(λ − 1)n−1 .
Então,
f (G; λ) = λn − (n − 1)λn−1 + · · · + (−1)n−1 λ
e, consequentemente, G tem n vértices e n − 1 arestas. Adicionalmente, o último
termo, (−1)n−1 λ, assegura que G é conexo (caso contrário, o polinómio de qualquer
componente dividia f (G; λ)). Logo, G é uma árvore.
Este teorema tem como consequência imediata que existem grafos não isomorfos com o mesmo polinómio cromático. Por exemplo, K1,3 e P4 não são
isomorfos e têm o mesmo polinómio cromático λ(λ − 1)3 (logo, o número de
colorações dos vértice, com λ cores, é igual).
6.2
Espectros de grafos
Quando falamos de espectros de grafos em geral falamos de valores próprios
das matrizes de adjacência as quais, sendo simétricas com a mesma ordem n
dos grafos, têm n valores próprios reais, contando eventuais repetições. Por
outro, uma vez que as entradas da diagonal principal destas matrizes são nulas
e, consequentemente, os respectivos traços são nulos, podemos concluir que a
soma dos valores próprios é também nula. Por exemplo, dado que a matriz de
adjacência de um grafo completo de ordem n, Kn , é AKn = J − I, onde J é
uma matriz de ordem n, com entradas todas iguais a 1, podemos concluir que
os Kn tem um valor próprio igual a n − 1 e os restantes iguais a −1. Com efeito,
dado que J ê = nê e J(ê1 − êj ) = 0, para j = 2, . . . , n, concluímos o conjunto
de vectores linearmente independentes {ê, ê1 − ê2 , . . . , ê1 − ên } é um conjunto
Espectros de grafos
83
de n vectores próprios, logo os valores próprios que lhe correspondem são o
valores próprios de J, logos subtraindo uma unidade a cada um deles obtêm-se
os valores próprios de Kn .
Dado um grafo G de ordem n, uma vez que AG é simétrica, podemos concluir
que AG tem n valores próprios reais. Por outro lado, dado que todas as entradas
ao longo da diagonal principal são nulas, o seu traço é também nulo. De agora
em diante, para um grafo G arbitrário, vamos considerar o valores próprios de
G segundo a ordem
λmin (AG ) = λ1 ≤ λ2 ≤ · · · ≤ λn−1 ≤ λn = λmax (AG ).
6.2.1
Algumas propriedades dos valores próprios da matriz de adjacência de um grafo
Se G tem pelo menos uma aresta, então λmin (AG ) ≤ −1, onde λmin (AG ) denota
o menor valor próprio de AG . Se N é um grafo nulo, isto é, sem arestas, então
∀λ ∈ σ(AN ) λ = 0, onde σ(AN ) denota o espectro de AN , ou seja, o conjunto
dos seus valores próprios.
Considerando o grafo completo de ordem n, Kn , e denotando o seu polinómio
característico (ou seja, o polinómio característico da sua matriz de adjacência)
por p(AKn , λ), vem que

p(Kn , λ) = det(AKn
−λ 1
 1 −λ
− λI) = det( 
..
 ...
.
1
1
···
···
..
.
...

1
1 
).
.. 
. 
−λ
Logo, é claro que −1 ∈ σ(AKn ). Por outro lado, AKn ê = (n − 1)ê, onde ê
denota o vector de componentes unitárias, pelo que n − 1 ∈ σ(AKn ). Com
facilidade se conclui que os n − 1 vectores, ê1 − ê2 , ê1 − ê3 , . . . , ê1 − ên , são
vectores próprios de AKn associados ao valor próprio −1, pelo que podemos
concluir que o subespaço invariante associado ao valor próprio −1 tem dimensão
n − 1 e, consequentemente, este valor próprio tem multiplicidade n − 1. Assim,
podemos concluir que Kn tem apenas dois valores próprios distintos (n − 1) com
multiplicidade 1 e −1 com multiplicidade n − 1.
Theorem 6.2.1 (do entrelaçamento). Seja A uma matriz simétrica real com
valores próprios λ1 ≥ λ2 ≥ . . . ≥ λn e sejam µ1 ≥ µ2 ≥ . . . ≥ µn−1 os valores
próprios de uma submatriz principal de A. Então
λi ≥ µi ≥ λi+1 , para i = 1, . . . , n − 1.
Como consequência imediata deste teorema, denotando por λmin (C) e λmax (C)
os valores próprios mínimos e máximos da matriz C, respectivamente, podemos
concluir que, sendo H um subgrafo induzido G, vem que
λmin (AG ) ≤ λmin (AH ) ≤ . . . ≤ λmax (AH ) ≤ λmax (AG ).
84
Resultados Algébricos Associados a Grafos
Assim, supondo que G tem pelo menos uma aresta, ou seja, contém K2 como
subgrafo induzido, vem que
λmin (AG ) ≤ −1 = λmin (AK2 ) ≤ λmax (AK2 ) = 1 ≤ λmax (AG ).
Adicionalmente, se G contém K1,2 como subgrafo induzido, uma vez que


−λ 1
1
p(K1,2 , λ) = det  1 −λ 0  = λ(−λ2 + 2)
1
0 −λ
√
√
e, consequentemente, σ(AK1,2 ) = {− 2, 0, 2}, podemos concluir que
√
√
λmin (AG ) ≤ − 2 ≤ 2 ≤ λmax (AG ).
Theorem 6.2.2. Dado um grafo G, supondo que existem dois vértices x, y ∈
V (G) tais que NG (x) \ {y} = NG (y) \ {x}, podemos concluir o seguinte:
1. Se xy ∈ E(G), então −1 ∈ σ(AG );
2. Se xy ∈
/ E(G), então 0 ∈ σ(AG ).
Demonstração. Suponha-se, sem perda de generalidade, que x = v1 , y = v2 e
NG (x) \ {y} = {v1 , . . . , vk }, então
AG − λI =
v1
v2
v3
..
.
vk
vk+1
..
.
vn
v1
−λ
 z

 1
 .
 .
 .

 1

 0

 .
 ..
0

v2
z
−λ
1
..
.
1
0
..
.
0
v3
1
1
−λ
..
.
...
...
...
...
..
.
..
.
..
.
vk
1
1
vk+1
0
0
..
.
−λ
..
.
...
...
...
...
..
.
−λ
..
.
..
.
..
.
vn

0
0 


.. 

. 
.




.. 
. 
−λ
Assim, podemos tirar as seguintes conclusões:
1. Se xy ∈ E(G), então z = 1 e, consequentemente, para λ = −1, as duas primeiras
linhas de AG − λI, são iguais. Logo, det(AG + I) = 0, pelo que −1 ∈ σ(AG ).
2. Se xy ∈
/ E(G), então z = 0 e, consequentemente, para λ = 0, as duas primeiras
linhas de AG − λI, são iguais. Logo, det(AG ) = 0, pelo que 0 ∈ σ(AG ).
Como corolário deste teorema, para os grafos bipartidos completos Kp,q ,
vem que −1 ∈ σ(AKp,q ). Por outro lado, dado um grafo G, se existem dois
vértices x, y ∈ V (G) tais que NG (x) = NG (y), sendo û um vector próprio de
AG , associado a um valor próprio λ, vem que
X
X
λûx = (AG û)x =
ûj =
ûi = (AG û)y = λûy .
j∈NG (x)
i∈NG (y)
Espectros de grafos
85
Logo, λ(ûx − ûy ) = 0, pelo que λ 6= 0 ⇒ ûx = ûy .
Voltando aos grafos bipartidos completos, podemos concluir o resultado a
seguir.
√
√
Theorem 6.2.3. σ(AKp,q ) = {− pq, 0, pq}.
Demonstração. Dado que a matriz de adjacência de Kp,q tem característica 2, podemos concluir que existem apenas dois valores próprios não nulos de sinais contrários,
λ1 e λn , tais que λ1 = −λn , com n = p + q. Adicionalmente, qualquer vector próprio
û, associado a um valor próprio não nulo λ, é tal que para todo o índice i, ûi ∈ {y, z}.
Como consequência, vem que λy = qz e λz = py, donde λ2 zy = (pq)zy ⇒ λ2 = pq.
Sendo G um grafo com pelo menos uma aresta, dado um vector próprio u
de norma unitária de AG , associado ao maior valor próprio λn , e sendo ui a
componente de u de maior valor absoluto, vem que
(AG u)i =
X
uj
⇔ λn ui =
j∈NG (i)
X
⇔
X
λn =
j∈NG (i)
logo,
λn ≤
X
|
j∈NG (i)
uj
j∈NG (i)
uj
,
ui
uj
| ≤ |NG (i)| ≤ ∆(G).
ui
É fácil concluir que se o grafo G tem uma componente ∆(G)-regular, então
λmax (AG ) = ∆(G) e a sua multiplicidade é igual ao número de componentes
∆(G)-regulares.
6.2.2
Algumas propriedades dos vectores próprios da matriz de adjacência de um grafo *
Seja G um grafo e U a matriz unitária cujas colunas são os vectores próprios
ortonormais de AG , ordenados de forma adequada, nestas condições vem que
U T AG U = Λ, onde Λ = diag(λ1 , . . . , λn ). Assumindo que valores próprios repetidos ocorrem consecutivamente ao longo da diagonal principal de Λ e denotando
por ki = dim ²(λi ), para i = 1, . . . , m, onde m denota o número de valores próprios distintos e ε(λi ) denota o subespaço invariante associado ao valor próprio
λi . Logo, fazendo
U T AG U = λ1 E1 + . . . + λm Em ,
onde



E1 = 

Ik1
0
.
..
0
0
0
.
..
0
···
···
.
..
···
0
0
.
..
0


0

 0


 , E2 =  .

 ..
0
0
Ik2
.
..
0
···
···
.
..
···
0
0
.
..
0


0

 0


 , . . . , Em =  .

 ..
0
0
0
.
..
0
···
···
.
..
···
0
0
.
..
Ikm



.

86
Resultados Algébricos Associados a Grafos
Nestas condições vem que
AG
= λ1 U E 1 U T + λ2 U E 2 + · · · + λm U E m U T
= λ1 P1 + λ2 P2 + · · · + λm Pm ,
com Pi = U Ei U T , para i = 1, . . . , m. Note-se que Pi Pj = 0, se i 6= j e Pi2 =
Pi = PiT e Pi AG = AG Pi , para cada i. Consequentemente, vem que
AkG = λk1 P1 + · · · + λkm Pm .
Por outro lado, Pi é a projecção ortogonal de Rn no subespaço invariante ε(λi ),
para i = 1, . . . , m. As projecções dos vectores da base canónica êj em ε(λi ),
Pi ê1 , . . . Pi ên , constituem o que alguns autores designam por eutatic star em
ε(λi ).
É possível determinar uma partição do conjunto {1, . . . , n} nos subconjuntos X1 , . . . , Xm tais que os conjuntos de vectores {P êj : j ∈ Xi } constitui uma
base para ε(λi ). Esta partiçãoSde signa-se por partição estrela de G nas célum
las X1 , . . . , Xm . Prova-se que i=1 {Pi êj : j ∈ Xi } é uma base para Rn que se
designa por base estrela.
Theorem 6.2.4. As seguintes afirmações são equivalentes para cada i.
1. {Pi êj : j ∈ Xi } é uma base para ε(λi );
/ Xi i;
2. Rn = ε(λi ) ⊕ hêj : j ∈
3. |Xi | = ki e λi não é valor próprio de G \ Xi .
6.3
Grafos fortemente regulares
O conceito de grafo fortemente regular é um conceito relativamente recente,
introduzido em 1963 por R. C. Bose em [8]. Um grafo não nulo nem completo
diz-se fortemente regular com parâmetros (n, p; a, c) se tem ordem n, é p-regular
e todo o par de vértices adjacentes tem a vizinhos em comum e todo o par de
vértices não adjacentes tem c vizinhos em comum.
Uma geometria parcial pg(K,R,T) é uma estrutura de incidência de pontos e
rectas com as seguintes propriedades:
1. toda a recta tem K pontos e todo o ponto pertence a R rectas;
2. quaisquer dois pontos pertencem a no máximo uma recta;
3. se um ponto p não pertence a uma recta L, então existem exactamente T
rectas que contêm p e encontram L.
Se dois pontos x e y pertencem a uma recta, diz-se que são colineares e escreve-se x ∼ y. O grafo dos pontos de uma geometria parcial é um grafo onde os
pontos da geometria parcial são os vértices e dois vértices x e y são adjacentes
Grafos fortemente regulares
87
se e somente se x ∼ y. O grafo dos pontos de uma geometria parcial pg(K,R,T)
é um grafo fortemente regular com parâmetros (n,p,a,c) tais que
(K − 1)(R − 1)
),
T
p = R(K − 1),
a = (K − 2) + (R − 1)(T − 1),
c = RT.
n
6.3.1
= K(1 +
Resultados fundamentais
Um exemplo simples de um grafo fortemente regular é C5 que é um grafo fortemente regular com parâmetros (5, 2, 0, 1).
4
5
3
1
2
Figura 6.3: Grafo fortemente regular com parâmetros (5, 2, 0, 1).
Lema 6.3.1. Se G é um grafo fortemente regular com parâmetros (n, p, a, c)
onde c > 0 então diam(G) = 2.
Demonstração. Com efeito, dados dois vértices não adjacentes x, y ∈ V (G), sabe-se
que |NG (x) ∩ NG (y)| = c > 0 e, consequentemente, dG (x, y) = 2.
Também se mostra, facilmente, que se G é um grafo fortemente regular com
parâmetros (n, p, a, c) então o seu complementar é também fortemente regular
com parâmetros (n, p̄, ā, c̄) tais que
p̄ =
ā =
c̄ =
n − p − 1,
n − 2 − 2p + c,
n − 2p + a.
(6.1)
(6.2)
(6.3)
Os parâmetros dos grafos fortemente regulares não são independentes. Podemos
contar o número total de arestas entre vértices adjacentes e não adjacentes a um
vértice fixo, u, de um grafo fortemente regular G de parâmetros (n, p, a, c) de
duas maneiras diferentes. Cada um dos p vizinhos do vértice é adjacente a u, a a
vizinhos de u e, consequentemente, a p − a − 1 vértices não adjacentes a u, num
total de p(p − a − 1) arestas. Por outro lado, cada um dos n − p − 1 vértices não
adjacentes a u é adjacente a c vizinhos de u num total de (n − p − 1)c arestas.
Consequentemente,
88
Resultados Algébricos Associados a Grafos
p(p − a − 1)
=
(n − p − 1)c.
(6.4)
Logo, se G é um grafo fortemente regular com parâmetros (n, p, a, c), então a igualdade (6.4) verifica-se. Esta igualdade é conhecida por igualdade de
admissibilidade de grafos fortemente regulares.
Um grafo fortemente regular G diz-se primitivo se tanto G como o seu complementar Ḡ são conexos e diz-se imprimitivo no caso contrário.
Lema 6.3.2 ([12], pag. 178). Um grafo fortemente regular com parâmetros
(n, p, a, c) é imprimitivo sse c = p ou c = 0.
Demonstração. Suponha que G é um grafo fortemente regular com parâmetros
(n, p, a, c). Então G é conexo sse c > 0 e Ḡ é conexo sse c̄ > 0. Logo, basta mostrar
que Ḡ é desconexo se p = c. Tendo em conta a igualdade (6.4), se p = c então
p − a − 1 = n − p − 1 ⇔ a = 2p − n.
Consequentemente, de acordo com (6.1)-(6.3), vem que c̄ = n − 2p + (2p − n) = 0.
Na figura a seguir representam-se dois grafos fortemente regulares imprimitivos.
1
6
2
1
3
2
5
4
6
5
3
4
Figura 6.4: Grafos fortemente regulares com parâmetros (6, 4, 2, 4) e (6, 2, 1, 0).
Lema 6.3.3 ([12], pag. 178). Se G é um grafo fortemente regular com parâmetros (n, p, a, c) e tal que n = q + 1, onde q é primo, então G é imprimitivo.
Demonstração. A partir de (6.4) vem que
p(p − 1 − a) = (q − p)c.
Tendo em conta que 1 < p < q, vem que p e q − p são primos relativos, pelo que p
divide c. Dado que c ≤ p, tal implica c = p ou c = 0, donde G é imprimitivo.
Considere o grafo fortemente regular com parâmetros (n, p, a, c). A entrada
uv de A2G corresponde ao número de passeios de comprimento 2 entre os vértices u e v. Em grafos fortemente regulares este número é determinado apenas
pelo facto de u e v serem o mesmo vértice ou vértices distintos adjacentes ou
não adjacentes. Consequentemente, obtém-se a seguinte condição necessária e
suficiente:
Grafos fortemente regulares
89
Theorem 6.3.4. Um grafo não nulo nem completo G é fortemente regular com
parâmetros (n, p, a, c) sse AG J = pJ e A2G + (c − a)AG + (c − p)I = cJ, onde I
e J, denotam, respectivamente, a matriz identidade e a matriz quadrada cujas
entradas são todas unitárias.
Demonstração. A entrada ij da matriz A2G é igual ao número de passeios de comprimento 2 entre i e j. Logo, se G é fortemente regular com parâmetros (n, p, a, c),
vem que AJ = pJ e
A2G = pI + aAG + c(J − I − AG )
⇔
A2G − (a − c)AG − (p − c)I = cJ. (6.5)
O recíproco decorre imediatamente da definição de grafo fortemente regular.
6.3.2
Espectros de grafos fortemente regulares
Sendo G um grafo fotemente regular com parâmetros (n, p, a, c), G é p-regular
e então p é um valor próprio cujo vector próprio associado é o vector ê de componentes todas iguais a 1. Por outro lado, sabe-se que qualquer vector próprio
associado a um valor próprio distinto de p é ortogonal a ê. Se û é um vector
próprio associado a λ 6= p então, de acordo com (6.5),
A2G û − (a − c)AG û − (p − c)û =
cJ û = 0̂
(6.6)
e, consequentemente,
λ2 − (a − c)λ − (p − c)
= 0.
(6.7)
Conclui-se assim que os valores próprios de AG distintos de p são raízes do
polinómio quadrático x2 − (a − c)x − (p − c). Fazendo ∆ = (a − c)2 + 4(p − c),
obtém-se
λ
=
(a − c) ±
2
√
∆
.
(6.8)
Os valores próprios do grafo fortemente regular G distintos de p designam-se
por valores próprios restritos e denotam-se (neste texto) por λ1 e λ2 . Note-se
que λ1 = λ2 implica ∆ = 0, o que, por sua vez, é equivalente a a = c e p = c.
Assim, podemos concluir que se G é primitivo, então os valores próprios restritos
são distintos. Adicionalmente, conclui-se, ainda, que
λ1 λ2
λ1 + λ2
= (c − p)
(6.9)
= (a − c).
(6.10)
As equações (6.9)-(6.10) decorrem directamente de (6.7). Por outro lado,
tendo em conta (6.9), se c < p então λ1 e λ2 têm sinais contrários e 0 6∈ σ(AG ).
Por outro lado, se c = p (como acontece em certos grafos imprimitivos) então
podemos concluir que 0 ∈ σ(AG ).
90
Resultados Algébricos Associados a Grafos
As multiplicidades dos valores próprios λ1 e λ2 , m(λ1 ) e m(λ2 ), também
se podem determinar a partir dos parâmetros do grafo fortemente regular que
lhes corresponde. Com efeito, tendo em conta que quando o grafo é conexo e
p-regular, a multiplicidade do valor próprio p é 1, podemos concluir que, no caso
de grafos fortemente regulares primitivos, m(λ1 ) e m(λ2 ) satisfazem o sistema
de equações:
m(λ1 ) + m(λ2 ) =
λ1 m(λ1 ) + λ2 m(λ2 ) =
n−1
−p.
(6.11)
(6.12)
Admitindo λ1 6= λ2 e resolvendo o sistema (6.11)-(6.12), conclui-se que
1
2p + (n − 1)(a − c)
((n − 1) −
)
(6.13)
2
λ1 − λ2
2p + (n − 1)(a − c)
1
m(λ2 ) =
((n − 1) +
).
(6.14)
2
λ1 − λ2
Como exemplo, considerando o grafo fortemente regular com parâmetros
(50, 7, 0, 1) obtêm-se os valores próprios λ1 = 2 e λ2 = −3 com multiplicidades
m(λ1 ) = 28 e m(λ2 ) = 21, respectivamente.
m(λ1 ) =
Note-se que no caso da solução do sistema (6.11)-(6.12) não ser inteira, tal
implica a impossibilidade de existência de um grafo fortemente regular com os
parâmetros em causa.
Lema 6.3.5. Seja G um grafo fortemente regular com parâmetros (n, p, a, c) e
com valores próprios restritos λ1 e λ2 . Se m(λ1 ) = m(λ2 ), então n = 2p + 1.
Demonstração. Suponha-se que m(λ1 ) = m(λ2 ). Então (c − a)(n − 1) = 2p o que
só é possível se c − a = 1 e, consequentemente, n = 2p + 1.
Os grafos fortemente regulares com valores próprios restritos λ1 e λ2 para os
quais se verifica a igualdade m(λ1 ) = m(λ2 ), designam-se por conference graphs.
Lema 6.3.6 ([13], pag. 220). Se G é um grafo regular conexo com exactamente
três valores próprios distintos, então é um grafo fortemente regular.
Demonstração. Suponha-se que G é um grafo p-regular conexo com valores próprios
distintos p, λ1 e λ2 . Então a matriz polinomial
1
M=
(AG − λ1 I)(AG − λ2 I)
(p − λ1 )(p − λ2 )
tem como valores próprios distintos 0 e 1. Por outro lado, qualquer vector próprio
de AG com valor próprio λ1 ou λ2 pertence ao núcleo de M . Consequentemente, a
característica de M é igual à multiplicidade de 1 como valor próprio. Dado que G é
conexo, esta multiplicidade é 1 e M ê = ê, o que implica que se tenha M = n1 J. Logo,
J é combinação linear de AG , A2G e I o que prova, de acordo com o Teorema 6.3.4,
que G é fortemente regular.
É claro que o recíproco deste teorema (para grafos fortemente regulares
primitivos) também é verdadeiro. Assim, se G é um grafo fortemente regular
primitivo, então G é conexo, regular e tem três valores próprios distintos.
6.4. EXERCÍCIOS
6.4
91
Exercícios
6.4.1. Prove que se G tem k componentes, então λk é um factor de f (G; λ).
6.4.2. Considere o grafo H representado na figura a seguir.
f
a
c
b
d
H
(a) Determine o polinómio cromático do grafo H representado na figura.
(b) Determine o número de colorações distintas dos vértices de H que é
possível realizar com 3 cores.
92
Resultados Algébricos Associados a Grafos
Bibliografia
[1] Amitsur, S.A. and Levitzki, J., Minimal identities for algebras, Proc. Amer.
Math. Soc., 1 (1950): 449ŋ463.
[2] Armstrong, M.A., Basic Topology, Springer (5ł edição), New York (1997).
[3] Berge, C., Graphs, NorthŋHolland (3th edition), Amsterdam (1991).
[4] Beineke, L.W., Topology, in Graph Conections: Relationships between Graph
Theory and others Areas of Mathematics (Beineke, L.W. et al, ed.), Claredon
Press, Oxford (1997): 155ŋ175.
[5] Biggs, N.L., Loyd, E.K. and Wilson, R.J., Graph Theory, Claredon Press
(1986): 1736ŋ1936.
[6] Birkhoff, G. and Lewis, D., Chromatic polynomials, Trans. Amer. Math. Soc.
60 (1946): 355-451.
[7] Bollobás, B, Graph Theory: An Introductory Course, Springer, New York
(1979).
[8] Bose, R.C. Strongly regular graphs, partial geometries and partially ballanced
designs, Pacific J. Math. 13 (1963): 389-419.
[9] Cardoso, D. M. Convex Quadratic Programming Approach to the Maximum
Matching Problem, Journal of Global Optimization 21 (2001): 91-106.
[10] Cardoso, D. M. On graphs with stability number equal to the optimal value of a convex quadratic program, Matemática Contemporânea (Sociedade
Brasileira de Matemática) 21 (2003): 9-24.
[11] Diestel, R., Graph Theory, Springer, New York (1997).
[12] Godsil, C. D. Algebraic Combinatorics. Chapman & Hall Mathematics Series, New York (1993).
[13] Godsil, C. D. and Royle, G. Algebraic Graph Theory. Springer-Verlag, New
York (2001).
[14] Farmer, D.W. and Stanford, T.B., Knots and Surfaces: A Guide to Discovering Mathematics, American Mathematical Society, Providence (1996).
93
94
Bibliografia
[15] Graham, R.L., Grotshel, M. and Lovász (ed.), Handbook of Combinatorics,
vol I, NorthŋHolland, Amsterdam (1995).
[16] Harary, F., Graph Theory, AddisonŋWesley, Reading (1969).
[17] Harary, F. and NashŋWilliams, C.J.A., On Eulerian and Hamiltonian
graphs and line graphs, Canad. Math. Bull., 8 (1965): 701ŋ710.
[18] Kuratowski, K., Sur le problème des courbes en topologie, Fund. Math., 15
(1930): 271ŋ283; English translation by J. Jaworowski in Graph Theory, Lagow 1981 (Borowiecki, M. et al, ed.), Lecture Notes in Math. 1018, Springer
(1983): 1ŋ13.
[19] Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G. and Shmoys D.B. (ed.),
The Traveling Salesmaan Problem: A Guided Tour of Combinatorial Optimization, John Wiley & Sons, Chichester (1995).
[20] Little, J.D.C., Murty, K.G., Sweenyey, D.W. and Karel, C., An Algorithm for the Traveling Salesman Problem, Operations Research, 11 (1963):
972ŋ989.
[21] Lovasz, L., Combinatorial Problems and Exercises, North Holland, Amsterdam (1979).
[22] Luz, C. J., An upper bound on the independence number of a graph computable in polynomial time, Operations Research Letters 18 (1995): 139-145.
[23] Motzkin, T. S., and Straus E. G., Maxima for graphs and a new proof of a
theorem of Túran, Canadian Journal of Mathematics, 17 (1965): 533-540.
[24] Parathasarathy, K.R., Basic Graph Theory, McGrawŋHill, New Delhi
(1994).
[25] Pelillo, M., Jagota, J. Feasible and infeasible maxima in quadratic programming for maximum clique, Journal of Artif. Neural Networks, 2 (1995):
411-420.
[26] Peressini, A. L., Sullivan, A. L., and Uhl-Jr, J. J. The Mathematics of
Nonlinear Programming, Springer, New York, 1993.
[27] Ringel, G. and Youngs, J.W.T., Solution of the Heawood mapŋcoloring problem, Proc. Nat. Acad. Sci. USA, 60 (1968): 438ŋ445.
[28] Shor, N. Z. Dual quadratic estimatesin polynomial and Boolean programming, in Computational methods in Global Optimization (P. M. Pardalos
and J. B. Rosen, Eds.), Ann. Oper. Res. 25 (1990): 163-168.
[29] Trudeau, R.J., Introduction to Graph Theory, Dover Publications, Inc., New
York (1993).
Bibliografia
95
[30] Wilson, R.J., Introduction to Graph Theory, Oliver and Boyd, Edinburgh
(1972).
[31] Whitney, H., Non-separable and planar graphs, Trans. Amer. Math. Soc.,
34 (1932): 339ŋ362.
[32] Whitney, H., Planar graphs, und. Math. 21 (1933): 73-84.