AULA 5

Prévia do material em texto

Estácio Teresina
Curso de Ciência da Computação
Algoritmos em Grafos
Aula 5 – Conceitos Básicos de Grafos
Joselito Mendes de Sousa Junior
Conceitos Importantes
 Grafo simétrico é um grau orientado no qual, sempre
que houver um arco (i, j), haverá um arco (j, i).
 Ou seja, equivale a um grafo não-orientado.
2
Conceitos Importantes
 Grafo completo é um grafo, orientado ou não, que possui
ao menos uma ligação entre cada par de vértices.
 Em outras palavras, é um grafo simples (não permite arestas
paralelas nem laços) no qual todos os vértices distintos são
adjacentes.
 Grafos completos recebem nomes especiais de acordo com
a quantidade de vértices que ele contém
 𝐾1
 𝐾2
 𝐾3
 ...
3
Grafo Completo
4
A B
C
Grafo Não-Completo
A B
C
Grafo Completo 𝐾3
D E
Grafo Completo 𝐾2
F
Grafo Completo 𝐾1
5 2
4 3
1
Grafo Completo 𝐾5
Conceitos Importantes
 Um grafo é bipartido quando o seu conjunto de
vértices puder ser particionado em dois subconjuntos
tais que não haja ligações internas a eles, ou seja, entre
dois vértices de um mesmo subconjunto.
 Alguns problemas de grafos podem ser resolvidos de
maneira mais fácil se forem modelados como grafos
bipartidos.
5
Grafo Bipartido
6
A C
B D
E
F
Grafo Bipartido
A
C
E
B
D
F
𝑃1 𝑃2
Grafo Bipartido
 O grafo a seguir é bipartido? Se sim, determine suas
partições.
7
A B C
H I D
G F E
Solução: Teorema das
duas cores (colorir seus
vértices com apenas duas
cores distintas, de modo
que vértices adjacentes
não tenham a mesma
cor).
Grafo Bipartido
8
A B C
H I D
G F E
𝑃1 𝑃2
𝑃1 = {A, C, E, G, I} 𝑃2 = {B, D, F, H}
A
C
E
G
I
B
D
F
H
Grafo Bipartido
 E se fosse esse grafo?
9
A B
E CF
D
 Os vértices E e F são vizinhos
e possuem a mesma cor.
 Os vértices D e E são vizinhos
e possuem a mesma cor.
 Logo, o grafo não é bipartido.
Conceitos Importantes
 Conexidade é a propriedade de um grafo ser, ou não,
conexo. Um grafo é conexo sempre que, dado um
vértice qualquer, é possível alcançar todos os outros
vértices.
 Em grafos não orientados conexos, sempre se pode ir
de um vértice a outro, atravessando arestas. Se, em
alguma situação, uma aresta for indispensável a este
processo, ela é chamada de ponte do grafo. A remoção
de uma ponte, portanto, desconecta o grafo.
10
Conceitos Importantes
11
1 2
4 3
5
x
 A remoção da aresta x, tornaria
o grafo 𝐺1 desconexo.
 Logo, a aresta x é uma ponte do
grafo.
Grafo 𝐺1
Conexidade
 Em grafos conexos, temos 3 tipos de conexidade:
 Fortemente conexo, onde existe sempre um caminho entre
qualquer par de vértices. Grafos fortemente conexos podem
ser chamados de f-conexo.
 Conexo ou semi-fortemente conexo, onde para todo par de
vértice (u, v), existe um caminho de u até v ou existe um
caminho de v até u. Grafos semi-fortemente conexos podem
ser chamados de sf-conexo.
 Fracamente conexo ou simplesmente conexo, onde se não
considerarmos a orientação, existem cadeias (caminhos)
entre todos os pares de vértices. Grafos simplesmente
conexos podem ser chamados de s-conexo.
12
Conceitos Importantes
 Dado um grafo G com 4 componentes f-conexos. Em
um componente f-conexo, podemos “ir” e “vir” de um
vértice a qualquer outro. Se a partir de um vértice u,
pudermos chegar a um vértice v, podemos chegar a
todos os vértices da componente f-conexa à qual v
pertence. Isso sugere a criação de um grafo reduzido.
 Grafo reduzido 𝐺𝑟 = (𝑉𝑟, 𝐸𝑟) é formado por:
 Para cada componente conexo, teremos um vértice de 𝐺𝑟.
 Dois vértices x e y de 𝐺𝑟 serão ligados por um arco se
houver um caminho indo de qualquer vértice da
componente f-conexa que contém x a qualquer vértice da
componente f-conexa que contem y.
13
Grafo Reduzido
14
F-conexo F-conexo
F-conexo F-conexo
1 2
34
1 2
34
Grafo G Grafo 𝐺𝑟
Conceitos Importantes
 O grafo reduzido tem a mesma conexidade do grafo
original (dizemos que a redução do grafo preserva a sua
conexidade).
 Se G for não conexo, 𝐺𝑟será não conexo.
 Se G for conexo, 𝐺𝑟 será um ponto (um ponto é f-conexo).
 A conexidade em grafos orientados é uma propriedade
muito importante em certos contextos. No trânsito, por
exemplo, é claro que o grafo que modela a rede de ruas
terá de ser f-conexo ou, então, haverá alguma rua onde
um carro não poderá entrar, ou, se entrar, não poderá
mais sair.
15
Propriedades
 Todo grafo f-conexo atende às definições de grafo sf-
conexo e s-conexo, ou seja:
 Em um grafo f-conexo sempre existe um caminho de um
vértice a outro (sf-conexidade).
 Poderemos andar de qualquer vértice a qualquer outro, sem
respeitar o sentido dos arcos, como os pedestres andam
pelas ruas de mão única, por exemplo (s-conexidade)
 Um grafo sf-conexo atende às definições de um grafo
s-conexo.
16
Componente F-Conexo
 A determinação das componentes f-conexas de um
grafo orientado é uma etapa muito importante no
estudo de muitos modelos de grafo, pois ela permite a
simplificação do modelo (imagine grafos com 50.000
vértices).
 Considerando um grafo orientado G. Se tomarmos um
vértice x e determinarmos o seu fecho transitivo direto
𝑹+(x), teremos encontrado todos os vértices atingíveis
a partir de x, ou seja, todos os vértices para os quais
existe um caminho a partir de x.
17
Componente F-Conexo
 Se, então, acharmos o fecho transitivo inverso 𝑹−(x),
teremos encontrado todos os vértices a partir dos quais
x é atingível, ou seja, todos os vértices a partir dos
quais existe um caminho para x.
 Assim como x pertence aos dois fechos, podem haver
outros vértices nessa situação. Basta olhar para a
interseção.
18
Componente F-Conexo
 Os vértices dessa interseção formam uma componente
f-conexa do grafo.
19
Vértices 
de 𝑅+(x) 
Vértices 
de 𝑅−(x) 
x
𝑅+(x) ∩ 𝑅−(x): contém os componentes 
f-conexos que contém x
Componente F-Conexo
 Utilizamos o Algoritmo de Malgrange para construir
os dois fechos transitivos de um vértice, fazer a
interseção deles e retirar do grafo os vértices dessa
interseção, até que todos os vértices sejam separados
de suas componentes.
20
Algoritmo de Malgrange
21
Algoritmo de Malgrange
22
 Utilizando o vértice 1 para achar seu fecho transitivo
direto (ou descendentes)
Algoritmo de Malgrange
23
 Utilizando o vértice 1 para achar seu fecho transitivo
inverso (ou ascendentes)
Algoritmo de Malgrange
 Assim, temos 𝑅+ 1 ∩ 𝑅− 1 = 1,4,5 ∩ 1,2,3,6 = 1
 Depois, fazemos isso com os vértices 2, 3, 4, 5 e 6. Assim,
encontramos os seguintes componentes f-conexos:
 {1}
 {2, 3, 6}
 {4, 5}
24
Algoritmo de Malgrange
 Ajustando nosso grafo, temos:
 Assim, o nosso grafo reduzido é:
25
6
3
2 1
4
5
{2, 3, 6}
{4, 5}
{1}
{2, 3, 6}
{4, 5}
{1}
Algoritmo de Malgrange
 Observações:
1. No algoritmo, as palavras em negrito (como enquanto) são
comandos a serem executados.
2. Pode-se notar que o algoritmo modifica o conteúdo do conjunto de
vértices, que diminui a cada iteração: por isso é conveniente
trabalhar com a cópia Y de V.
3. A variável I, como comentado, é um indexador das componentes f-
conexas.
4. O algoritmo pode ser aplicado a grafos não orientados, bastando,
neste caso, executar a varredura uma só vez e dispensando-se a
fase de interseção. O resultado será o particionamento do grafo em
suas componentes conexas.
5. Se um grafo orientado for f-conexo, o algoritmo descobrirá isso em
uma só iteração (pois existirá uma única componente). O mesmo
ocorrerá com um grafo não orientado conexo.
26