698156_Aulas - Unidade 1

Prévia do material em texto

Grafos 
 
 
• CLÓVIS LEMOS TAVARES 
 
 
2013-2 
 
Prof.: Clóvis Lemos Tavares 
Sete pontes de Königsberg 
Prof.: Clóvis Lemos Tavares 
É possível atravessar todas as pontes sem repetir nenhuma? 
 
Euler, em 1736, provou que não existia caminho que possibilitasse tais restrições 
 
Apenas seria possível se houvesse exatamente zero ou dois pontos de onde 
saísse um número ímpar de caminhos. A razão de tal coisa é que de cada ponto 
deve haver um número par de caminhos, pois será preciso um caminho para 
"entrar" e outro para "sair" 
Grafo 
Prof.: Clóvis Lemos Tavares 
Grafo é representado como um conjunto de pontos (vértices) ligados por retas 
(as arestas). Dependendo da aplicação, as arestas podem ser direcionadas, e são 
representadas por "setas" 
 
Estruturas chamados de grafos, 
G(V,A), onde V é um conjunto não 
vazio de objetos denominados 
vértices e A é um conjunto de pares 
não ordenados de V, chamado 
arestas. 
Grafo com 4 vértices e 6 arestas. 
É um grafo completo, conexo e 
planar 
Tipos de Grafos 
Prof.: Clóvis Lemos Tavares 
Um grafo direcionado (também chamado digrafo ou quiver) consiste de 
Arestas ligadas a vértices onde o alvo da aresta é direcionada 
 
Grafo simples, as arestas não tem alvo direcionado. 
Um grafo com 6 vértices e 7 arestas 
Um digrafo com 11 vértices e 9 arcos 
Representação gráfica (layout do grafo) 
Prof.: Clóvis Lemos Tavares 
Os grafos são geralmente representados graficamente da seguinte maneira: é 
desenhado um círculo para cada vértice, e para cada aresta é desenhado um arco 
conectando suas extremidades. Se o grafo for direcionado, seu sentido é indicado 
na aresta por uma seta 
O grafo de exemplo exibido à direita é 
um grafo simples com o conjunto de 
vértices V = {1, 2, 3, 4, 5, 6} e um 
conjunto de arestas E = { {1,2}, {1,5}, 
{2,3}, {2,5}, {3,4}, {4,5}, {4,6} } 
Conectividade 
Prof.: Clóvis Lemos Tavares 
• Dois vértices são considerados adjacentes se uma aresta existe entre eles; 
 
• A valência (ou grau) de um vértice é o número de arestas incidentes a ele, 
com loops contados duas vezes; 
 
• Em um dígrafo, distingue-se o grau de saída (o número de arestas saindo de 
um vértice) e o grau de entrada (o número de arestas entrando em um 
vértice); 
 
• O grau de um vértice é igual à soma dos graus de saída e de entrada; 
 
• Dois vértices são considerados adjacentes se uma aresta existe entre eles; 
 
• A ordem de um grafo é o numero de vértices que ele possui; 
 
 
Grafo Simples 
Prof.: Clóvis Lemos Tavares 
É um grafo não direcionado, sem 
laços e que existe no máximo 
uma aresta entre quaisquer dois 
vértices (sem arestas paralelas) 
Grafo Completo 
Prof.: Clóvis Lemos Tavares 
 
 
é o grafo simples em que, para cada vértice do grafo, existe uma 
aresta conectando este vértice a cada um dos demais. Ou seja, 
todos os vértices do grafo possuem mesmo grau. 
Grafo Nulo / Vazio 
Prof.: Clóvis Lemos Tavares 
Grafo nulo é o grafo cujo 
conjunto de vértices é vazio. 
 
Grafo vazio é o grafo cujo 
conjunto de arestas é vazio. 
Grafo Regular 
Prof.: Clóvis Lemos Tavares 
É um grafo onde cada vértice tem 
o mesmo número de adjacências 
Laço 
Prof.: Clóvis Lemos Tavares 
Laço (loop) num num digrafo é 
uma aresta e em E cujas 
terminações estão no mesmo 
vértice. 
Ciclo 
(ou circuito) é um caminho que começa e acaba com o mesmo vértice. Ciclos de 
comprimento 1 são laços. No grafo acima, (1, 2, 3, 4, 5, 2, 1) é um ciclo de 
comprimento 6. Um ciclo simples é um ciclo que tem um comprimento pelo menos de 
3 e no qual o vértice inicial só aparece mais uma vez, como vértice final, e os outros 
vértices aparecem só uma vez. No grafo acima, (1, 5, 2, 1) é um ciclo simples. Um 
grafo chama-se acíclico se não contém ciclos simples. 
Multigrafo 
Prof.: Clóvis Lemos Tavares 
é um grafo que permite múltiplas 
arestas ligando os mesmos 
vértices (arestas paralelas) 
Multigrafo com laços (azul) e arestas múltiplas 
(vermelho) 
Árvore 
Prof.: Clóvis Lemos Tavares 
é um grafo simples acíclico e conexo. Às vezes, um 
vértice da árvore é distinto e chamado de raiz. 
Árvores são comumente usadas como estruturas 
de dados em informática (veja estrutura de dados 
em árvore). 
Uma árvore com 5 arestas e 6 vértices. 
Grafo bipartido 
Prof.: Clóvis Lemos Tavares 
é o grafo cujos vértices podem ser divididos em dois conjuntos, nos quais não 
há arestas entre vértices de um mesmo conjunto. Para um grafo ser bipartido 
ele não pode conter circuitos de comprimento ímpar. 
Grafo bipartido completo é o grafo bipartido, 
cujo qualquer vértice do primeiro conjunto é 
adjacente a todos vértices do segundo 
conjunto 
Grafo cromático 
Prof.: Clóvis Lemos Tavares 
Teorema das quatro cores é baseado no 
problema das cores necessárias para se colorir 
um mapa sem que os países vizinhos 
compartilhem da mesma cor. Transformando o 
mapa em um grafo pode-se provar que pode-
se representar qualquer mapa (um grafo 
planar) com apenas 4 cores (4 partições). 
Abstração de um mapa com 4 cores usando grafos 
Digrafo 
Prof.: Clóvis Lemos Tavares 
Um grafo orientado, grafo dirigido, grafo direcionado ou digrafo é um par G=(V,A) 
Um conjunto V, cujos elementos são chamados vértices ou nodos, 
um conjunto A de pares ordenados de vértices, chamados arcos, arestas 
direcionadas, ou setas . 
Ele difere de um grafo não-direcionado comum, em que o último é definido em 
termos de pares não ordenados de vértices, que são normalmente chamados arestas. 
Por exemplo, ser possível ir de um nó A para um nó B, mas não o contrário através 
desse arco. 
Um grafo orientado (direcionado). 
Matriz de incidência 
Prof.: Clóvis Lemos Tavares 
Matriz de adjacência 
Prof.: Clóvis Lemos Tavares 
Algotirmos de busca em grafos 
Prof.: Clóvis Lemos Tavares 
Busca em largura 
Prof.: Clóvis Lemos Tavares 
Prof.: Clóvis Lemos Tavares 
Busca em profundidade