AULA3a583742

Prévia do material em texto

Santos / SP
SISTEMAS DE 
INFORMAÇÃO
TEORIA DOS GRAFOS
PROF. Dr. PAULO SCHROEDER
Universidade Santa Cecília – Santos / SP
Universidade Santa Cecília – Santos / SP
AULA 3
Universidade Santa Cecília – Santos / SP
Universidade Santa Cecília – Santos / SP
Grau de um vértice
• O grau de um vértice v em G, cuja 
notação é gG (v), é o número de 
arestas incidentes a v, onde cada laço é 
contado duas vezes. Para todo grafo 
vale:
• “a soma dos graus de seus n vértices é 
igual ao dobro do número de arestas” 
(incluindo laços). Figura 14.
Universidade Santa Cecília – Santos / SP
Universidade Santa Cecília – Santos / SP
Universidade Santa Cecília – Santos / SP
Universidade Santa Cecília – Santos / SP
Universidade Santa Cecília – Santos / SP
Universidade Santa Cecília – Santos / SP
• Cardinalidade: (número de elementos de um 
conjunto) Notação: | V | = n e | E | = m
• Se n = 1, dizemos que o grafo é trivial.
• O tamanho de um grafo G (V, E) é dado por | V | + 
| E |.
• O grafo vazio é um grafo tal que | V | + | E | = 0 
(sem arestas e vértices).
• A cardinalidade dos conjuntos V e E é de extrema 
importância para a avaliação da eficiência de 
algoritmos sobre grafos.
• A relação entre duas cardinalidades determina 
grafos densos e grafos esparsos.
• Se os vértices de um grafo têm todos o mesmo 
grau, dizemos que o grafo é regular.
Universidade Santa Cecília – Santos / SP
Universidade Santa Cecília – Santos / SP
• Grafos Conexos:
• Um grafo G (V, E) é dito conexo se, para 
qualquer par de vértices, existe um 
caminho contínuo entre eles. Figura 15.
• Por definição, um grafo trivial (um 
vértice isolado) é um grafo conexo.
Universidade Santa Cecília – Santos / SP
Universidade Santa Cecília – Santos / SP
Universidade Santa Cecília – Santos / SP
Universidade Santa Cecília – Santos / SP
Universidade Santa Cecília – Santos / SP
Universidade Santa Cecília – Santos / SP
Universidade Santa Cecília – Santos / SP
Universidade Santa Cecília – Santos / SP
Universidade Santa Cecília – Santos / SP
Universidade Santa Cecília – Santos / SP
• Grafo Orientado (dígrafo):
• Grafo orientado é aquele cuja 
representação geométrica (em diagrama) 
implica na atribuição de sentido às linhas.
• No caso de grafos orientados usamos o 
termo arco em lugar de aresta, cuja 
notação passa a ser a mesma dos pares 
ordenados; o termo linha pode ser usado 
para designar aresta ou arco.
• Vértices adjacentes aqui, podem receber 
as designações de
• extremidade inicial e extremidade final.
Universidade Santa Cecília – Santos / SP
Universidade Santa Cecília – Santos / SP
• Exemplo 1:
• Numa pequena empresa trabalham 
12 funcionários F1, F2, F3, ...., F12 e 
a relação chefe-subalterno é 
expressa por:
Universidade Santa Cecília – Santos / SP
Universidade Santa Cecília – Santos / SP
• Exemplo 2:
• As unidades C1, C2, C3,....C6 são 
ligadas entre si pela seguinte rede 
de comunicação: quando há uma 
flecha de Ci a Cj significa que é 
possível a comunicação direta de Ci 
a Cj.
Universidade Santa Cecília – Santos / SP
Universidade Santa Cecília – Santos / SP
TP2