Matemática Discreta - Teoria dos grafos

Prévia do material em texto

CAPÍTULO 7 - Teoria dos grafos Paulette 
 
89 
 
 
 
TEORIA DOS GRAFOS 
 
1. INTRODUÇÃO 
Muitos problemas foram apresentados ao longo da história e na tentativa de resolvê-los foram 
geradas novas teorias na matemática. O mais famoso deles é conhecido como as pontes de Königsberg, 
que levou o grande matemático Leonardo Euler a inventar um novo ramo da matemática na tentativa de 
resolvê-lo, esse ramo denominou-se Teoria dos grafos. 
Leonardo Euler foi o matemático mais prolífico de todos os tempos, nasceu em Basiléia, na Suíça, 
em morreu em 1783. Escreveu mais de 800 artigos científicos e vários livros. A cidade de Königsberg é 
cortada pelo rio Pregelarme e nele há duas ilhas, ligadas às margens e entre elas por 7 pontes. O 
problema apresentado a Euler era: Seria possível encontrar um caminho que atravesse cada ponte 
exatamente uma vez? 
Euler provou em 1736, que tal percurso era impossível, provando não existir nenhuma solução 
para esse problema. 
Figura das pontes 
Fig. 01 
 
 
 
O problema das pontes se reduz a uma simples rede de pontos unidos por linhas, mostrados aqui por 
sobreposição ao mapa. São 4 pontos A,B,C e D, e 7 arestas uma para cada ponte. Simplificando o 
problema inicial podemos perguntar: Será possível encontrar um trajeto que atravesse a rede passando 
por cada aresta exatamente uma vez? 
 
2. GRAFOS 
 
 Definição 01: 
Grafo é uma terna ordenada (V,A,g) sendo 
 i) V: um conjunto não vazio de vértices ou nós. 
 ii) A: um conjunto de arestas ou arcos. 
 iii) g: uma função que associa cada aresta a um par não ordenado x-y de vértices chamados extremos 
da aresta.. 
 
CAPÍTULO 7 - Teoria dos grafos Paulette 
 
90 
 
Os grafos são normalmente representados por meio de diagramas no plano. 
Exemplo 1: 
 Seja o grafo: 
 
 Fig. 02 
 Este grafo contem quatro vértices e cinco arestas. 
 
 i) V: vértices ou nós, A,B,C e D. 
 ii) A: um conjunto de arestas (arcos) 
 iii) g: uma função que associa cada aresta a um par não ordenado: 
1( )g a A B , 2( )g a B C , 3( )g a C D , 4( )g a A C e 5( )g a B D . 
 
Exemplo 2: 
 O grafo que segue tem 5 vértices e 6 arestas. A função g que associa as arestas aos seus 
vértices. 
 
 6a 
 
 1a 4a 
 3a 3 4 
 
 2a 5a 
 Fig. 03 
 5 
A função g que associa as arestas aos seus vértices é dada por: 
 
1( ) 1 2g a , 2( ) 1 3g a , 3( ) 1 3g a , 4( ) 2 3g a , 5( ) 3 5g a , 6( ) 2 2g a . 
 
 
 Definição 02: Arestas paralelas 
 São as arestas que possuem os mesmos extremos. No exemplo 02, 2a e 3a são ditas paralelas. 
 
 Definição 03: Vértices adjacentes 
 Dois vértices são adjacentes se forem extremos de uma mesma aresta. No exemplo 02, tem-se: 1 
e 3 são adjacentes e o vértice 2 é adjacente a ele mesmo. 
 
A
B
D
3a
C
1a
2a
4a
5a
1
2
CAPÍTULO 7 - Teoria dos grafos Paulette 
 
91 
 
Definição 04: Vértice isolado 
 Não é adjacente a qualquer outro vértice. No exemplo 02, tem-se: o vértice 4 é um vértice 
isolado. 
 
Definição 05: Laço 
Laço é uma aresta com extremos no mesmo vértice. No exemplo 02, tem-se: a aresta 
6a sai do 
vértice 2 e volta ao mesmo vértice 2. 
 
Definição 06: Grafo simples 
 São grafos que não têm arestas paralelas e nem laços. 
 
Definição 07: Grau de um vértice 
 O grau de um vértice de um grafo é o número de arestas incidente nesse vértice. 
 No exemplo 02, tem-se: (1) 3g , (2) 4g , (3) 4g e (4) 0g e (5) 1.g 
Observação: A soma dos graus dos vértices de um grafo G é igual a duas vezes o número de arestas. 
 No exemplo 02, tem-se, 6 arestas e g(G)=12 
 
Definição 08: Grau par ou ímpar 
 Um vértice é par ou ímpar dependendo de seu grau ser par ou ímpar. 
 Um vértice de grau zero é dito vértice isolado. 
 
Definição 09: Grafo completo 
 Um Grafo se diz completo se todos os seus vértices distintos são adjacentes. 
 O exemplo 1 é um grafo completo. 
 
Definição 10: Subgrafo 
 Subgrafo de um grafo G é um subconjunto de arestas e vértices do grafo original. Podemos dizer 
que o subgrafo é um grafo obtido apagando-se parte o gráfico original. 
 
Definição 11: Caminho 
Caminho de um vértice 1A a um vértice nA é uma sequência alternada de vértices e arestas: 
1 1 2 2 3 3 1 1, , , , , ,...., , , ,n n nA a A a A a A a A sendo que cada aresta ia contém os vértices 1i iA A . 
No exemplo 1, tem-se o caminho do vértice A a D: 1 2 3, , , , , , .A a B a C a D 
 
Definição 12: Comprimento de um caminho 
 Comprimento de um caminho é o número de arestas que ele contém 
 O caminho indicado no exemplo 1, o caminho do vértice A a D: 1 2 3, , , , , ,A a B a C a D é de 
comprimento 3. 
 
Definição 13: Grafo conexo 
 Um grafo se diz conexo se existir um caminho entre quaisquer dois vértices. 
 O grafo do exemplo 1 é conexo, porém o exemplo 2 não é conexo. 
 
 
CAPÍTULO 7 - Teoria dos grafos Paulette 
 
92 
 
Definição 14:Ciclo 
 Ciclo em um grafo é o caminho de algum vértice 0 0 até n n de novo, de forma que nenhum 
vértice ocorra mais de uma vez no caminho. 
 
Definição 15: Árvores 
 Uma árvore é um grafo acíclico e conexo com um nó designado como raiz da árvore. Os grafos 
que seguem são duas árvores. 
 
Fig. 04 
 Um grafo acíclico e conexo sem a designação de um vértice como raiz é chamado de árvore não 
enraizada. Um único vértice é uma árvore e esse vértice é a raiz. 
 Dado que a árvore é um grafo conexo, existe um caminho entre a raiz e todos os vértices da 
árvore e como a árvore é acíclica, esse caminho é único. 
 
Definição 16:Profundidade de um vértice 
 Profundidade de um vértice de uma árvore é o comprimento do caminho da raiz até o vértice. A 
raiz tem profundidade zero. 
 
Definição 17: Altura da árvore 
 Altura da árvore é a maior profundidade de todos seus vértices. É o comprimento do maior 
caminho entre a raiz e um vértice. 
 
Definição 18: Folha 
 Um vértice sem filhos é denominado de folha. 
 
Definição 19: Vértices internos 
 Os vértices que não são folhas são denominados vértices internos. 
 
Definição 20: Floresta 
 Floresta é um grafo acíclico, portanto uma floresta é uma coleção de árvores disjuntas. 
 
Definição 21: Árvore binária 
 Uma árvore se diz binária se cada nó tem no máximo dois filhos, sendo um filho denominado 
filho à direita e filho à esquerda. 
 
r
r
CAPÍTULO 7 - Teoria dos grafos Paulette 
 
93 
 
Definição 22: Árvore binária completa 
 Uma árvore binária se diz completa se todos os nós internos têm dois filhos e todas as folhas têm 
a mesma profundidade. 
 A Fig.05a é uma árvore binária de altura 4 e a Fig.05b é uma árvore binária completa de altura 
3. 
 
 
 Fig. 05 a Fig. 05 b 
Exemplo 3: 
 Construir um grafo que tenha os vértices {1,2,3,4,5} e as arestas 1 2 3 4 5 6{ , , , , , }a a a a a a e a função 
1( ) 1 2g a , 2( ) 1 3g a , 3( ) 3 4g a , 4( ) 3 4g a , 5( ) 4 5g a , 6( ) 5 5g a . 
a)Construir o grafo 
 
Fig.06 
 
Com relação ao grafo obtido, responda as questões. 
b) dois vértices que não sejam adjacentes. f) um vértice que seja adjacente a ele mesmo 
 Resp: 1 e 4 Resp: 5 
 c) um laço. g) duas arestas paralelas. 
 Resp: 5 Resp: 
3 4a e a 
d) o grau do vértice 3. h) este gráfico é conexoResp: 3 Resp: Sim 
e)este grafo é completo? 
 Resp: não, pois 2 e 3 não são adjacentes. 
 
 
 
 
 
r r
1
2
3
4
5
1a
3a
4a
2a
5a
6a
r r
CAPÍTULO 7 - Teoria dos grafos Paulette 
 
94 
 
Exercícios de aplicação 20: 
1) Responder as questões observando o grafo. 
 
 
 
 Fig.07 
a)Este grafo é simples? 
 
 
 
 
 
 
b)Este grafo é completo? 
 
 
c)Este grafo é conexo? 
 
d)Existem dois caminhos entre os vértices 7 e 3? 
 
 
e)Este grafo possui ciclo? 
 
f)O grafo possui alguma aresta cuja remoção o tornaria 
uma árvore. 
 
2) Esboce um diagrama para cada um dos seguintes grafos. 
a)Um grafo simples com 3 vértices, cada qual com 2 graus. 
 
 
 
b)Uma árvore com cinco vértices de altura 1. 
 
 
 
 
3) Responder as questões observando a 
árvore. 
 Fig.08 
 
 
a)Qual a altura? 
 
 
 
b)Qual é o filho à esquerda do nó B? 
 
 
 
c)Qual a profundidade do nó E? 
 
 
 
 
A
B
C
D
1a
2a
3a
4a
E
5
6a
2
3
6
7 1a
2a
3a4
a
5a
7a
4
1
CAPÍTULO 7 - Teoria dos grafos Paulette 
 
95 
 
 
 
4) Responder as questões observando a 
árvore. 
 Fig.09 
 
 
a)A árvore é binária? 
 
b)A árvore é binária completa? 
 
 
 
c)Qual o pai do vértice f ? 
 
 
 
d)Qual é o filho à esquerda do vértice h? 
 
 
e)Qual a altura de g? 
 
 
 
f)Qual a altura da árvore? 
 
 
 
 
5)No grafo a seguir: 
 
 
a) Descreva formalmente o grafo. 
 
 
 
 
 
b) Dê o grau de seus vértices. 
 
 
 
c) Qual a soma dos graus dos vértices? 
 
 
 Definição 23: Grafos direcionados 
 
Muitas vezes há interesse que as arestas de um grafo comecem em um vértice e terminem em 
outro, neste caso, podemos usar o grafo direcionado. 
 
Grafo direcionado é uma terna ordenada (V, A, g) sendo 
 i) V: um conjunto não vazio de vértices ou nós. 
 ii) A: um conjunto de arestas ou arcos. 
 iii) g: uma função que associa cada aresta a um par ordenado (x,y) de vértices chamados extremos da 
aresta, sendo x ponto inicial e y ponto final. 
 
A
B
C
D
1a 2a
3a
4a
5a
7a8a
6a
E
b
c
d
e
f g h
i
a
CAPÍTULO 7 - Teoria dos grafos Paulette 
 
96 
 
 Exemplo 4: 
O grafo que segue é um grafo direcionado e apresenta três caminhos do vértice A para o vértice C. 
 
 Fig.10 
 
 
Exercícios de aplicação 21: 
 
1)Responder as questões observando o grafo direcionado. 
 
 Fig.11 
a) Quais são os nós acessíveis a partir do vértice A? 
 
 
 
b) Qual o caminho mais curto de A para C? 
 
 
 
c) Qual o caminho de comprimento 6 de A a para D? 
 
 
 
 
 
A
B C
D
1a
2a
3a
4a
5a
7a
9a
10a
8a
F
6a E
11a
D
3a
A
B C
1a
2a
4a
5a
CAPÍTULO 7 - Teoria dos grafos Paulette 
 
97 
 
2) Transforme o grafo em grafo direcionado de tal forma que partindo de um vértice passe por todos 
os vértices, sem usar duas vezes a mesma aresta. Se isto for feito teremos um grafo atravessável. 
 
 Fig.12 
 
Definição 24: Grafos isomorfos 
 
Os grafos G= (V,A,g) e G’= (V’,A’,g’) são isomorfos se, existir uma aplicação bijetora 
: 'f V V tal que se ea b são duas arestas de G, então ( )e ( )f a f b são arestas de G’. 
 
 Exemplo 5: Os grafos que seguem são isomorfos (Mostre você) 
 
 Fig.13 
 
 Exemplo 6: 
Os grafos que seguem não são isomorfos 
 
 Fig.14 
 Os grafos possuem 6 vértices e 7 arestas, o vértice A´ de grau 2, é adjacente aos vértices 
 
 
Á
não é isomorfo a
A
B
C
D
E
F
´B
´C
A
B
2a
C
D
1a 3a
4a
5a
6a7a
8a
é isomorfo a
E
´D
´E
´F
é isomorfo a
CAPÍTULO 7 - Teoria dos grafos Paulette 
 
98 
 
 
B´ e F´ de grau 3, porém, o vértice A correspondente o vértice A´ é adjacente aos vértices B de grau 3 e 
F de grau 2, portanto, os grafos não são isomorfos. 
Condições para verificar se dois grafos são isomorfos: 
 
 Existem certas condições sob as quais se torna mais fácil ver se dois grafos não são isomorfos. 
 1.Um grafo tem mais vértices que o outro. 
 2.Um grafo tem mais arestas que outro. 
 3.Um grafo tem mais arestas paralelas e outro não. 
 4.Um grafo tem um laço e o outro não. 
 5.Um grafo tem um vértice de grau K e o outro não. 
 6.Um grafo é conexo e o outro não. 
 7.Um grafo tem um ciclo e o outro não. 
 
 
Exemplo 7: 
Os grafos que seguem são ou não isomorfos. 
 
 Fig.15 
Verificando as condições para ver se dois grafos são ou não isomorfos. 
 1. Um grafo tem mais vértices que o outro. (não). 
 2. Um grafo tem mais arestas que outro. (não). 
 3. Um grafo tem mais arestas paralelas e outro não. (sim) 
 4. Um grafo tem um laço e o outro não. (não). 
 5. Um grafo tem um vértice de grau K e o outro não. ( O primeiro grafo tem o vértice A com 
grau 4 e o vértice A´ correspondente tem grau 3) 
 6. Um grafo é conexo e o outro não. (não). 
 7. Um grafo tem um ciclo e o outro não. (não). 
 Portanto, os grafos não são isomorfos, pois não atendem o item 3 e o item 5. 
 
 
 
 
 
A
B ´DD
Á
´B
´CC
CAPÍTULO 7 - Teoria dos grafos Paulette 
 
99 
 
 
Exercícios de aplicação 22: 
 
1) Qual dos grafos que seguem não é isomorfo aos outros? Por que? 
 Fig.16 
2) Qual dos grafos que seguem não é isomorfo aos outros? Por que? 
 
 Fig.17 
 
3) Verifique se os grafos são ou não isomorfos. Se forem apresente a função que estabelece o 
isomorfismo entre eles, caso contrário explique por quê. 
 
 Fig.18 
 Fig.19 
 
a b c d
)a
)b
CAPÍTULO 7 - Teoria dos grafos Paulette 
 
100 
 
 Fig.20 
 Fig.21 
 
Definição 25: Grafo Atravessável 
 
 Um grafo se diz atravessável se pode ser desenhado sem quebras nas curvas e sem repetição de 
arestas, isto é, se existir um caminho que inclua todos os vértices e use cada aresta uma única vez. 
 
Exemplo 8: 
 Foi pedido no exercício de aplicação 02 para transformar o grafo que segue em grafo 
direcionado de tal forma que partindo de um vértice passe por todos os vértices, sem usar duas vezes a 
mesma aresta. Se isto for feito teremos um grafo atravessável. 
 
 
 Fig.22a Fig.22b 
 
 Nestas condições o caminho é uma trilha, pois, nenhuma aresta pode ser usada duas vezes, e será 
uma trilha atravessável, assim a trilha é: 
 
1 7 6 8 4 3 5 2
, , , , , , , , , , , , , , , ,B a A a E a D a A a C a D a B a C . 
 
A
B
2a
C
D
1a 3a
4a
5a
6a7a
8a A
B
2a
C
D
1a 3a
4a
5a
6a7a
8a
E
)c
)d
E
CAPÍTULO 7 - Teoria dos grafos Paulette 
 
101 
 
 Se a trilha passa por um vértice P de grau 2, neste caso a trilha entra e sai por esse vértice. Se P é 
um vértice de grau 3, a trilha será atravessável se começar em P e terminar em outro vértice também de 
grau 3. Se uma trilha possuir dois vértices P e Q de grau ímpar, a trilha deve começar por P e terminar 
em Q. Se o caminho tiver 3 ou mais vértices ímpares, o caminho não é atravessável. 
 O caminho pelas pontes de Könisberg apresentam 4 vértices de graus ímpares, portanto não é 
atravessável. 
 
Definição 26: Grafo Euleriano e Hamiltonianos 
 
 Um grafo se diz euleriano se existir uma trilha atravessável fechada.(Ver Fig.22b) 
 Um grafo conexo finito é euleriano se, e somente se cada vértice tem grau par. 
O caminho euleriano percorre cada aresta exatamente uma vez. 
 Um grafo se diz ciclo hamiltoniano (William Rowan Hamilton 1865-1905) se for fechado e 
visita todos os vértices exatamente uma vez. Um caminho nessas condições deve ser um ciclo. 
Um ciclo hamiltoniano percorre cada vértice exatamente uma vez 
 
Exemplo 9: 
Verifique se os grafos a seguir são ounão Ciclo hamiltoniano e Grafo euleriano. 
 
 .23Fig a (Ciclo hamiltoniano) .23Fig b(Grafo euleriano) 
 
 
Definição 27: Grafo Bipartido Completo 
 Sabemos que os grafos que seguem são grafos simples completos com 1, 2, 3, 4 e 5 vértices. 
 
 Fig. 24 
 
O grafo simples que segue não é um grafo completo, porque nem todo vértice é adjacente a todos 
os demais vértices, mas, os vértices podem ser divididos em dois grupos disjuntos {A,B} e {C,D,E} de 
tal forma que dentro do conjunto quaisquer dois vértices são adjacentes. 
1
k
2
k
3
k
4
k 5
k
CAPÍTULO 7 - Teoria dos grafos Paulette 
 
102 
 
 Fig. 25 
Os grafos com essa característica são denominados grafos bipartidos completos e denotamos 
por 
2 ,3
k . 
Exemplo 10: 
Qual é o diagrama para o grafo 
3,3
k ? 
 
3,3
k é um grafo conexo simples com três conjuntos disjuntos, portanto, segue seu diagrama. 
 
 Fig. 26 
Definição 28: Grafo planar 
 
 Um grafo se diz planar se pode ser desenhado em um plano de forma que suas arestas se 
interceptem apenas nos vértices. Muitas vezes o grafo é planar e, é desenhado com cruzamentos de 
arestas, no entanto, podemos determinar um grafo isomorfo sem cruzamentos. 
 
Exemplo 11: 
O grafo visto na Fig. 27a possui cruzamentos, mas é isomorfo ao grafo da Fig. 27b, assim são 
planares. 
 
A
B ´DD
Á
´B
´CC
.27Fig a .27Fig b
A B C
D E F
A B
C D E
CAPÍTULO 7 - Teoria dos grafos Paulette 
 
103 
 
Exemplo 12: 
O grafo visto na Fig. 28a possui cruzamento, mas é isomorfo ao grafo da Fig. 28b, assim são 
planares. 
 
 
 Fig. 28a Fig. 28b 
 
Exemplo 13: 
O grafo 
5
k visto na Fig. 29 é um grafo conexo, simples. Verifique se é planar. 
 
 
 
Construindo 
5
k por etapas e incluindo se possível novas arestas que não interceptem as já 
concluídas. Na construção da Fig.c ,nota-se que não existe maneira de construir a última aresta 2-4 no 
mesmo plano sem interceptar as outras arestas, portanto o grafo não é planar. 
 
 
 
No exemplo 13 tentamos resolvê-lo por tentativa e erro, vejamos agora a fórmula de Euler para 
resolução desses problemas. 
Seja G um grafo conexo, simples e planar com: 
n: vértices, 
a: arestas e 
r: regiões. 
 
 
a b c
1 1
1
2 2
2
3 3
34 4 4
5
5
5
.30Fig
CAPÍTULO 7 - Teoria dos grafos Paulette 
 
104 
 
Definição 29: Região 
 
Um grafo conexo simples e planar com seu diagrama planar sem interseções de arestas, divide o 
plano em regiões. Do exemplo 13, a Fig.30a divide o plano em 2 regiões, Fig.30b divide o plano 4 
regiões e Fig.30c divide o plano 6 regiões. 
 
Formula de Euler 
Se G é um grafo conexo, simples, planar e com r regiões, então 
 i) 2n a r . 
 ii) Se 3, então 3 6.n a n 
 iii) Se 3n e não existem ciclos de comprimento 3, então 2 4.a n 
 
 Exemplo 14: 
 Verifique se o grafo 
5
k é planar. 
 
Fig.31 
 Do diagrama podemos concluir que 
5
k é conexo, simples com n =5 vértices e a =10 arestas e 
pelo item ii) se 3, então 3 6n a n segue 10 3.5 6 10 9,a portanto 5k não é 
planar como já tínhamos visto no exemplo 13. 
 
 
Exercícios de aplicação 23: 
 
1)Verificar se o grafo 
2 ,3
k é planar (ver Fig. 25 ) 
 
 
 
 
 
 
2)Verificar se o grafo 
3,3
k é planar(ver Fig. 26 ). 
 
 
 
 
 
 
CAPÍTULO 7 - Teoria dos grafos Paulette 
 
105 
 
3)Verificar se o grafo é planar e dar o número de regiões que divide o plano. 
 
 
 
4) Se todos os vértices de um grafo simples conexo e planar tem grau 4 e o número de arestas é 12, 
quantas regiões divide o plano? 
 
 
 
 
3. COLORAÇÃO 
 Alguns problemas são fáceis de enunciar, porem difíceis de resolver. O teorema das quatro cores 
é um bom exemplo. O estudante de pós-graduação Francis Guthrie da Universidade College, em 
Londres (1852), ao colorir o mapa dos municípios da Inglaterra descobriu que conseguia fazê-lo usando 
para isso 4 cores (ou menos) de modo que as regiões que possuem fronteiras comuns jamais tenham a 
mesma cor. Ele se perguntou se esse fato seria uma particularidade para o mapa da Inglaterra. 
 
 Será possível colorir qualquer mapa no plano com quatro cores de modo que as regiões que 
possuem fronteiras comuns jamais tenham a mesma cor? 
Não se conseguiu até agora nenhuma prova conceitual para esse teorema. Famosos matemáticos 
tentaram resolver esse problema sem sucesso, tais como: Augustus De Morgan, William Rowan 
Hamilton, Arthur Cayley e Philip Franklin. Em 1976 dois matemáticos americanos Kenneth Appel e 
Wolfang Haken usando computadores e testes de redutibilidade com 487 regras diferentes encontraram 
cerca de 1405 configurações de mapas distintos e todas elas usaram 4 cores. 
 
 
 
3.1 Grafo dual de um mapa 
 
Seja M um mapa. Se colocarmos um vértice em cada região do mapa, e uma aresta entre dois 
vértices que representem países adjacentes, então o problema de coloração do mapa, torna-se problema 
de coloração de vértices de um grafo dual, de forma que não haja dois vértices adjacentes que tenham a 
mesma cor. 
 
3.2 Número cromático 
 
 É o menor número de cores necessárias para se obter uma coloração. 
 
 
 
CAPÍTULO 7 - Teoria dos grafos Paulette 
 
106 
 
Exemplo 15: 
Desenhe o grafo dual do mapa da figura que segue. 
 
 
3.3 Algoritmo de welch-powell 
 
 Seja um grafo G. Uma coloração de vértices de G é uma atribuição de cores aos vértices de G de 
tal forma que vértices adjacentes têm cores distintas. Utilizaremos a seguir o Algoritmo de Welch-
Powell para a coloração minimal de um gráfico G. 
 
 
 
Passo 1: Ordenar os vértices de G em ordem decrescente de grau. 
Passo 2: Atribuir a primeira cor, 
1
C , ao primeiro vértice e, então sequencialmente atribua a mesma cor 
1
C para vértices não adjacente ao primeiro vértice. 
Passo 3: Repetir o passo 2 com a segunda cor 
2
C e os vértices subsequentes não coloridos. 
Passo 4: Repetir o passo 3 com a terceira cor 
3
C , depois com a cor 
4
C e assim por diante. 
Exemplo 16: 
Utilize o Algoritmo de Welch-Powell para a coloração do grafo 
5
k . 
 O grafo 
5
k tem todos os vértices de mesmo grau e neste caso usamos a ordem natural do grafo. 
 
 
Passo 1: Ordenar os vértices em ordem decrescente de 
grau.(A,B,C,D,E) 
Passo 2: Atribuir a primeira cor, 
1
C , vértice A 
Passo 3: Atribuir a primeira cor, 
2
C , vértice B 
Passo 4: Atribuir a primeira cor, 
3
C , vértice C 
Passo 5: Atribuir a primeira cor, 
4
C , vértice D 
Passo 6: Atribuir a primeira cor, 
5
C , vértice E 
Fig.33 
 
Sabemos que todo grafo planar é 4-colorizável, porém, 
5
k não é planar e é 5-colorizável. De 
modo geral 
n
k é n-colorizável. 
A
B
CD
E
.32Fig
CAPÍTULO 7 - Teoria dos grafos Paulette 
 
107 
 
 
Exercícios de aplicação 24: 
1) Encontre o número cromático para cada grafo. 
 
2) Encontre o número cromático para o grafo. 
 
 
4. MATRIZ DE ADJACÊNCIAS 
 
 Seja G um grafo com m vértices e sejam ordenados como
1 2 3
, , ,..., .
m
n n n n A matriz de adjacências 
ij
A a do grafo G é a matriz m m definida por 
 
 
1 se é adjacente 
0 caso contrario
i j
ij
n n
a 
 
Exemplo 16: 
 Dar a matriz de adjacência para o grafo. 
 
 
A 
11 12 13 14
21 22 23 24
31 32 33 34
41 42 43 44
0 1 0 1
1 0 1 1
0 1 0 0
1 1 0 0
a a a a
a a a a
A
a a a a
a a a a
 
2
3
4
1
CAPÍTULO 7 - Teoria dos grafos Paulette 
 
108 
 
Exemplo 17: 
 Dar a matriz de adjacência para o grafo. 
 
 
Solução 
 
1 1 0 1
1 0 2 1
0 2 0 0
1 1 0 0
 
 
 
A matriz de adjacência dos exemplos são todas simétricas, isso não ocorre se a matriz de adjacência 
for de grafos não direcionados. 
 
Exemplo 18: 
 Dar a matriz de adjacência para o grafo direcionado. 
 
 
Solução: 
1 1 0 0
0 0 1 0
0 1 0 0
1 1 0 0A matriz de adjacência desse exemplo não é simétrica, isso ocorreu por ser um grafo direcionado. 
 
Exercícios de aplicação 25: 
 
1) Dar a matriz de adjacência para o grafo. 
 
 
 
 
 
 
 
2
3
4
1
3
2
4
1
2
3
4
1
CAPÍTULO 7 - Teoria dos grafos Paulette 
 
109 
 
2) Dar a matriz de adjacência para o grafo. 
 
 
 
 
3) Dar a matriz de adjacência para o grafo. 
 
 
 
 
 
 
 
 
 
 
4)Encontre o grafo direcionado para a matriz. 
 
0 1 1 1
0 1 0 0
0 1 0 0
0 0 1 0
 
 
 
 
2
4
1
5
6
3
2
3
4
1