Upload
olivia-do-amaral-miranda
View
219
Download
1
Embed Size (px)
Citation preview
UFESTeoria dos Grafos
Alguns conceitos de Teoria dos Grafos para Fluxo em Redes
Maria Claudia Silva [email protected]
Mestrado em Informática
UFESTeoria dos Grafos
Motivação
• Definições e terminologias usadas em diferentes formulações e algoritmos de fluxo em redes
UFESTeoria dos Grafos
Discutiremos...
• Definições e terminologias de Teoria dos Grafos para fluxo em redes
• Estruturas de Dados para representação de Redes
• Transformações de modelos de problemas de fluxo em redes
UFESCC/EC/Mestrado Teoria dos Grafos
Conceitos Básicos
• O que é um grafo?G=(V, E)
V = {v1, ..., vn} E = {e1, ..., em}
vértices arestas
ek = {vi,vj}, k = 1,...,m, i,j = 1,..., n
vi e vj são ditos extremos de ek
UFESCC/EC/Mestrado Teoria dos Grafos
ExemploG = (V, E)
V = {a,b,c,d,e}E = {{a,b},{a,c},{b,c},{b,d},{c,d},{c,e}} = { e1, e2, e4, e5, e7, e9}
a
e
b c
d
G = (V, E)
V = {a,b,c,d,e}E = {{a,b},{a,c},{b,b},{b,c},{b,d},{c,d},{c,d},{c,d},{c,e}} = { e1, e2, e3, e4, e5, e6, e7, e8, e9}
Grafo simples
Multigrafo
e1 e2
e3
e4
e5
e6 e7e8
e9
UFESCC/EC/Mestrado Teoria dos Grafos
Conceitos
• Uma aresta do tipo {vi,vi} é denominada laço. – A aresta e3 do exemplo anterior é um laço.
• Arestas que possuem os mesmos vértices extremos são ditas paralelas.– As arestas e6, e7 e e8 do exemplo anterior são
paralelas.• Um grafo que possui arestas paralelas é
denominado multigrafo.• Um grafo sem laços nem arestas paralelas é
denominado grafo simples.
UFESCC/EC/Mestrado Teoria dos Grafos
Conceitos
• Os extremos de uma aresta são ditos incidentes com a aresta, e vice-versa.
u v
e
u e v são incidentes a e e é incidente a u e a v
UFESCC/EC/Mestrado Teoria dos Grafos
Conceitos
• Dois vértices que são incidentes a uma mesma aresta são ditos adjacentes.
• Duas arestas que são incidentes a um mesmo vértice são ditas adjacentes.
u v
eu e v são adjacentes
e1 e e2 são adjacentes
ue2
e1
UFESCC/EC/Mestrado Teoria dos Grafos
Observação
O conceito de incidência ou adjacência
é importante para a representação
da estrutura de um grafo como um diagrama
UFESCC/EC/Mestrado Teoria dos Grafos
Conceitos
• O número de vértices de um grafo G é denotado por n = |V|. O valor n também é conhecido como ordem de G
• O número de arestas de um grafo é denotado por m = |E|
• Se n e m são finitos, o grafo é finito. Caso contrário é dito infinito.– Exemplo de grafo infinito: malhas
UFESCC/EC/Mestrado Teoria dos Grafos
Conceitos
• O número de arestas incidentes a um vértice v é denominado grau(v) e representado por d(v).
• Grau também é conhecido como valência.
a
e
b c
d
d(a) = 3d(b) = 5d(c) = 4d(d) = 2d(e) = 2
UFESCC/EC/Mestrado Teoria dos Grafos
Conceitos• Vértice isolado é o vértice que não possui arestas
incidentes (grau nulo)• Vértice folha ou terminal é o vértice que possui grau
1• Vizinhos de um vértice são os vértices adjacentes a
ele.
b
a
cd
e
d é um vértice folha e e é um vértice isoladob e c são vizinhos de a
UFESCC/EC/Mestrado Teoria dos Grafos
Conceitos
• Pares de vértices (ou de arestas) não adjacentes são denominadas independentes.
• Um conjunto de vértices (ou arestas) é independente se nenhum par de seus elementos é adjacente.
UFESCC/EC/Mestrado Teoria dos Grafos
Exemplo
a
b c
d
f
ege10
e1 e2
e3
e4e5
e6e7
e8
e9
•e1 e e5 são independentes•a e d são independentes•{b,e,g} é um conjunto independente•{e1, e5 } é um conjunto independente
UFESCC/EC/Mestrado Teoria dos Grafos
Teorema 1:
Seja G = (V,E) um grafo simples com n vértices e m arestas. Então
∑ d(v) = 2mv Є V
u v
e
Prova:
• A aresta e é incidente aos vértices v e w• É contabilizada no cômputo do grau de v etambém de w.
UFESCC/EC/Mestrado Teoria dos Grafos
Corolário 1:
O número de vértices de grau ímpar, de um grafo G, é par.
Prova:V
VI VP
∑ d(v) = ∑ d(v) + ∑ d(v) = 2mv Є V v Є VI v Є VP
par par par
2010/2 Teoria dos Grafos UFES
Subgrafos Subgrafo: G' = (N', A') é um subgrafo de G = (N, A) se N' N e A'
A. Subgrafo induzido por N': G' = (N', A') é um subgrafo de G = (N,
A) induzido por N' se G' contém todos os arcos de G que ligam apenas os vértices de N'.
• Subgrafo gerador: o subgrafo G' = (N', A') de G = (N, A) é gerador se N' = N e A' A.
2010/2 Teoria dos Grafos UFES
Percursos Percurso: é um subgrafo de G = (N, A) que consiste de vértices e
arcos em uma sequência i1 – a1 – i2 – a2 – i3 – a3 - … - ir-1 – ir, que satisfaz a seguinte propriedade:
k, 1 k r-1, ak = (ik, ik+1) Aou ak = (ik+1, ik) A.
Percurso direcionado: todos os arcos do percurso estão na mesma direção.
Percurso simples direcionado: étodos os arcos do percurso direcionado não se repetem, podendo haver repetição de vértices.
• Caminho: percurso simples sem repetição de vértices.
• Caminho direcionado: percurso simples direcionado sem repetição de vértices.
2010/2 Teoria dos Grafos UFES
Percursos Ciclo: percurso simples e fechado (o nó inicial coincide com o final). Ciclo direcionado: ciclo orientado com todos os arcos na mesma
direção. Rede acíclica: um grafo é acíclico se não contém ciclo direcionado.
2010/2 Teoria dos Grafos UFES
Conexidade Dois vértices estão conectados se existe um caminho entre eles. Um grafo é conexo se todo par de vértices é conectado. Caso contrário
é desconexo. Grafo simplesmente conexo ou s-conexo: todo par de vértices é
unido por ao menos um caminho no grafo correspondente não direcionado.
Grafo semi-fortemente conexo ou sf-conexo: em todo par de vértices do grafo, um deles é atingível a partir do outro (ou seja, entre eles existe um caminho em ao menos um dos dois sentidos possíveis)
Grafo fortemente conexo ou f-conexo: todo par de vértices é mutuamente atingível, ou seja, a todo par de vértices está associado um par de caminhos de sentidos opostos. Todo vértice é atingível a partir de um vértice dado e todo vértice atinge todo vértice dado
2010/2 Teoria dos Grafos UFES
Exemplosa
d
b c
a
d
b c
a
b c
d
2010/2 Teoria dos Grafos UFES
Níveis de Conexidade
s-conexo
f-conexo
sf-conexo
2010/2 Teoria dos Grafos UFES
Componentes f-conexas
• Um grafo orientado qualquer pode ser particionado em componentes f-conexas maximais.
• Se um grafo orientado é f-conexo: a partição é o próprio conjunto de vértices do grafo.
2010/2 Teoria dos Grafos UFES
Corte de arcos• Um corte é um conjunto de arcos que define uma partição do
conjunto de vértices [S, N-S], de maneira que cada arco pertencente ao corte possui um dos seus extremos em S e o outro em N-S.
• Um corte s-t é um corte [S, N-S] com respeito a dois vértices s e t do grafo, de maneira que s S e t N-S.
2010/2 Teoria dos Grafos UFES
Árvores• Uma árvore é um grafo conexo sem ciclos.• Algumas propriedades:
– Uma árvore com n nós possui exatamente n-1 arcos– Cada par de vértices de uma árvore está conectado por
exatamente um único caminho– Uma árvore possui pelo menos 2 folhas (vértices de grau
1)• Uma floresta é um grafo sem ciclos.• Subárvore: um subgrafo conexo de uma árvore• Árvore enraizada: algum vértice da árvore é escolhido como raíz e
todos os outros vértices são “hierarquizados” de acordo com essa raíz
2010/2 Teoria dos Grafos UFES
Árvores• Uma árvore out-tree direcionada enraizada no nó s é uma árvore
T na qual o único caminho entre s e cada vértice de T é um caminho direcionado.
• Uma árvore in-tree direcionada enraizada no nó s é uma árvore T na qual o único caminho entre cada vértice de T e s é um caminho direcionado.
• Árvore geradora: Uma árvore T é uma árvore geradora de G se T é subgrafo gerador de G e é uma árvore.
• Um grafo G é bipartido se o seu conjunto de vértices pode ser particionado em 2 conjuntos N1 e N2 de forma que cada arco de G possui um dos extremos em N1 e o outro em N2 e não há arcos que liguem vértices de uma mesma partição.
– Propriedade: Um grafo G é bipartido sss cada ciclo em G possui comprimento par.