Tema 04 - Planaridade, Coloração, Representaçao Computacional de Grafos - TEXTO DE APOIO

Prévia do material em texto

NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 29 
 
 
3. PLANARIDADE 
Uma representação de um grafo qualquer é dita uma representação plana quando não 
existem arestas que se cruzem (apenas se encontram com outras arestas adjacentes nos vértices 
em comum). Dizemos que G é um grafo planar se G admite uma representação plana. Por 
exemplo, o K4 é um grafo planar (veja figuras (b) e (c) abaixo). 
 
FIGURA 3.1 – DUAS REPRESENTAÇÕES PLANAS PARA O K4: (b) e (c) 
Observe que qualquer representação geométrica de um grafo divide o plano em regiões, ou 
faces, sendo que existe exatamente UMA região ilimitada, denominada face externa. Veja que na 
FIGURA 3.1 (a), a face externa é representada pela região 5, enquanto nas FIGURAS 3.1 (b) e 3.1 (c) a 
face externa é representada pela região 4. 
Quaisquer representações planas de um mesmo grafo possuem sempre o mesmo número 
de faces. Este número, denotado por f, é um valor constante e único para cada grafo. 
• TEOREMA 3.1: (Fórmula de Euler) 
Seja G um grafo planar e conexo. Então n + f = m + 2. 
A prova deste teorema será omitida, e pode ser feita por indução sobre o número de 
arestas. 
• TEOREMA 3.2: Seja G um grafo planar e conexo, com n ≥ 3. Então são válidas as seguintes 
desigualdades: 
(a) m ≤ 3n – 6; e 
(b) Se G não contém ciclo de comprimento 3, então m ≤ 2n – 4. 
A prova deste teorema será omitida, e tem consequências importantes para determinarmos 
se um grafo é planar, como veremos a seguir. 
• LEMA 3.3: Os grafos K5 e K3,3 (FIGURA 3.2 abaixo) são não–planares. 
 
FIGURA 3.2 – GRAFOS NÃO-PLANARES 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 30 
 
 
Para o K5 temos n = 5 e m = 10, e consequentemente m > 3n – 6; desta forma, K5 não é 
planar, pois não satisfaz ao TEOREMA 3.2 (a). Para o K3,3 temos: n = 6 e m = 9. Embora satisfaça ao 
TEOREMA 3.2 (a), note que o K3,3, que não tem ciclo de comprimento ímpar, não satisfaz ao 
TEOREMA 3.2 (b), sendo não planar. Os grafos K5 e K3,3 têm um papel especial para a determinação 
de planaridade em grafos, como veremos a seguir. 
• Subdivisão de um grafo, Homeomorfismo 
Seja um grafo G, e {v,w} uma aresta de G. A subdivisão da aresta {v,w} é a inserção de k 
vértices v1,v2,…,vk à aresta {v,w} de forma que esta seja transformada em um caminho simples 
v,v1,v2,…,vk,w, de forma que todos os k vértices vi tenham grau 2, sendo adjacentes apenas entre 
si (ou então a v ou a w). Dizemos que um grafo G′ é a subdivisão de um grafo G se G′ poder ser 
obtido de G através de subdivisões de arestas de G. A FIGURA 3.3 abaixo, ilustra a definição. 
 
FIGURA 3.3 – G′ É SUBDIVISÃO DE G 
Dois grafos G′ e G′′ são ditos homeomorfos se um deles é a subdivisão do outro, ou se 
ambos são resultados da subdivisão de um terceiro grafo G. Na FIGURA 3.3, G e G′ são 
homeomorfos, enquanto na Figura 32 (abaixo), G e G′ são homeomorfos, bem como G e G′′. 
Ainda, G′ e G′′ são também homeomorfos, pois ambos são subdivisões de G. 
 
FIGURA 3.4 – G, G’ E G′’: GRAFOS HOMEOMORFOS 
• TEOREMA 3.4: (Teorema de Kuratowski) 
Um grafo é planar se e somente se não contém um subgrafo homeomorfo a K5 
ou homeomorfo a K3,3. 
A prova deste teorema será omitida, mas pode ser encontrada na literatura sobre o assunto. 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 31 
 
 
EXERCÍCIOS 3.1 
1) Desenhe uma representação plana para o grafo abaixo, ou prove que este grafo é não-planar. 
 
2) Desenhe uma representação plana para o grafo abaixo, ou prove que este grafo é não-planar. 
 
3) Desenhe uma representação plana para o K2,3. 
4) Desenhe uma representação plana para o K2,4. 
5) Mostrar que o Grafo de Petersen, ilustrado abaixo, é não-planar. 
 
RESPOSTAS E COMENTÁRIOS DE ALGUNS EXERCÍCIOS 
1) 
 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 32 
 
 
4. COLORAÇÃO DE VÉRTICES 
Seja G = (V, E) um grafo qualquer, e C = { c1, c2, c3, … cp } um conjunto de p cores distintas. 
Uma coloração de G é conjunto de atribuições destas cores aos vértices de G, de forma que 
vértices adjacentes tenham cores distintas. Formalmente, uma coloração é uma função: 
cor: V → C, tal que {v,w} ∈ E  cor(v) ≠ cor(w). 
Uma k-coloração de G é uma coloração que utiliza k cores; ou seja, o conjunto imagem da 
função cor tem cardinalidade k. Neste caso, dizemos que G é k-colorível. Observe que todo grafo é 
n-colorível. Basta pegarmos uma cor distinta para cada vértice de G. Mas o objetivo é utilizarmos o 
menor número possível de cores. 
O número cromático de G, notado por χ(G), é o valor mínimo de k para o qual o grafo G é 
k-colorível. Qualquer coloração que utilize χ(G) cores é chamada coloração mínima. A figura 
abaixo mostra um grafo G que admite uma 3-coloração. Pode-se verificar facilmente que esta 
coloração é mínima; desta forma, temos χ(G) = 3. 
 
FIGURA 4.1 – UMA 3-COLORAÇÃO (MÍNIMA) PARA G 
• LEMA 4.1: Um grafo é bicolorível se e somente se for bipartido. 
A prova do LEMA 4.1 é bastante simples. Seja G um grafo bipartido, sendo V = V1 ∪ V2 tal que 
vértices de uma mesma partição não são adjacentes. Podemos então escolher duas cores, uma 
para colorir os vértices de V1, e outra para colorir os vértices de V2. Reciprocamente, se um grafo é 
bicolorível, então podemos particionar V em subconjuntos de vértices de mesma cor. Como 
vértices de mesma cor não são adjacentes, temos que G é um grafo bipartido. 
• Problema das quatro cores 
O Teorema das Quatro Cores diz que é possível colorir as regiões de qualquer mapa 
desenhado no plano (que pode ser modelado como um grafo planar) usando no máximo quatro 
cores, de forma que regiões adjacentes sejam de cores distintas. A FIGURA 4.2 abaixo ilustra um 
mapa com 5 regiões, e seu respectivo grafo, que é 4-colorível, como mostrado. O problema das 
quatro cores relaciona os estudos de COLORAÇÃO e PLANARIDADE em grafos. 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 33 
 
 
 
FIGURA 4.2 – UMA 4-COLORAÇÃO DE UM MAPA 
EXERCÍCIOS 4.1 
1) Determine χ(G) para o grafo G abaixo. Prove que o valor χ(G) está correto: 
(a) Mostre uma χ(G)-coloração para o grafo; e 
(b) Prove que esta coloração é mínima. 
 
2) Construa o menor grafo sem triângulos cujo número cromático seja 3. 
Um grafo sem triângulos não tem o K3 como subgrafo. 
3) Qual é o valor de χ(Kn)? 
4) Seja G um grafo composto apenas por um ciclo simples contendo todos os seus vértices. Qual 
é o número cromático de G? 
5) Determine χ(G) para todos os grafos abaixo. Mostre a χ(G)-coloração de cada um deles. 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 34 
 
 
6) Determine o número cromático do grafo abaixo. Apresente uma coloração para este valor. 
 
7) Considere as seguintes afirmações sobre grafos simples: 
I. Todo grafo bipartido completo é conexo. 
II. Todo grafo bipartido é 2-colorível. 
III. Todo grafo conexo e bipartido é euleriano. 
IV. Existem um grafos 3-regulares planares e não-planares. 
 
Das afirmações acima, são verdadeiras: 
 
(a) Todas, menos a afirmação I. 
(b) Todas, menos a afirmação II. 
(c) Todas, menos a afirmação III. 
(d) Todas, menos a afirmação IV. 
(e) No máximo duas afirmações. 
 
8) Assinale a única alternativa correta sobre o grafo abaixo: 
 
 
a) G é um grafo hamiltoniano e também euleriano. 
b) G é um grafo regular e também hamiltoniano. 
c) G é 3-colorível e admite um caminho euleriano. 
d) G é um grafo bipartido que não contém pontes. 
e) G tem um corte de vértices com cardinalidade 2. 
9) Para o grafo G abaixo, considere as afirmações sobre G. 
 
I. G admite caminho euleriano. 
II. G é hamiltoniano. 
III. G é bipartido. 
IV. G é admite uma 3-coloração de vértices. 
 
Das afirmações acima, são verdadeiras: 
 
(a) Apenas as afirmações I e IV. 
(b) Apenas as afirmações II e IV. 
(c) Apenas as afirmações I e II. 
(d) Todas as afirmações, menos a III. 
(e) Todas as afirmações, menos a II. 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 35 
 
10)Considere os grafos, a seguir. 
 
 
 
Pela análise desses grafos, verifica-se que: 
 
a) G3 e G4 são grafos completos. 
b) G1 e G2 são grafos isomorfos. 
c) G3 e G1 são grafos bipartidos. 
d) G2 e G3 são grafos planares. 
e) G1 e G4 são grafos eulerianos. 
 
RESPOSTAS E COMENTÁRIOS DE ALGUNS EXERCÍCIOS 
1) χ(G) = 3 
a) 
 
b) 
G contém um ciclo de comprimento ímpar (A,B,C,D,E,A). 
Portanto, pelo TEOREMA 1.3, G não é bipartido. 
 
Logo, pelo LEMA 1.1, G não é 2-colorível, e a 3-coloração 
apresentada é uma coloração mínima para G. 
7) c) 
8) c) 
9) d) 
10) b) 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 36 
 
5. REPRESENTAÇÃO COMPUTACIONAL, DIGRAFOS, GRAFOS PONDERADOS 
5.1 REPRESENTAÇÕES COMPUTACIONAIS DE GRAFOS 
Muitas aplicações práticas utilizam modelagem que utilizem determinados grafos, sobre os 
quais serão implementados algoritmos para resolução de problemas específicos. 
As duas estruturas de dados mais utilizadas para representação computacional de grafos são 
as matrizes de adjacências e as listas de adjacências, descritas a seguir. Uma terceira forma, 
menos utilizada é a matriz de incidências, que não será coberta neste estudo. 
• Matriz de Adjacências: 
Uma típica matriz de adjacências de um grafo G = (V, E) é uma matriz An×n definida como: 
∀ 1 ≤ i ≤ n: A[i][i] = 0 vi não é adjacente a si mesmo 
∀ 1 ≤ i , j ≤ n, i ≠ j, A[i][j] = A[j][i] = 1 se vi e vj são adjacentes 
 0 caso contrário. 
A FIGURA 5.1 ilustra uma típica matriz de adjacências para o grafo do EXEMPLO 1. 
































0100000000
1010000000
0100000000
0000001000
0000001000
0000001100
0001110100
0000011010
0000000100
0000000000
10
9
8
7
6
5
4
3
2
1
10987654321
 
 
FIGURA 5.1 – MATRIZ DE ADJACÊNCIAS PARA O GRAFO DO EXEMPLO 1 
Observe que a matriz de adjacências possui as seguintes características: 
• É uma matriz quadrada; 
• Todos os elementos da diagonal principal são nulos; 
• Ela é simétrica em relação à diagonal principal. 
• Listas de Adjacências 
Dependendo da razão entre a quantidade de arestas e o número de vértices do grafo, 
podemos ter um percentual muito pequeno de elementos não nulos na matriz de adjacências, 
configurando o que se denomina matriz esparsa. Normalmente este desperdício de memória não 
é um problema muito relevante. 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 37 
 
Porém, em determinadas aplicações, a quantidade de grafos (e vértices) pode ser de 
considerável magnitude, e a quantidade de memória pode se tornar um fator relevante. 
Uma forma alternativa de armazenamento computacional de grafos é a representação em 
listas de adjacências, como ilustrado na FIGURA 5.2 a seguir. 
 
FIGURA 5.2 – LISTAS DE ADJACÊNCIAS PARA O GRAFO DO EXEMPLO 1 
Nesta estrutura, temos uma lista encadeada associada a cada vértice v. Esta lista contém nós 
para todos os vértices adjacentes a ele. O uso de memória para representar “arestas inexistentes” 
é evitado, o que não acontece na matriz de adjacências. 
A economia de memória tem um preço. Na matriz de adjacências, descobrimos se uma 
aresta (v,w) ∈ E de forma imediata: basta verificarmos A[v][w] ou A[w][v]. Já com listas de 
adjacências, devemos percorrer os nós relativos ao vértice v (ou w) para descobrirmos se tal 
aresta existe. 
Temos então um balanço espaço versus desempenho, que deve ser avaliado para a escolha 
da estrutura mais adequada a uma determinada aplicação. 
EXERCÍCIOS 5.1 
1) Desenhe as matrizes e listas de adjacências dos grafos a seguir: 
 a) b) 
 
2) Desenhe uma representação da matriz de adjacências do K4. Quais são as características da 
matriz de adjacências do Kn? Quantos elementos nulos existem? Quantos não nulos? 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 38 
 
3) Quais são as características da matriz de adjacências de um grafo r-regular com n vértices? 
Quantos elementos nulos e não nulos existem em tal matriz? 
4) Caracterize um grafo cuja matriz de adjacências tenha uma linha com todos os elementos 
nulos. O que você pode dizer da lista de adjacências deste grafo? 
5) Seja o grafo G, cuja matriz de adjacências é exibida abaixo. 
 
⎣
⎢
⎢
⎢
⎢
⎡
0 1 1 1 0 0
1 0 0 1 0 0
1 0 0 1 0 0
1 1 1 0 1 1
0 0 0 1 0 1
0 0 0 1 1 0⎦
⎥
⎥
⎥
⎥
⎤
 
 
Considere as seguintes afirmações sobre G. 
 
I. G é um grafo bipartido. 
II. G admite caminho (não ciclo) hamiltoniano. 
III. G admite caminho (não ciclo) euleriano. 
IV. G contém pelo menos uma ponte. 
V. G contém pelo menos uma articulação. 
 
São verdadeiras: 
 
(a) Apenas as afirmações II, III e V. 
(b) Todas, menos a afirmação IV. 
(c) Apenas as afirmações I, III, e V. 
(d) Apenas duas afirmações acima. 
(e) No máximo uma das afirmações. 
 
 
 
RESPOSTAS E COMENTÁRIOS DE ALGUNS EXERCÍCIOS 
3) Caracterize as linhas e colunas da matriz. 
 Obtenha uma expressão em função de n e k. 
5) Resp.: (a). 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 39 
 
5.2 GRAFOS DIRECIONADOS (DIGRAFOS), GRAFOS PONDERADOS 
Alguns problemas poder exigir uma modelagem que utilize extensões da definição usual de 
um grafo simples. Em determinado problemas de otimização, pode ser necessário que a cada 
aresta seja associado um peso (valor). Outras aplicações exigem que as arestas sejam orientadas 
(modeladas como pares ordenados), indicando um sentido no percurso da aresta em questão. 
• Digrafo 
Um grafo direcionado (ou digrafo) G possui arestas orientadas. Uma aresta orientada é um 
par ordenado de vértices distintos de G. 
Desta forma, uma aresta orientada e será representada como e = (v,w), onde v,w ∈ V, e 
v ≠ w. Neste caso, a aresta (v,w) possui uma única direção: do vértice v para o vértice w. Dizemos 
que a aresta (v,w) é divergente de v e convergente a w. 
• EXEMPLO 5.1: GRAFO DIRECIONADO 
Na representação geométrica de um digrafo, as arestas são representadas como setas 
indicativas de direção, conforme ilustrado na FIGURA 5.3. 
V = { a, b, c, d, e, f, g } 
E = { (a,b), (a,c), (d,a), (d,g), 
 (g,e), (f,g), (e,f), (f,e) } 
 
FIGURA 5.3 – GRAFO DIRECIONADO 
• Digrafos – graus de um vértices, fontes, sumidouros 
Para qualquer vértice v em um dígrafo, definimos: 
grau de entrada de v – in(v): número de arestas convergentes a v (in-degree) 
grau de saída de v – out(v): número de arestas divergentes de v (out-degree) 
No digrafo do EXEMPLO 5.2, temos: 
in(a) = 1 out(a) = 2 
in(b) = 1 out(b) = 0 
in(c) = 1 out(c) = 0 
in(d) = 0 out(d) = 2 
in(e) = 2 out(e) = 1 
in(f) = 1 out(f) = 2 
in(g) = 2 out(g) = 1 
 
FIGURA 5.4 – GRAUS DE ENTRADA E SAÍDA DO DIGRAFO DO EXEMPLO 5.1 
Um vértice com grau de entrada igual a ZERO é denominado fonte. Já um vértice cujo grau de 
saída seja ZERO é chamado sumidouro. No grafo do EXEMPLO 5.2, o vértice d é uma fonte, e os 
vértices b e c são sumidouros. 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 40 
 
• Digrafos – Matriz de Adjacências 
























000000
00000
000000
00000
0000000
0000000
00000
1
11
1
11
11
g
f
e
d
c
b
a
gfedcba
 
 
FIGURA 5.4 – MATRIZ DE ADJACÊNCIAS PARA O DIGRAFO DO EXEMPLO 2 
• Grafos Ponderados 
Em determinadas aplicações, podemos atribuir valores às arestas de um grafo qualquer, seja 
ele direcionado ou não. Formalmente, a cada aresta (v,w) – ou vw em grafos não ponderados –
 será atribuído um peso, tipicamente um valor associado a um custo ou ganho quando tal aresta 
for selecionada ou “percorrida”. Temos então um grafo dito ponderado. 
• EXEMPLO 5.2: GRAFO PONDERADO 
 
FIGURA 5.5 – GRAFO PONDERADO 
• Matriz de Adjacências em grafos ponderados 
Em um grafo ponderado, o peso (weight, em inglês) de uma aresta uv , denotado por será 
atribuído ao seu respectivo elemento W[u][v] da sua matriz de adjacências. 
Em aplicações envolvendo grafos, os pesos das arestas geralmente estarão associados a 
funções de ganhos ou acustos, dependendo do tipo de problema considerado. A partir da 
modelagem em um grafo, é elaborar um algoritmo que minimize uma determinada função. Casos 
típicos envolvem a minimização de (funções de) custos ou maximização de (funções de) ganhos. 
Em problemas de otimização, um elemento da matriz cuja aresta não pertence ao grafo 
geralmente recebe um valor muito grande, quando o problema envolve custo, ou muito pequeno, 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 41 
 
quando são computados ganhos. Formalmente, usamos a notação +∞ ou –∞ nestes casos. A 
figura a seguir ilustra a matriz de adjacências do EXEMPLO 5.2, considerando os pesos como custos 
associados a cada aresta. 
























∞∞∞∞∞
∞∞∞∞∞∞
∞∞∞∞∞
∞∞∞
∞∞∞
∞∞∞∞∞
∞∞∞∞
37
4
510
34512
101298
96
786
7
6
5
4
3
2
1
7654321
v
v
v
v
v
v
v
vvvvvvv
 
 
FIGURA 5.6 – MATRIZ DE ADJACÊNCIAS PARA O GRAFO DO EXEMPLO 5.3 
• EXEMPLO 5.3: DIGRAFOS PONDERADOS 
Os mesmos conceitos de grafos ponderados também se aplicam a grafos direcionados. 
 
FIGURA 5.7 – DIGRAFO PONDERADO 
A matriz de adjacências do grafo do EXEMPLO 5.3 é exibida na figura a seguir, onde os pesos 
são associados a uma função de custo. 
























∞∞∞∞∞∞
∞∞∞∞∞
∞∞∞∞∞∞
∞∞∞∞∞
∞∞∞∞∞∞∞
∞∞∞∞∞∞∞
∞∞∞∞∞
6
87
4
118
75
g
f
e
d
c
b
a
gfedcba
 
 
FIGURA 5.8 – MATRIZ DE ADJACÊNCIAS PARA O DIGRAFO DO EXEMPLO 5.3 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 42 
 
EXERCÍCIOS 5.2 
1) Preencha os elementos de matriz de adjacências do dígrafo abaixo: 






















______
______
______
______
______
______
FEDCBA
F
E
D
C
B
A
 
2) Indique os graus de entrada e de saída dos vértices do digrafo da questão 1): 
in(A) = out(A) = 
in(B) = out(B) = 
in(C) = out(C) = 
in(D) = out(D) = 
in(E) = out(E) = 
in(F) = out(F) = 
Existe alguma fonte ou sumidouro no digrafo acima? Indique quais. 
3) Considere a seguinte definição de um digrafo não-ponderado abaixo (com alocação estática): 
EM PASCAL: 
const 
 MAX = 100; 
 
var 
 A: array[1..MAX,1..MAX] of integer; 
 
 n: integer; { Número de vértices } 
 
EM C: 
#define MAX 100 
 
int A[MAX][MAX]; 
 
int n; // Núm. de vértices 
 
A partir das definições acima, escreva o código de duas funções, GrauEntrada(v) e 
GrauSaida(v), que retornam, respectivamente, os graus de entrada e de saída de um vértice, 
passado como parâmetro – o valor v é o índice do vértice na matriz de adjacências. Considere 
que as declarações acima são variáveis globais. 
Em C: 
int GrauEntrada (int v) 
{ 
 int i, g; /* Variáveis locais */ 
 
 /* Calcule o valor do grau em g */ 
 ... 
 return g; 
} 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 43 
 
5.3 CAMINHOS E CICLOS EM GRAFOS PONDERADOS E/OU DIRECIONADOS 
Os conceitos relativos a caminhos e ciclos podem ser estendidos a grafos ponderados e 
também a digrafos (ponderados e não ponderados). 
• Caminho e ciclos em digrafos não ponderados 
Os conceitos relativos a caminhos e ciclos são análogos aos grafos não direcionados, apenas 
devendo-se respeitar as direções das arestas. A única exceção é que, em um dígrafo, podemos ter 
um ciclo de comprimento 2. 
No digrafo do EXEMPLO 5.1 temos: 
Caminho simples: 
d,g,e,f comprimento 3 
 
Ciclos simples: 
f,g,e,f comprimento 3 
e,f,e comprimento 2 
c
b
a
g
f
e
d
 
• Caminho e ciclos em grafos e digrafos ponderados 
Em grafos e digrafos ponderados, os comprimentos dos caminhos e ciclos são calculados 
somando-se os pesos das arestas envolvidas, independendo da quantidade de arestas percorridas 
no caminho. 
No grafo ponderado do EXEMPLO 5.2, temos: 
Caminhos simples: 
v1,v3,v5 comprimento 18 
v1,v7,v4,v5 comprimento 15 
 
 
No digrafo do EXEMPLO 5.4, temos: 
Caminho simples: 
d,g,e,f comprimento 21 
 
Ciclos simples: 
f,g,e,f comprimento 18 
e,f,e comprimento 11 
 
 
NOTAS DE AULA – PROF. JÚLIO SILVEIRA 
 GRAFOS 44 
 
EXERCÍCIOS 5.3 
1) Para o digrafo ponderado representado abaixo, faça o que se pede: 
a. Preencha TODOS os elementos da sua matriz de adjacências, considerando que o peso de 
cada aresta está associado a CUSTO. 
C
F
8
E
6
9
B
3
D
A
12
7
5
8
5
 






















______
______
______
______
______
______
FEDCBA
F
E
D
C
B
A
 
b. Enumere os seguintes caminhos de A a D, indicando também seus comprimentos. 
Caminho simples de comprimento mínimo: Comprimento = 
Caminho simples de comprimento máximo: Comprimento = 
2) Seja o grafo G, cuja matriz de adjacências é exibida abaixo. 
| 0 1 1 1 0 0 | 
| 1 0 0 1 0 0 | 
| 1 0 0 1 0 0 | 
| 1 1 1 0 1 1 | 
| 0 0 0 1 0 1 | 
| 0 0 0 1 1 0 | 
 
Considere as seguintes afirmações sobre G. 
 
I. G é um grafo bipartido. 
II. G admite caminho hamiltoniano. 
III. G admite caminho euleriano. 
IV. G contém pelo menos uma ponte. 
V. G contém pelo menos uma articulação. 
São verdadeiras: 
 
(a) Apenas as afirmações II, III e V. 
(b) Todas, menos a afirmação IV. 
(c) Apenas as afirmações I, III, e V. 
(d) Apenas duas afirmações acima. 
(e) No máximo uma das afirmações. 
 
RESPOSTAS E COMENTÁRIOS DE ALGUNS EXERCÍCIOS 
2) a)