Elementos de Matemática Finita
Exercı́cios Resolvidos
Ficha 9 - 12.* - Um vértice v de um grafo chama-se um corte se G \ v tem
mais componentes conexas que G. Um grafo (com mais do que um vértice) é
um bloco se é conexo e não tem cortes.
Mostrar que as seguintes propriedades sobre um grafo G com mais do que dois
vértices e sem vértices isolados são equivalentes:
1- G é um bloco;
2- quaisquer dois vértices de G estão em algum ciclo de G;
3- todos os vértice v e aresta a fazem parte de um ciclo de G;
4- quaisquer duas arestas de G estão em algum ciclo de G.
Nota: a condição de G ter pelo menos três vértices é necessária porque o
grafo completo em dois vértices é um bloco mas não satisfaz nem 2 nem 3. Por
outro lado, a condição de não existirem vértices isolados é necessãria porque um
grafo sem arestas satisfaz 3 e 4 trivialmente mas não é um bloco.
Provam-se as implicações 1 ⇒ 2 ⇒ 3 ⇒ 4 ⇒ 1.
1 ⇒ 2: suponhamos que G é um bloco. Dados vértices u e v temos que mostrar
que existe um ciclo que os contém.
Para acompanhar o raciocı́ni oé útil fazer um diagrama esquemático da situação.
Seja X o conjunto dos vértices que estão num ciclo com u. X não é vazio: notese que u tem pelo menos dois vértices adjacentes u1 e u2 (se u tivesse um único
vértice adjacente, este seria um corte em G); como u não é corte, G \ u é conexo
e existe um caminho unindo u1 a u2 ; este caminho juntamente com as arestas
uu1 e uu2 constitui um ciclo contendo estes três vértices. Mais geralmente,
qualquer vértice adjacente a u pertence a X. Vamos supôr que v não pertence
a X e chegar a uma contradição.
Seja z um vértice de X à distância mı́nima de v e C0 um caminho de z a v de
comprimento mı́nimo. Existem dois caminhos C1 e C2 unindo u a z, disjuntos
à excepção dos extremos. Como z não pode ser um corte, existe em G \ z um
caminho Q com inı́cio em u e fim em v. Seja x a última intersecção de Q com
C1 ∪ C2 (quando percorremos o caminho Q de u para v), que supômos pertencer
por exemplo a C1 ; e seja y a primeira intersecção de Q com o caminho C0 .
Note-se agora que seguindo C1 de u até x, depois Q de x até y, depois C0 de y
1
até z, e finalmente C2 de z até u, temos um ciclo; logo y ∈ X e está mais perto
de v que z, uma contradição.
2 ⇒ 3: seja v um vértice e a uma aresta de extremos x e y; se v = x (
ou v = y), como 2 implica que x e y estão num ciclo, temos que v e a estão
num ciclo, portanto podemos supôr que a aresta a não incide em v. A condição
2 implica que v e x estão num ciclo, ou seja, existem dois caminhos C1 e C2
unindo v a x, disjuntos à excepção dos extremos. Por outro lado, como também
v e y estão em algum ciclo, existe um caminho Q com inı́cio em v e fim em y
que não passa por x (caso contrário, não poderiam existir caminhos disjuntos
unindo v a y). Seja z o último vértice de Q que pertence também a C1 ∪ C2
e que supômos estar por exemplo em C1 . O caminho que consiste na união de
C2 com a aresta a, com a parte do caminho Q entre y e z e com a parte de C1
entre v e z é um ciclo nas condições pretendidas.
A implicação 3 ⇒ 4 pode provar-se de modo semelhante. Quanto a 4 ⇒ 1,
notamos em primeiro lugar que como não há vértices isolados a condição 4
implica que G é conexo. Seja u um vértice e mostremos que, na condição de
G satisfazer 4, G \ u é conexo: dados dois vértices x e y e duas arestas a e
b incidentes em x e y respectivamente, sabemos que existe um ciclo contendo
estas arestas; pelo menos um dos caminhos unindo x a y nesse ciclo não contém
u; portanto existe um caminho entre x e y em G \ u.
Ficha 9 - 13. - O diâmetro de um grafo conexo G é o máximo D(G) das
distâncias entre dois vértices. Dado um grafo conexo de diâmetro D e grau
máximo ∆,
a) Fixando um vértice v0 , provar que o número de vértices à distância k de
v0 é menor ou igual a ∆(∆ − 1)k−1 ;
b) Concluir que o número total de vértices de G é menor ou igual a
1+∆
(∆ − 1)D − 1
∆−2
A alı́nea a) é imediata: existem no máximo ∆vértices à distâcia 1 de v0 ; cada
um deles tem no máximo ∆ − 1 outros vértices adjacentes que estão à distância
2 de v0 e assim por diante.
b) decorre de notar que contando os vértices de acordo com a distância a v0 , o
seu número total é menor ou igual a
1 + ∆ + ∆(∆ − 1) + · · · + ∆(∆ − 1)
D−1
∑
(∆ − 1)k =
(1)
(∆ − 1)D − 1
1 − (∆ − 1)D
=1+∆
1 − (∆ − 1)
∆−2
(2)
D−1
=1+∆
k=0
=1+∆
2
Ficha 10 - 6. - Dado um grafo conexo G e um vértice v0 , mostrar que
existe uma árvore geradora T , tal que, para todo o vértice v, a distância entre
v0 e v em T é igual à distância entre v0 e v em G.
Construı́mos uma árvore geradora T com o algoritmo ganancioso, usando o
vértice v0 como raiz e fazendo a busca em largura.
Podemos raciocinar por indução: todas as arestas incidentes em v0 são incluı́das
na árvore e portanto os vértices que estão à distância 1 de v0 em G, ficam à
mesma distância em T (e são os únicos nessa situação); em seguida o algoritmo
procura os vértices adjacentes a estes que ainda não estejam em T e assim por
diante; suponhamos que os vértices à distância k de v0 em G são exactamente
os que ficam à mesma distância em T e seja v um vértice à distância k + 1 de
v0 ; v não pode ser incluı́do em T antes do algoritmo fazer a busca nos vértices
adjacentes aos que estão à distância k de v0 ; mas v ’e adjacente a algum destes
e vai portanto ser incluı́do em T nesse passo do algoritmo.
Ficha 10 - 12. - Seja F uma floresta. Constrói-se um novo grafo G acrescentando um novo vértice x e uma aresta a ligar x a cada vértice de F de grau
ı́mpar. Mostrar que G é aleatoriamente Euleriano.
Recorde-se que um grafo G é aleatoriamente Euleriano para um vértice x
se todos os caminhos maximais com inı́cio em x são ciclos Eulerianos do grafo.
Como se deduziu na aula, um grafo G é aleatoriamente Euleriano para x se e s
se G é Euleriano (ou seja é conexo e todos os vértices têm grau par) e x pertence
a todos os ciclos do grafo.
O grafo G contruı́do no enunciado é sem dúvida conexo. Além disso todos os
vértices têm grau par: os vértices que tinham grau ı́mpar em F passaram a ter
grau par, enquanto que os tinham grau par mantêm o mesmo grau. Quanto ao
novo vértice x, o seu grau é igual ao número de vértices de grau ı́mpar em F ,
que é par pelo primeiro Teorema dos Grafos. Portanto G é Euleriano. Além
disso, todos os ciclos de G contêm arestas incidentes em x pois F nã tinha ciclos.
Ficha 11 - 5. - Uma coloração de um grafo determina uma partição de
qualquer subconjunto S dos vértices. Dado um conjunto S, definir um grafo G
com conjunto de vértices V , com S ⊂ V , tal que as partições de S determinadas
pelas colorações de G com k cores sejam
a) a partição de S em subconjuntos com um elemento cada:
b) todas as partições excepto a anterior;
c) a partição trivial com o único conjunto S;
d) todas as partições excepto a anterior.
3
Seja S = {s1 , · · · , sn }. A alı́nea a) é imediata: basta considerar o grafo completo no conjunto de vértices S. Evidentemente esta alı́nea só tem significado
se k ≥ n.
Em todas as outras alı́neas é claro que os vértices de S não podem ser adjacentes
entre si, uma vez que estamos sempre a admitir colorações em que vários deles
ficam com a mesma cor.
b) Neste caso queremos que os vértices de S tenham que ser coloridos com n − 1
cores para que haja dois deles com a mesma cor. Tomamos mais k − n + 1
vértices e ligamo-los entre si, criando um Kk−n+1 , e ligamos cada um deles a
todos os vértices si ; numa coloração com k cores, k − n + 1 cores são usadas
para os vértices do subgrafo completo Kk−n+1 e sobram n − 1 cores para colorir
os vértices de S, uma vez que estes são adjacentes a todos aqueles. Dois dos
vértices de S ficam forçosamente com a mesma cor, mas não há mais restrições,
uma vez que os vértices de S não são adjacentes entre si.
c) Ligamos cada vértice si a todos os vértices de um grafo completo Kk−1 ; numa
coloração com k cores, sobra uma única cor para os elementos de S.
d) Este caso é claramente mais difı́cil. Fica aqui a solução, deixando-se a confirmação de que realmente funciona para os mais persistentes. Criamos um grafo
completo Kk−3 e um ciclo C com vértices x1 , · · · , xm , em que m é ı́mpar e maior
que n. Ligamos todos os vértices de Kk−3 a todos os os xi e a s1 . Além disso
ligamos cada xi a algum dos vértices de S, de modo a que todos os vértices de
S sejam adjacentes a algum dos vértices do ciclo.
Tem que se verificar que numa coloração com k cores deste grafo não é possı́vel
colorir todos os vértices de S com a mesma cor, mas que qualquer outra coloração é possı́vel.
Ficha 11 - 8. - Define-se α0 (G) como o número de arestas num emparelhamento máximo de G. Recorde-se, por outro lado, que β(G) designa o número
mı́nimo de vértices numa cobertura, ou seja, que incidem em todas as arestas
do grafo.
a) Mostrar que β(G) ≥ α0 (G);
b) Mostrar que se M for um emparelhamento, C uma cobertura e |M | = |C|
então M é máximo e C é mı́nimo;
c) Mostrar que se G for bipartido, se tem β(G) = α0 (G).
A alı́nea a) é uma consequência directa das definições: se C for uma cobertura e M um emparelhamento, cada aresta de M incide em pelo menos um
vértice de C e arestas diferentes de M não podem incidir no mesmo vértice. É
portanto possı́vel definir uma aplicação injectiva de M em C e temos |M | ≤ |C|.
Como esta desigualdade é válida para qualisquer cobertura e emparelhamento,
tem-se a desigualdade do enunciado.
A conclusão de b) é agora imediata: se |M | = |C| e M não fosse máximo ou C
4
não fosse mı́nimo, terı́amos um emparelhamento com mais elementos do que os
de uma cobertura.
A alı́nea c) é o Teorema de König e Egérvary. A demonstração pode ser feita
á custa do Teorema de Berge sobre emparelhamentos e caminhos aumentáveis:
seja G[X, Y ] um grafo bipartido e suponhamos que X = X1 ∪ X2 e Y = Y1 ∪ Y2
são uniões disjuntas e que temos um emparelhamento máximo M que liga os
vértices de X1 com os de Y1 . De acordo com a alı́nea anterior, basta arranjarmos uma cobertura de G[X, Y ] com o mesmo número de elementos de M .
Chamemos Z ao conjunto de vértices em X1 que podem ser alcançados por um
caminho M -alternado com inı́cio em X2 . A nossa cobertura vai ser constituı́da
pelos vértices em X1 \ Z e pelos vértices de Y1 emparelhados por M com os de
Z. É óbvio que este conjunto de vértices tem o número de elementos desejado;
resta portanto confirmar que se trata de uma cobertura.
As arestas do emparelhamento estão todas cobertas. Além disso, se existir uma
aresta ligando x ∈ X1 com y ∈ Y2 então x não pertence a Z e portanto aquela
aresta também está coberta: caso contrário existiria um caminho M -alternado
com inı́cio em X2 terminando em x que poderia ser prolongável até y, criando-se
assim um caminho M -aumentável, o que é impossı́vel por M ser máximo.
Do mesmo modo, se existir uma aresta entre x ∈ Z e um y ∈ Y1 , o par de y por
M em X1 também pode ser alcançado por um caminho M -alternado a partir
de X2 e portanto y está no nosso conjunto de vértices e a aresta em questão
está coberta.
Notamos finalmente que não existem arestas entre vértices de X2 e de Y2 , pela
hipótese de M ser máximo. As arestas estão portanto todas cobertas.
5