Cap2 TG terminologia

Prévia do material em texto

TEORIA DOS GRAFOS
Prof. Bernardo Caldas
bcaldasbc@gmail.com
17/02/2018 1Teoria dos Grafos
• “Por menor que seja seu tempo de estudo, ESTUDE.”
• “Não tenha medo de crescer lentamente, tenha medo 
apenas de ficar parado.”
17/02/2018 2Teoria dos Grafos
• “Você deve estudar para “aprender” e “não” para passar de 
ano.”
• “Eu só sei que nada sei.” - Sócrates
• Minha meta é formar pensadores.
Índice
• Terminologia
• Isomorfismo
• Representação planar
• Complementariedade , subgrafos• Complementariedade , subgrafos
• Comprimento mínimo
• Matrizes de adjacência e listas de adjacência
• Problemas de cor
17/02/2018 3Teoria dos Grafos
Introdução
• Faça a ligação de telefone, gás e luz em cada casa
sem que as linhas se cruzem.
• A solução desse problema pode minimizar custos na
confecção de placas de circuitos impressos.
17/02/2018 4Teoria dos Grafos
Introdução
• “Uma figura vale mais que mil palavras”.
17/02/2018 5Teoria dos Grafos
Existe uma rota direta entre Chicago e Denver, mas
não existe rota direta entre Denver e Dallas.
Introdução
• “Uma figura vale mais que mil palavras”.
17/02/2018 6Teoria dos Grafos
Introdução
• “Uma figura vale mais que mil palavras”.
17/02/2018 7Teoria dos Grafos
Introdução
• “Uma figura vale mais que mil palavras”.
17/02/2018 8Teoria dos Grafos
Introdução
• “Uma figura vale mais que mil palavras”.
17/02/2018 9Teoria dos Grafos
Introdução
• Dentre os diversos problemas existentes na computação é comum
encontrar problemas de conexão entre elementos.
• Esses problemas podem ser representados pela teoria dos grafos.
• Gráfico -> é qualquer representação visual de dados.
17/02/2018 10Teoria dos Grafos
• A Teoria dos Grafos é um ramo da matemática que estuda as relações
entre objetos de um determinado conjunto.
• Um grafo é um conjunto não-vazio de nós(ou vértices) e um conjunto de
arcos(ou arestas) tais que cada arco conecta dos nós.
nó
nó (vértice)arco (aresta)
Introdução
• O gráfico abaixo possui 5
nós e 7 arcos.
• O arco a1 conecta os
1 2
a1
17/02/2018 11Teoria dos Grafos
• O arco a1 conecta os
nós 1-2, a4 conecta os
nós 3-5, e assim por
diante.
3
4 5
a4
a3
a6
a5
a2
a7
Histórico
• A Teoria dos Grafos teve
sua origem com o
“problema das pontes de
Konigsberg” ( 1735).
17/02/2018 12Teoria dos Grafos
Konigsberg” ( 1735).
• Esse problema foi
resolvido por Leonharde
Euler em 1736.
Matemático Suíço
Histórico
• Os habitantes da cidade (localizada na Rússia)
gostariam de saber se era possível cruzar as sete
pontes numa caminhada contínua sem passar duas
vezes por qualquer delas.
17/02/2018 13Teoria dos Grafos
Histórico
• A solução de Euler foi representar por um grafo G as
pontes por arcos e as partes de terra por nós.
• Um caminho de Euler em um grafo G é um caminho
que usa cada arco em G exatamente uma vez.
17/02/2018 14Teoria dos Grafos
que usa cada arco em G exatamente uma vez.
Definição de Grafo
• Um grafo é uma tripla ordenada (N,A,g), onde:
– N = um conjunto não vazio de nós (vértices)
– A = um conjunto de arcos (arestas)
17/02/2018 15Teoria dos Grafos
– A = um conjunto de arcos (arestas)
– g = uma função que associa a cada arco a um par não
ordenado x,y de nós, chamados de extremidades de a.
Definição de Grafo
1 3 4 5
2
a1
a2
a3
a4
a5 a6
17/02/2018 16Teoria dos Grafos
• A função g que associa arcos a suas extremidades é:
– g(a1)=1-2, g(a2)=1-2, g(a3)=2-2, g(a4)=2-3, g(a5)=1-3,
g(a6)=3-4
Definição de Grafo Direcionado
• Um grafo direcionado (dígrafo) é uma tripla ordenada
(N,A,g), onde:
– N = um conjunto não vazio de nós
– A = um conjunto de arcos
– g = uma função que associa a cada arco a um par ordenado
17/02/2018 17Teoria dos Grafos
– g = uma função que associa a cada arco a um par ordenado
(x,y) de nós, onde x é o ponto inicial (extremidade inicial) e y é o
ponto final (extremidade final) de a.
• Em um grafo direcionado, cada arco tem um
sentido ou orientação.
∫aa
r
Definição de Grafo Direcionado
1 3 4
2
a1 a2
a3 a4
17/02/2018 18Teoria dos Grafos
• Um grafo direcionado com 4 nós e 4 arcos e função g
que satisfaz g(a1)=(1,2), g(a2)=(2,3), g(a3)=(1,3) e
g(a4)=(3,4).
Definição de Grafo Direcionado
1 3 4
2
7 5
4 2
17/02/2018 19Teoria dos Grafos
• Havendo a necessidade dos nós conter informações
identificadoras, ou rótulos, esse grafo será um grafo
rotulado. É possível pesos, distâncias, relacionamentos,
etc...(pesos de uma rede neural, diagrama E-R, PERT)
Terminologia
Arcos paralelos
• Dois arcos com as mesmas extremidades são ditos
arcos paralelos. Os arcos a1 e a2 são arcos paralelos.
a3
17/02/2018 20Teoria dos Grafos
1 3 4 5
2
a1
a2
a3
a4
a5 a6
Terminologia
Nós adjacentes
• Dois nós são ditos adjacentes se ambos são as
extremidades de algum arco. A noção de adjacência
de nós é associada a grafos não orientados.
2
a3
17/02/2018 21Teoria dos Grafos
• Os nós 1 e 3 são nós adjacentes, 1 e 4 não são
adjacentes e o nó 2 é adjacente a si mesmo.
1 3 4 5
2
a1
a2
a4
a5 a6
Terminologia
Laço
• Um laço em um grafo é um arco com extremidades
n-n para algum nó n. o arco a3 é um laço, bem como
v1.
2
a3
17/02/2018 22Teoria dos Grafos
• A terminologia grafo sem laço, é aplicada quando o
grafo não tiver nenhum laço.
1 3 4 5
2
a1
a2
a4
a5 a6
Terminologia
Nó isolado
• Um nó isolado é um nó que não é adjacente a
nenhum outro. O nó 5 é um nó isolado.
17/02/2018 23Teoria dos Grafos
1 3 4 5
2
a1
a2
a3
a4
a5 a6
Terminologia
17/02/2018 24Teoria dos Grafos
Obs.:
Multigrafo: é o grafo que permite arcos paralelos e não permite laço
Pseudografo: é o grafo que permite arcos paralelos e permite laço
Terminologia
Grau de um nó
• O grau de um nó é o número de extremidades de
arcos naquele nó.
2
a2
a3
17/02/2018 25Teoria dos Grafos
• Os nós 1 e 3 têm grau 3, o nó 2 tem grau 5, o nó 4
tem grau 1 e o nó 5 tem grau 0.
1 3 4 5
a1
a2
a4
a5 a6
Terminologia
Ordem e tamanho de um grafo
• Ordem de um grafo é o número de nós que ele
possui.
• Tamanho de um grafo é o número de arcos que ele
possui.
17/02/2018 26Teoria dos Grafos
possui.
1 3 4 5
2
a1
a2
a3
a4
a5 a6 1
4
2
a1
a2
a3
a4
3
Ordem: 5
Tamanho: 6
Ordem: 4
Tamanho: 4
Terminologia
Nó sucessor e antecessor
• Um nó j é sucessor de i se existe pelo menos um arco
ligando i a j. No caso da ocorrência da relação inversa
diz-se que o nó j é antecessor de i.
• O nó 2 é antecessor do nó 3 e os nós 1 e 4 são
17/02/2018 27Teoria dos Grafos
O nó 2 é antecessor do nó 3 e os nós 1 e 4 são
sucessores do nó 3
1 3 4
2
a1
a2 a3
Terminologia
Grafo trivial
• Um grafo é dito trivial quando possui somente
um nó.
17/02/2018 28Teoria dos Grafos
1
Terminologia
Grafo simples
• Um grafo simples é um grafo sem laços e
arcos paralelos.
2
9Km
3
17/02/2018 29Teoria dos Grafos
1
4
2
7Km
12Km
15Km
Terminologia
Grafo completo
• Um grafo é dito completo se dois nós distintos
quaisquer são adjacentes.
2 3a1
a4a2
a3
17/02/2018 30Teoria dos Grafos
1
4
5
a3
a5
a6
a7
a8
a9
a10
• Um grafo completo possui n(n-1)/2 arcos.
Terminologia
Teorema 1
• Em um grafo não orientado qualquer, o
somatório dos graus de todos os nós é igual ao
dobro do número de arcos. Ou seja, todo grafo G
satisfaz a identidade:
17/02/2018 31Teoria dos Grafos
nógraunóg
arcoa
onde
ang
__)(
_
:
*2)(∑ =
N=4
A=4
8=2*4
N=4
A=510=2*5
N=5
A=5
10=2*5
N=5
A=6
12=2*6
N=1
A=0
0=2*0
Terminologia
Teorema 2
• Um grafo não orientado qualquer, o número de nós
de grau ímpar é par.
2
2
2 2
4
17/02/2018 32Teoria dos Grafos
Dois nós de grau impar
Dois nós de grau impar
2
3
3
33
Terminologia
Teorema 2
• Um grafo não orientado qualquer, o número de nós de grau ímpar é par.
• Em uma cidade existem 15 telefones e deseja-
se ligar cada telefone a exatamente 5 outros
17/02/2018 33Teoria dos Grafos
se ligar cada telefone a exatamente 5 outros
telefones. É possível?
– Não => 15*5=45(ímpar) e é contrário ao teorema 2.
Terminologia
Caminho de um nó
• Um caminho do nó n0 para o nó nk é uma
sequencia n0, a0, n1, a1,...,nk-1, nk de nós e arcos
onde, para cada i, as extremidades do arco ai são
ni-ni+1.
17/02/2018 34Teoria dos Grafos
1 3 4
2
a1
a2
a3
a4
a5 a6
5
• Um caminho do nó 2 para o nó 4
será: 2, a1, 1, a2, 2, a4, 3, a6, 4.
• Nós e arcos podem ser repetidos
em um caminho.
Terminologia
Um ciclo
• Existem muitos caminhos do nó 1
para o nó 3: 1, a4, 3; 1, a1, 2, a2,
2, a2, 2, a2, 2, 3. Isso torna 3 um
nó acessível.
17/02/2018 35Teoria dos Grafos
nó acessível.
• O nó 1 não é acessível a nenhum
outro nó.
• Os ciclos no gráfico são: 2, a2, 2 e
3, a5, 4, a6, 3.
Terminologia
Comprimento do caminho
• O comprimento de um caminho é o número de
arcos que ele contém, se um arco for usado mais
de uma vez, ele é contado cada vez que é usado.
17/02/2018 36Teoria dos Grafos
1 3 4
2
a1
a2
a3
a4
a5 a6
5
• Um caminho do nó 2 para
o nó 4 será: 2, a1, 1, a2,
2, a4, 3, a6, 4 e seu
comprimento é 4.
Terminologia
Grafo conexo
• Um grafo é conexo se existir um caminho de
qualquer nó para qualquer outro.
2
a2
a3
Um grafo conexo emA
17/02/2018 37Teoria dos Grafos
1 3 4
a1 a4
a5 a6
• Um grafo conexo em
A e um grafo não
conexo em B.
1 3 4
2
a1
a2
a3
a4
a5 a6
5
A
B
Terminologia
Grafo vazio
• É um grafo que contém exclusivamente nós.
Por exemplo, o grafo de jogos antes do início
do campeonato é um grafo vazio.
7
17/02/2018 38Teoria dos Grafos
1 2 3
5
4
6
7
Terminologia
Subgrafo 
• Um subgrafo de um grafo consiste em um
conjunto de nós e um conjunto de arcos que são
subconjuntos do conjunto original de nós e arcos,
respectivamente, nos quais as extremidades de
um arco têm que ser os mesmos nós que no
grafo original.
17/02/2018 39Teoria dos Grafos
um arco têm que ser os mesmos nós que no
grafo original.
1 3 4
2
a1
a2
a3
a4
a5 a6 1 3
2
a1 a4
a5 1 3 4
2
a1
a2
a3
a5 a6
subgrafo subgrafo
Terminologia
Subgrafo 
Subgrafo de G
17/02/2018 40Teoria dos Grafos
Subgrafo de G
Terminologia
Complementariedade
• Um complemento ou inverso de um grafo G é um grafo
H de mesmos vértices, tais que dois vértices de H são
adjacentes se e somente se eles não são adjacentes em
G, são as arestas complementares do grau G.
17/02/2018 41Teoria dos Grafos
7
3
5
1
6
4 7
3
5
1
6
4
Grafo complementar
G H
Terminologia
Complementariedade
17/02/2018 42Teoria dos Grafos
Terminologia
Complementariedade
17/02/2018 43Teoria dos Grafos
Terminologia
Comprimento mínimo
• Um caminho C num grafo é mínimo se não existe
outro caminho que tenha a mesma origem e o
mesmo término que C mas comprimento menor
que o de C.
17/02/2018 44Teoria dos Grafos
A
B
• Qual o caminho mais
curto (em número de
quarteirões) de um
ponto A da cidade
para um ponto B?
Terminologia
Comprimento mínimo
• Se não existe caminho algum de a até b,
podemos dizer que a distância de a até b é
infinita e se a distância de a até b é 0 se e
somente se a = b.
17/02/2018 45Teoria dos Grafos
• Em um grafo orientado as arcos que saem de um
nó chamam-se divergentes (que saem) e os que
entram chamam-se convergentes (que entram).
– Um nó com grau de saída 0 é chamado de sumidouro
e um nó com grau de entrada 0 é chamado de fonte.
Terminologia
Comprimento mínimo
• Qual a distância de cada nó para os demais?
2
17/02/2018 46Teoria dos Grafos
0
3 5
1
4
n0 n1 n2 n3 n4 n5
n0 0 3 1 1 1 2
n1 inf 0 1 inf 1 2
n2 inf 3 0 inf 1 2
n3 inf 3 4 1 1 1
n4 inf 3 3 inf 0 1
n5 inf 1 2 inf 2 0
Terminologia
Comprimento mínimo
• Qual a distância de cada nó para os demais?
a b c d
17/02/2018 47Teoria dos Grafos
Terminologia
Grafo regular
• Diz-se que um grafo qualquer é regular se todos os
seus nós tiverem o mesmo grau.
• Se o grafo for direcionado regular também deve
satisfazer a condição de que o grau de entrada e o grau
de saída de cada nó sejam iguais uns aos outros.
17/02/2018 48Teoria dos Grafos
7
3
5
1
6
4 7
3
5
1
4
Grafo regular Grafo direcionado regular 
Terminologia
Grafo regular
• O grau de saída dout(v) de um nó v corresponde ao
número de arcos divergentes (que saem) de v.
• O grau de entrada din(v) de um nó v corresponde ao
número de arcos convergentes (que chegam) a v.
17/02/2018 49Teoria dos Grafos
Terminologia
Grafo regular
17/02/2018 50Teoria dos Grafos
Terminologia
Kn
• Um grafo simples completo com n nós é
denominado Kn.
5
17/02/2018 51Teoria dos Grafos
1
2 3
4
K5
Terminologia
Grafo bipartido
• O grafo abaixo é simples e não completo pelo fato de
nem todo nó é adjacente a outros nós.
• É possível dividir o grafo em dois conjuntos disjuntos,
{1,2} e {3,4,5} tais que dois nós quaisquer escolhidos
no mesmo conjunto não são adjacentes, mas dois nós
quaisquer escolhidos um em cada conjunto são
17/02/2018 52Teoria dos Grafos
quaisquer escolhidos um em cada conjunto são
adjacentes, sendo assim, esse grafo é bipartido
completo.
K2,3
Terminologia
Grafo bipartido
4 65
• Os conceitos de caminho e ciclo podem ser
aplicados. Se existir um caminho de n0 para nk
então nk é acessível a n0.
17/02/2018 53Teoria dos Grafos
K3,31 2 3
a2a1
a4
a3
a5
Um caminho
4, a1, 2, a2, 6
Um ciclo
4, a1, 2, a3, 5, a4, 1, a5, 4
Terminologia
Grafo bipartido
AMIZADE casa1 casa2 casa3
luz água gás
SERVIÇO
17/02/2018 54Teoria dos Grafos
Grafos isomorfos
• Os gráficos A e B são iguais e o gráfico C
também é igual ao passar através das funções
f1 e f2.
A B C
17/02/2018 55Teoria dos Grafos
f1: 
1->a
2->c
3>b
4->d 
f2: 
a1->e2
A2->e1
Grafos isomorfos
Grafos idênticos embora suas 
aparências são diferentes
17/02/2018 56Teoria dos Grafos
aparências são diferentes
Grafos isomorfos
• Condições para dois grafos não serem
isomorfos:
– Um grafo tem mais nós do que o outro;
– Um grafo tem mais arcos do que o outro;
17/02/2018 57Teoria dos Grafos
– Um grafo tem mais arcos do que o outro;
– Um grafo tem arcos paralelos e o outro não;
– Um grafo tem um laço e o outro não;
– Um grafo é conexo e o outro não;
– Um grafo tem um ciclo e o outro não;
– Existem nós de graus diferentes nos grafos.
Grafos isomorfos
• Os grafos são
isomormos, porque:
– Os grafos possuem o
mesmo número de nós;
– Os grafos possuem o
mesmo número de arcos;
17/02/2018 58Teoria dos Grafos
Os grafos possuem o
mesmo número de arcos;
– O grau dos nós dos dois
grafos são iguais;
– Os dois grafos são
conexos;
– Os dois grafos possuem
ciclo.
Grafos idênticos embora suas 
aparências são diferentes
Grafos isomorfos
• Os grafos são isomormos,
porque:
– Os grafos possuem o mesmo
número de nós;
– Os grafos possuem o mesmo
número de arcos;
– O grau dos nós dos grafos são
17/02/2018 59Teoria dos Grafos
– O grau dos nós dos grafossão
iguais;
– Não possuem nós com graus
de adjacência diferentes;
– Os grafos são conexos;
– Os grafos não possuem laço;
– Os dois grafos possuem ciclo.
Grafos isomorfos
• Os grafos não são
isomormos, porque:
– O grafo “b” tem um nó de
grau 2 adjacente a dois
32 3
3
2
17/02/2018 60Teoria dos Grafos
grau 2 adjacente a dois
nós de grau 3; isso não
acontece no grafo “a”.
2
3
Grafos isomorfos
3
17/02/2018 61Teoria dos Grafos
Grau 4
Todos os nós possuem grau 3
Grafos planares
• Um grafo planar é um grafo que pode ser
representado de modo que seus arcos se
intersectam apenas em nós.
17/02/2018 62Teoria dos Grafos
Grafos planares
• Representações do grafo K4.
17/02/2018 63Teoria dos Grafos
Representações isomorfas de K4
Grafos planares
• Seja G um grafo planar e R uma representação plana
de G em um plano P. Então, as linhas R dividem P em
regiões, as quais são denominadas faces de R.
Existem somente uma face não limitada, chamada de
face externa ou face infinita.
17/02/2018 64Teoria dos Grafos
Grafos planares
• O grafo ‘c’ possui: 5 nós, 9 arcos e 6
faces.
f6externa
f
f2externa f4externa
17/02/2018 65Teoria dos Grafos
f5
f1
f2
f3
f4
f1 f2
f1 f3
Nós=5
Arcos=5
Faces =2
Nós=5
Arcos=7
Faces=4
Nós=5
Arcos=9
faces=6
Grafos planares
• Número de faces e três representações
planares de K4.
17/02/2018 66Teoria dos Grafos
Todos possuem:
Nós=4 ; Arcos=6; Faces=4
Grafos planares
Fórmula de Euler (condição 1)
• Para um grafo planar simples e conexo com ‘n’ nós e ‘a’ arcos:
• Se a representação planar divide o plano em ‘f’ faces, então
• => n – a + f = 2, onde:
• n – é o número de nós;
• a – é o número de arcos;
• f – é o número de faces.
17/02/2018 67Teoria dos Grafos
• f – é o número de faces.
f6externa
f5
f1
f2
f3
f4
Nós=5
Arcos=9
faces=6
5-9+6<=2
Grafos planares
Fórmula de Euler (condição 2)
• Para um grafo planar simples e conexo com ‘n’ nós e
‘a’ arcos:
• Se n>= 3, então
• => a <= 3n – 6, onde:
• n – é o número de nós;
17/02/2018 68Teoria dos Grafos
• n – é o número de nós;
• a – é o número de arcos.
Nós=5
Arcos=9
9<=3*5-6 planar
Grafos planares
Fórmula de Euler
• K5 é um grafo planar simples e conexo
com 5 nós e 10 arcos. K5 é planar?
• Pela condição 2 5
17/02/2018 69Teoria dos Grafos
• a <= 3n – 6
• a <= 3*5 – 6 = 9
• como a=10 => não é planar
1
2 3
4
K5
Representação computacional de grafos
Matriz de adjacência
• Se G é um grafo com nós {1, 2, 3, ..., n}
sua matriz de adjacência é a matriz n X n
cujo elemento ij é o número de arcos
ligando o nó i ao nó j.
17/02/2018 70Teoria dos Grafos
ligando o nó i ao nó j.
n1 n2 n3 n4
n1 1 1 0 1
n2 1 0 1 0
n3 0 1 0 2
n4 1 0 2 0
Representação computacional de grafos
Matriz de adjacência
• Em um grafo direcionado, a matriz de
adjacência G reflete o sentido de
orientação dos arcos.
17/02/2018 71Teoria dos Grafos
n1 n2 n3 n4
n1 1 1 0 0
n2 0 0 1 1
n3 0 1 0 0
n4 0 0 1 0
Representação computacional de grafos
Matriz de incidência
• Se G é um grafo com nós {1, 2, 3, ..., n} e arcos
{a1, a2, a3, ..., m}, sua matriz de incidência é a
matriz n X m cujo elemento ij é o número de
vezes em que o nó i é incidente ao arco.
17/02/2018 72Teoria dos Grafos
a1 a2 a3 a4
n1 1 0 0 2
n2 1 1 1 0
n3 0 1 1 0
n4 0 0 0 0
1
a1
a4
a3a2
2
34
Representação computacional de grafos
Matriz de adjacência e incidência
Matriz de adjacência
N1
N2
N3
N4
N5
n1 n2 n3 n4 n5
17/02/2018 73Teoria dos Grafos
Matriz de incidência
N1
N2
N3
N4
N5
e1 e2 e3 e4 e5 e6
Representação computacional de grafos
Lista de adjacência
• Um grafo com relativamente poucos arcos pode
ser representado de modo mais eficiente
armazenando-se apenas os elementos não
nulos da matriz de adjacência.
17/02/2018 74Teoria dos Grafos
Ponteiro nulo
Representação computacional de grafos
Lista de adjacência
• Para o grafo abaixo, sua lista de
adjacência será:
17/02/2018 75Teoria dos Grafos
Ponteiro nulo
Representação computacional de grafos
Lista de adjacência
• Para o grafo abaixo direcionado e com
pesos, sua lista de adjacência será:
17/02/2018 76Teoria dos Grafos
Ponteiro nulo
Coloração de grafos
• A origem desses problemas é o problema de
colorir um mapa. Seja um mapa contendo
vários países, esse mapa, deve ser colorido
de modo que dois países que têm fronteiras
comum não fiquem com a mesma cor.
17/02/2018 77Teoria dos Grafos
de modo que dois países que têm fronteiras
comum não fiquem com a mesma cor.
Coloração de grafos
• Desenhar um mapa com 4 cores.
17/02/2018 78Teoria dos Grafos
Coloração de grafos
• Associado a qualquer mapa existe um grafo, chamado de
grafo dual do mapa, formado da seguinte maneira:
– Colocar um nó em cada região central do mapa e um arco entre dois
nós que representam países adjacentes. As regiões que se tocam em
um ponto não são consideradas vizinhas.
17/02/2018 79Teoria dos Grafos
• Uma coloração de um grafo é uma atribuição de cor a cada
nó de modo que dois nós adjacentes nunca tenham a
mesma cor.
• O número cromático de um grafo é o menor número de
cores necessários para se obter uma coloração do grafo.
Coloração de grafos
• Criar os grafos duais dos mapas.
17/02/2018 80Teoria dos Grafos
Coloração de grafos
• Grafo dual do mapa.
17/02/2018 81Teoria dos Grafos
Coloração de grafos
• Pelo menos quatro cores são necessárias para
se resolver o problema geral de colorir um
mapa no plano, ou seja, o número cromático de
qualquer grafo planar simples e conexo é no
máximo 4.
17/02/2018 82Teoria dos Grafos
máximo 4.
Obrigado
Prof. Bernardo Caldas
17/02/2018 83Teoria dos Grafos