Grafos01

Prévia do material em texto

2
Conceitos Básicos
� Em grafos ocorrem dois 
tipos de elementos:
� Vértices ou nós;
� Arestas ou arcos.
G1(V1, E1)
3
Conceitos Básicos
� Grafo é um coleção de 
vértices e arestas.
� Vértice é um objeto 
simples que pode ter 
nomes e outros 
atributos.
� Aresta é uma conexão 
entre dois vértices.
G2(V2, E2)
4
Representação
� Um conjunto V é o conjunto de vértices de 
um grafo.
� V2 = {v1, v2, v3, v4}
� Um conjunto E é o conjunto de arestas de 
um grafo.
� E2 = {e1, e2, e3, e4, e5}
� E2 = {(v1, v3), (v3, v1), (v1, v2), (v2, v1), (v2, v4), (v4, 
v2), (v1, v4), (v4, v1), (v3, v4), (v4, v3)}
5
Ordem de um Grafo
� O número de vértices de um grafo é dado por |V|, 
onde V é o conjunto de vértices de um grafo.
� O número de arestas de um grafo é dado por |E|, 
onde E é o conjunto de arestas de um grafo.
� A ordem de um grafo G é dada pela cardinalidade 
do conjunto de vértices, ou seja, pelo número de 
vértices de G (|V|).
� Ordem(G1) = |V1| = 6
� Ordem(G2) = |V2| = 4
6
Conceitos Básicos
� Um grafo não-direcionado G é um par (V, E), 
onde:
� V é o conjunto de vértices e V ≠ ∅;
� E consiste no par de vértices não direcionado, 
isto é, (vi, vj) e (vj, vi) são a mesma aresta.
7
Conceitos Básicos
� Grafo direcionado ou digrafo G é 
um par (V, E), onde V é o conjunto 
finito de vértices e V ≠ ∅ e E é
uma relação binária em V, ou seja, 
as arestas (vi, vj) ≠ (vj, vi).
� Arestas têm uma direção associada.
8
Conceitos Básicos
� Se (u, v) é uma aresta em um grafo 
direcionado G = (V, E), dize-se que (u, v) é 
incidente do ou sai do vértice u e é incidente 
no ou entra no vértice v.
� Saem do vértice 2
� (2, 2), (2, 4) e (2, 5)
� Entram no vértice 2
� (1, 2) e (2, 2)
9
Conceitos Básicos
� Se (u, v) é uma aresta em um grafo não 
direcionado G = (V, E), dize-se que (u, v) é 
incidente nos vértices u e v.
� Incidem no vértice 2
� (1, 2) e (2, 5)
10
Conceitos Básicos
� Em grafos não direcionados, 
dois vértices são ditos 
adjacentes se eles são 
pontos finais de uma mesma 
aresta.
� V1 e V2 são adjacentes, pois 
são pontos finais da aresta e2
� V2 e V3 não são adjacentes, 
pois não são pontos finais de 
nenhuma aresta
11
Conceitos Básicos
� Em um grafo direcionado, um 
vértice v é adjacente a um 
vértice u se o par (u, v) é um 
arco, ou seja, se existe um arco 
que sai de u e entra em v.
� O vértice 4 é adjacente ao vértice 2 
e ao vértice 5, mas não é adjacente 
aos vértices 1, 3 e 6.
12
Conceitos Básicos
� Loop ou laço:
� Uma aresta associada a um par 
de vértices (vi, vi).
� Somente em grafos direcionados.
� Arestas paralelas:
� Quando mais de uma aresta está 
associada ao mesmo par de 
vértices.
13
Conceitos Básicos
� Duas arestas não paralelas são adjacentes 
se elas são incidentes a um vértice comum.
As arestas (v1, v2) e (v2, v5) são 
adjacentes, pois incidem ao vértice 
v2 comum a ambas.
As arestas destacadas não são
adjacentes, pois são paralelas. 
14
Conceitos Básicos
� Grafo simples:
� Um grafo que não possui loops e nem arestas 
paralelas.
Não é um 
grafo simples
Não é um 
grafo simples
É um grafo 
simples
15
Conceitos Básicos
� Um grafo ponderado é um grafo no qual 
existe um número associado a cada aresta.
� O número associado a uma aresta é 
chamado peso.
16
Conceitos Básicos
� Um grafo G(V, E) é dito ser rotulado em 
vértices ou arestas quando a cada vértice ou 
aresta estiver associado um rótulo.
17
Grau de um Vértice
� Grau de um vértice v, representado por grau(v), em 
um grafo não direcionado é o número de arestas 
que incidem em v.
� De acordo com o grau, os vértices se classificam 
em:
� Vértice par – grau par;
� Vértice ímpar – grau ímpar;
� Vértice isolado – grau zero.
� Sequência de graus de um grafo consiste em 
escrever em ordem crescente os graus dos seus 
vértices.
18
Grau de um Vértice
v6 é um vértice isolado: grau(v6) = 0
v2 é um vértice par: grau(v6) = 4
v3 é um vértice ímpar: grau(v3) = 4
Sequência de graus:
0, 1, 2, 2, 3, 4
19
Grau de um Vértice
� Em um grafo direcionado, o grau de saída de 
um vértice é o número de arestas que saem 
dele.
� O grau de entrada é o número de arestas 
que entram nele.
� O grau de um vértice em um grafo 
direcionado é o seu grau de entrada somado 
ao seu grau de saída.
20
Grau de um Vértice
Grau de entrada do vértice 5: 2
Grau de saída do vértice 5: 1
Grau do vértice 5: 3
21
Grau de um Vértice
� TEOREMA 1. A soma dos graus de todos os 
vértices de um grafo G é duas vezes o número 
de arestas de G.
� TEOREMA 2. O número de vértices de grau 
ímpar em um grafo é par.
∑
=
=
||
1
||2)(V
i
Evgrau i
∑∑ ∑ +=
=
ímparkparj vgrau
k
V
i
vgrau
ji vgrauvgrauvgrau
)(
||
1
)(
)()()(
22
Grau de um Vértice
Número de vértices de grau ímpar = 2 (v3 e v5)
6212012342)(6
1
×==+++++=∑
=i i
vgrau
23
Definições
� Um grafo no qual todos os 
vértices possuem o mesmo 
grau é chamado de grafo 
regular.
� Um vértice com nenhuma 
aresta incidente é chamado 
de vértice isolado.
� Um vértice de grau 1 é 
chamado de vértice 
pendente ou terminal.
Grafo Regular
Vértice 4 é um vértice isolado.
Os vértices 3 e 6 são vértices pendentes.
24
Definições
� Um grafo sem nenhuma aresta é chamado 
de grafo nulo.
� Todos os vértices em um grafo nulo são 
vértices isolados.
� Um vértice v é uma fonte se o grau de 
entrada de v é igual a zero.
� Um vértice v é um sumidouro se o grau de 
saída de v é igual a zero.
25
Definições
� Um grafo completo é um grafo simples em que 
todo vértice é adjacente a todos os outros 
vértices.
� O grafo completo de |V| vértices é 
freqüentemente denotado por Kn, onde n = |V|.
� O número de arestas de um grafo Kn é dado 
por:
2
)1|(|||
)!2|(|!2
|!|
2
||
−
=
−
=




 VV
V
VVC
26
Grafos Completos
27
Definições
� Um grafo G = (V, E) é dito ser bipartido
quando seu conjunto de vértices V puder ser 
particionado em dois subconjuntos V1 e V2
tais que toda aresta de G une um vértice de 
V1 a outro de V2. V1
V2
28
Definições
� Grafo conexo: existe pelo menos um caminho 
entre todos os pares de vértices de G.
� Um grafo desconexo consiste de 2 ou mais 
grafos conexos. Cada um dos subgrafos
conexos é chamado de componente.