Teoria de Grafos
Trabalho realizado por:
Cátia Cardoso
Filipe Silva
Sandra Cunha
Um pouco da história de Teoria de
Grafos
Tudo começou no século XVIII, na
cidade medieval de Königsberg,
situada no leste europeu.
Königsberg é banhada pelo rio
Pregel, que a divide em quatro áreas
de terra ligadas umas às outras por
sete pontes, as famosas “sete pontes
de Königsberg”.
Durante muito tempo, os habitantes daquela
cidade perguntavam-se se era possível cruzar as sete
pontes numa caminhada contínua, sem que se
passasse duas vezes por qualquer uma delas.
Leonhard Euler estudou este problema em 1736
(como veremos, mais adiante) e a partir daí,
desenvolveu toda a teoria que é hoje utilizada nas mais
diversas áreas que envolvem tarefas: a Teoria de
Grafos.
Conceitos básicos
Um grafo G(V,A) é definido pelo par de conjuntos não vazios V e A,
onde:
V- conjunto dos vértices do grafo;
A- conjunto de pares ordenados a= (v,w), v e w  V: as arestas do
grafo.
Vértices adjacentes: são aqueles que estão ligados por uma mesma
aresta.
Aresta incidente: é aquela que liga dois vértices distintos.
Exemplo:
Encontre o caminho até ao centro representado por *, e a respectiva saída.
Resolução:
Grau de um vértice é igual ao número de arestas nele incidentes.
Grafo Regular é aquele em que todos os vértices têm o mesmo grau.
Grafo Completo é aquele em que todos os vértices são adjacentes.
Um grafo G diz-se um Grafo Bipartido se o conjunto dos seus vértices
admitir uma partição {V1, V2 } de tal forma, que toda a aresta de G une
um vértice de V1 e um vértice de V2.
Um grafo planar é um grafo que pode ser desenhado no plano de forma
a que as arestas não se cruzem.
Exemplo 2:
Pretendemos ligar três casas A, B e C a três utilitários, gás (g), água
(a) e electricidade (e). Por razões de segurança convém que as ligações
não se cruzem. Será possível?
Representação do grafo:
Trata-se de um grafo regular: todos
os vértices têm grau 3;
É bipartido, basta considerar a
partição V1= {A,B,C} e V2={g, a, e};
Não é possível fazer as ligações sem estas se cruzarem. O que
pretendíamos era um grafo planar, mas pelo teorema de
Kuratowsky, um grafo K3,3 nunca é planar.
Um grafo G’ diz-se um subgrafo de um grafo G, se o conjunto dos
vértices e das arestas de G’ são subconjuntos do conjunto de vértices e
do conjunto de arestas, respectivamente, de G.
Dois grafos G1, G 2, dizem-se isomorfos se existe uma bijecção entre os
conjuntos dos vértices dos dois grafos, preservando a adjacência desses
vértices, ou seja, se dois vértices são adjacentes em G1, as suas imagens
pela referida bijecção são adjacentes em G2.
Um grafo dirigido é um grafo em cujas arestas é definido um sentido.
Exemplo 3:
Regule com semáforos a circulação automóvel de modo a evitar
colisões num cruzamento com dois sentidos e possibilidade de virar à
esquerda e à direita. Não é permitido fazer uma volta de 180º.
Resolução:
Quando os semáforos da rua 1 estão
verdes:
Quando os semáforos da
rua 2 estão verdes:
Quando o semáforo da rua 3 está
verde:
Quando o semáforo da rua 4 está
verde:
Cada situação é um subgrafo da situação global que representa todas
as possibilidades de deslocamento no cruzamento em causa;
Em cada situação os grafos subjacentes aos grafos dirigidos são
isomorfos aos restantes;
Caminho é uma sucessão de vértices e arestas tal que cada aresta liga
o vértice que a precede ao vértice que a segue, não repetindo arestas.
Passeio é um caminho onde pode haver repetição de arestas e de
vértices.
Ciclo ou circuito é um caminho fechado.
Grafo conexo é aquele onde entre qualquer par de vértices existe
sempre um caminho que os une.
Grafos Eulerianos
Leonhard Euler
1707-1783
O que é um circuito de Euler?
É um caminho fechado em que cada aresta é percorrida uma só vez.
Exemplo:
u1, u2, u3, u4, u5, u3, u1, u6, u2, u7, u3, u6, u7, u1
Trilho (caminho) euleriano
É aquele que passa por todas as arestas uma única vez.
Grafo euleriano
É um grafo que possui pelo menos um circuito de Euler.
Teorema de Euler
Um grafo G é euleriano se e somente se G é conexo e cada vértice de G
tem grau par.

Se um grafo tiver um vértice qualquer de grau ímpar então é impossível
encontrar um circuito de Euler.
Mais alguns teoremas relevantes...
Teorema:
Um grafo conexo G, é um grafo euleriano se e somente se ele pode ser
decomposto em ciclos.
Teorema:
Se um grafo G tiver mais de dois vértices de grau ímpar então não
existe nenhum trilho euleriano.
Teorema:
Se G for um grafo conexo e tiver apenas dois vértices de grau ímpar
então ele tem pelo menos um trilho euleriano (às vezes mais).Qualquer
trilho tem de começar num dos vértices de grau ímpar e terminar no
outro.
Quando sabemos que um grafo admite circuito de Euler, como
fazemos para o encontrar?
Podemos fazê-lo por:
 tentativa-erro;
 Método de Fleury.
Método de Fleury:
1. Verificar se o grafo é conexo e se todos os vértices têm grau par;
2. Começar em qualquer vértice;
3. Percorrer uma aresta se:
a) Não é uma ponte;
b) Não houver outra alternativa;
4. Numerar as arestas pela ordem que são percorridas;
5. Quando não houver mais arestas a percorrer o processo termina.
Eulerizar um grafo
Quando não temos um caminho, nem um ciclo euleriano e
pretendemos percorrer o grafo repetindo o menor número de arestas
possíveis, o melhor é eulerizar o grafo.
Eulerizar um grafo é acrescentar as arestas necessárias de forma a que
todos os vértices de grau ímpar se tornem vértices de grau par.
Nota: É de salientar, que não se pode acrescentar arestas não existentes,
apenas podemos duplicar as arestas já existentes.
 Ainda uma melhor eulerização:
Grafo inicial:
Grafo eulerizado:
Aplicações:
Problema do desenho da casa
No desenho ao lado, uma criança diz ter posto a
ponta do lápis numa das bolinhas e sem levantar o lápis
traçou as linhas que formam o desenho da casa, traçando
cada linha uma única vez e voltando ao ponto de partida.
A mãe da criança acha que ela a enganou, pois não foi
capaz de achar nenhuma sequência que pudesse
produzir tal resultado.
Quem terá razão a criança ou a mãe?
Resolução:
Este problema, consiste simplesmente, em verificar se o grafo
admite um circuito de Euler.
A resposta é negativa (e assim, a criança enganou a mãe). No
entanto, é possível encontrar um caminho de Euler:
ADCBFDECFAB.
O problema das 7 pontes de Königsberg
Como já vimos anteriormente, os habitantes de Königsberg
pretendiam arranjar uma forma de cruzar as sete pontes numa caminhada
contínua sem que passassem duas vezes por qualquer uma delas e
regressando ao ponto de partida.
Resolução:
Vamos substituir o desenho, por um grafo:
Matematicamente, o que pretendemos é um caminho que passe por
todas as arestas uma única vez, regressando ao ponto de partida, portanto
um circuito de Euler.

Atendendo ao Teorema de Euler (que nos diz que para um grafo ser
euleriano é necessário que todos os vértices tenham grau par), verificamos
de imediato que o grafo em causa não possui circuitos de Euler, logo o
problema não tem solução.
O problema do controle dos parquímetros
Precisamos de organizar um giro de um agente para o controle dos
parquímetros de uma determinada zona, de modo a verificar violações
das regras de estacionamento, evitar o vandalismo e roubo. O agente
terá de gastar o mínimo de tempo possível no seu giro, para poder
repeti-lo com mais frequência.
A nossa zona de estudo: tem ruas, um bloco residencial e uma zona
verde.
Problema:
Pretende-se procurar o percurso mais eficiente para um agente,
que anda a pé e tem a missão de vigiar os parquímetros da área.Tendo
duas finalidades em mente:
 o agente tem que cobrir todos os passeios que têm parquímetros,
sem dar mais passos do que os necessários;
 o percurso deve acabar no mesmo ponto onde começa - o local onde
estaciona o carro patrulha.
Resolução:
Para começar, consideremos que só há dois blocos que têm
parquímetros:
Suponhamos que o agente começa e acaba o seu giro no canto
superior esquerdo do bloco da esquerda.
Como esquema do nosso problema temos o seguinte grafo:
Um possível circuito a percorrer, supondo que o agente parte de A
e volta a A, é o seguinte:
Observações:
É de salientar, que o que pretendíamos era um percurso óptimo, isto
é, um circuito de Euler (circuito em que cada aresta é percorrida uma
só vez);
Logo à partida, podíamos inferir que este grafo possuía um circuito
de Euler, já que todos os vértices são de valência par (Teorema de
Euler);
O estudo em causa pode assim ser alargado a uma área com mais ruas e
outras condições, as respostas seriam dadas por um estudo análogo ao
realizado.
Existem outras profissões/tarefas em que se pode enquadrar este tipo de
problema:
 Distribuição do jornal;
 Vendedor ambulante;
 Leitura dos contadores da luz.
Grafos Hamiltonianos
Sir William Rowan Hamilton
1805-1865
No caso dos circuitos de Euler, o nosso problema consistia em
encontrar caminhos, a começar e a acabar no mesmo vértice, que
passassem por todas as arestas apenas uma vez. Mas podíamos visitar
os vértices tantas vezes quantas quiséssemos. O que acontece se
trocarmos os papéis das arestas e dos vértices?
Caminho hamiltoniano é um caminho que passa exactamente uma
vez por cada vértice de um grafo, não sendo necessário percorrer
todas as arestas.
Ciclo hamiltoniano é um caminho hamiltoniano que começa e
termina no mesmo vértice.
Um grafo G é dito hamiltoniano se contém um ciclo hamiltoniano.
Quais são as condições necessárias e
suficientes para determinar se um grafo
é hamiltoniano?
Infelizmente, não conhecemos um método para determinar se um
grafo qualquer tem ou não um circuito hamiltoniano.
Teorema de Ore:
Uma condição suficiente (mas não necessária) para que um grafo G
seja hamiltoniano é que a soma dos graus de cada par de vértices não
adjacentes seja no mínimo n, onde n é o número de vértices.
Teorema de Dirac:
Uma condição suficiente (mas não necessária) para que um grafo G
seja hamiltoniano é que o grau de todo vértice de G seja no mínimo n/2.
Exemplo:
Não são muito informativos, pois o que eles dizem intuitivamente, é que
se um grafo contém muitas arestas e estas são bem distribuídas, ele é
hamiltoniano.
Ciclos hamiltonianos em grafos completos
Grafo completo com n vértices tem n(n-1)/2 arestas.
Todo o grafo completo que contém mais de dois vértices é um grafo
hamiltoniano.
Teorema:
Num grafo completo com n vértices podem ser escolhidos (n-1)!
Circuitos de Hamilton.
Agora o problema não é saber se há um circuito de Hamilton, mas sim,
como vamos lidar com tantos!
Problema do Caixeiro Viajante (PCV)
Determinação da viagem do custo mínimo, partindo e regressando ao
mesmo local;
Principais aplicações:
- entrega de encomendas;
- recolha de objectos;
- planificação de viagens;
- leitura de contadores…
Métodos para resolver PCV
Método 1: Algoritmo da Força Bruta

Lista de todos os circuitos possíveis;

Calcula-se o custo total de cada circuito;

Escolhemos um circuito com o custo total mínimo (Circuito Óptimo
de Hamilton).
Método 2: Algoritmo do Vizinho mais Próximo
- Escolhemos um ponto de partida (casa);
- De entre as arestas adjacentes escolhemos a que tem menor peso, e
partimos para o vértice correspondente (vizinho mais próximo);
- Continuamos a construir o circuito, indo sempre para o vizinho mais
próximo, a não ser que a aresta que o liga feche um circuito e havendo ainda
vértices por visitar. E prosseguimos até que todos os vértices sejam
visitados;
-Chegando ao último vértice, regressamos a “casa”.
A, C, E, D, B, A
773 EUROS
Os resultados são diferentes;
O Algoritmo da Força Bruta é conhecido como um algoritmo ineficiente.
Restringe-se a pequenos problemas.
O Algoritmo do Vizinho mais Próximo é um exemplo de algoritmo
eficiente. Contudo o resultado pode estar longe de ser um circuito
óptimo.
Surgem então os Algoritmos Aproximados, para tentar solucionar os
problemas atrás mencionados:
- lentidão;
- solução rápida mas apenas aproximada;
O Algoritmo Repetitivo do Vizinho mais Próximo
O Algoritmo da Ligação mais Económica
Método 3: O Algoritmo Repetitivo do Vizinho mais
Próximo
-Seja X um vértice qualquer. Apliquemos o algoritmo do vizinho mais
próximo, sendo X o ponto de partida. E calculemos o custo total do
circuito;
-Repetimos o processo usando os outros vértices como “casa”;
-Dos circuitos hamiltonianos obtidos escolhemos o que tem custo
mínimo. Se à partida estiver estabelecido o vértice de partida e não
coincidir com aquele do qual partimos, basta reescrever o circuito
tomando como ponto de partida o que estava pré-estabelecido.
Pelo Algoritmo do Vizinho mais Próximo tínhamos obtido A, D, B, C,
E, A com custo total de 773 euros;
Repetindo o processo para os outros vértices obtemos:
- para o vértice B temos: B, C, A, E, D, B com custo total = 722;
- para o vértice C temos: C, A, E, D, B, C com custo total = 722;
- para o vértice D temos: D, B, C, A, E, D com custo total = 722;
- para o vértice E temos: E, C, A, D, B, E com custo total = 741;
Os vértices com circuitos óptimos têm como vértice inicial B, C ou D.
Portanto pode-se escolher qualquer um deles.
Escolhemos o que tem como vértice inicial o B. Mas tem que começar
em A, logo reordenando temos: A, E, D, B, C, A.
Método 4: Algoritmo da Ligação mais Económica
- Escolher a aresta com menor peso. Marcar a aresta correspondente
com uma cor, por exemplo vermelho;
- Escolher a ligação mais económica que se segue, e assinalar a
vermelho;
- Continuar a escolher a ligação mais económica disponível. Marcar a
aresta correspondente a vermelho excepto quando:
a)esta aresta fecha um circuito;
b)esta aresta parte de um vértice ao qual já estão ligadas
duas outras arestas anteriormente escolhidas;
-Quando não existirem mais vértices para ligar, fecha-se o circuito
que temos vindo a assinalar a vermelho.
Colorir um grafo
O número cromático de um grafo é o número mínimo necessário para
colorir os seus vértices de forma a que dois vértices adjacentes não
possam ter a mesma cor.
O número cromático das arestas de um grafo é o número mínimo de
cores necessárias para colorir as arestas de G, de forma a que as arestas
incidentes num mesmo vértice não possam ter a mesma cor.
Snark é um grafo cujo número cromático para as arestas é igual a
quatro.
Exemplo:
Uma companhia industrial deseja armazenar sete diferentes
produtos farmacêuticos C1, C2, ..., C7, mas alguns não podem ser
armazenados juntos por motivos de segurança. A tabela seguinte mostra
os produtos que não podem estar no mesmo local. Encontre o número
mínimo de localizações necessárias para colocar estes produtos.
Primeira forma de resolver (coloração dos vértices)
Resposta:
O número cromático deste grafo é 4. Precisamos de quatro gavetas
para colocar os medicamentos. Uma combinação possível dos
medicamentos compatíveis é: C2C5, C3C6, C4C7, C1.
Esta combinação não é única, pois a disposição dos produtos
compatíveis pode variar consoante a coloração do grafo.
Segunda forma de resolver (coloração das arestas)
Observação: O número
cromático das arestas deste
grafo é 4, contudo, a definição
de número cromático das
arestas diz-nos, que para colorir
um grafo devemos usar o
número mínimo de cores. Neste
caso, a aresta preta devia ser
verde. Logo o número cromático
das arestas será 3.
Resposta:
Preciso de quatro gavetas para colocar os produtos, temos três
combinações possíveis para arrumar os medicamentos compatíveis. Por
exemplo, a combinação dada pela cor verde: C1C3, C2C5, C4C7, C6.
Teorema das quatro cores
Qualquer mapa de regiões, desenhado num plano pode ser colorido
com quatro cores de modo a que as regiões adjacentes (arestas comuns
ou parcialmente comuns) fiquem com cores diferentes.
Exemplo:
Mapa da Europa
Se a cada aresta de um grafo se associar um número natural, chamado
peso, ficamos com um grafo “pesado”.
Árvore é um grafo conexo e sem ciclos.
Dado um grafo G, uma árvore geradora de G é um subgrafo G’ de G,
tal que G’ é uma árvore e possui todos os vértices de G.
Num grafo “pesado” G, a árvore geradora mínima é uma árvore
geradora de G, para a qual é mínima a soma dos pesos das arestas
envolvidas.
Exemplo:
O concelho de uma cidade, que possui um orçamento muito
limitado, quer pavimentar algumas estradas de forma a que se possa ir de
qualquer cidade para qualquer cidade só por estrada pavimentada.
Directa ou indirectamente. A autarquia quer minimizar o número total de
quilómetros a pavimentar. Procure a rede de estradas a pavimentar que
preencherá todos estes requisitos.
Algoritmo de Kruskal
1. Escolher a aresta menos pesada: AB
2. Das restantes arestas escolher a aresta
menos pesada: BD
3. Continuar sucessivamente mas sem
nunca escolher uma aresta que feche
um ciclo.
Peso total: 88Km
Algoritmo de Prim
1. Começar num vértice qualquer: A
2. Ir para o vizinho mais “próximo”: B
3. Daí para o vizinho “mais próximo” e assim sucessivamente até
chegar ao último, (sem fechar um ciclo).
Observação: Por vezes este método pode levar a um beco sem saída, que é
o que acontece se começarmos em A: AB, BD, DC. Não podemos
continuar senão fechamos o ciclo.
Uma solução poderá ser:
AB, BD, DC, BF, FE, EG.
FIM