Grafos - Anotações Conceitos Básicos

Prova 1 - Grafos

CONCEITOS:

Vértice adjacente - Um vértice que está ligado a outro pela adjacência.

Laço - Uma aresta que conecta um vértice nele mesmo.

Grau - Número de arestas que incidem no vértice.

Caminho - Um caminho é uma cadeia na qual todos os arcos possuem a mesma orientação.

Circuito - É um caminho simples e fechado.

Ponte - É qualquer aresta que não pertence a um circuito.

Conexidade - Um grafo qualquer (orientado ou não) é não conexo, ou desconexo, se nele existir ao menos um par de vértices não unidos por uma cadeia.

Grafo regular - Um grafo onde todos o vértices têm o mesmo grau.

Grafo completo - É um grafo simples em que todo vértice é adjacente a todos os outros vértices.

Grafo conexo - é conexo se existir um caminho entre qualquer par de vértices

Grafo fortemente conexo - Quando é possível sair e voltar de todos para todos os vértices.

Grafo acíclico - É um grafo dirigido sem ciclo.

Grafos isomorfos - São grafos equivalentes desenhados de forma diferente.

Fecho Transitivo de um vértice - Basicamente é o conjunto de vértices alcançáveis pelo vértice inicial.

Fecho Transitivo de um Grafo - Conjunto de alcances possíveis de um grafo.

Grafo ponderado - Grafo com arestas com peso.

Grafo não ponderado - Grafo sem peso nas arestas.

Caminhos disjuntos em arestas - Dois caminhos são disjuntos quando não possuem arestas em comum.

Caminhos disjuntos em vértices - Dois caminhos são disjuntos quando não possuem vértices em comum.

Ciclo em grafos - Um passeio de comprimento mínimo três, em que o primeiro e o último vértice coincidem, mas nenhum outro vértice é repetido. O número de vértices e arestas tem de ser igual.

Grafo simples - Não contém laços nem arestas paralelas.

Grafo bipartido - Um grafo é bipartido se por possível separar o grafo em dois grupos, sendo que os vértices de cada grupo não podem se conectar com ninguém do mesmo grupo.

Clique - Uma clique quer dizer que um sub-grafo é completo.

Grafo clique - Grafo clique quer que ele possui subgrafos cliques.

Circuito Hamiltoniano - É um caminho em um grafo não dirigido que visita cada vértice apenas uma única vez.

Dígrafo - É um grafo dirigido.

Ordenação topológica - Um dígrafo acíclico (DAG) é uma ordem linear de seus nós em que cada nó vem antes de todos nós para os quais este tenha arestas de saída

Árvore - É um grafo sem ciclos.

BUSCAS:

Busca em largura:

A busca em largura funciona com base no grau dos vértices, ou seja, será visitado a partir do grau inicial as conexões com grau um, depois os de grau dois e assim sucessivamente.

A busca em largura produz uma árvore do grafo a partir do ponto escolhido.

Realizando a busca:

Para organizar o processo de busca os vértices são geralmentes “pintados”:

* Branco: não foram descobertos ainda

* Cinza: o vértice já foi descoberto mas ainda não examinamos os seus vizinhos.

* Preto: são os vértices já descobertos e seus vizinhos já foram examinados.

É utilizado uma fila para manter os vértices cinzas.

Busca:

* Inicialmente todos os vértices são pintados de branco e a distância até eles setada é infinito já que não se conhece o valor.

* O vértice inicial é colocado na fila.

* O vértice pai é retirado da fila após os seus filhos serem adicionados, o mesmo é pintado de preto já que seus vizinhos foram visitados, o seus vizinhos são pintados de cinza, a distância do pai até os vizinhos é adicionado nas arestas vizinhas.

* Agora lê o próximo da fila e repete o mesmo processo, adicionando os filhos na fila e removendo o pai e etc…

* Lembrando que só pode ser adicionado à fila vértices brancos, ou seja, vértices que ainda não foram visitados.

* Após todos os vértices do grafo estiverem na cor “preta” quer dizer que o processo terminou, caso algum vértice permanecer na cor “branca” quer dizer que ele não tem conexão com o vértice inicial escolhido.

* A busca em largura no final do processo pode ser mostrada em forma de árvore.

Busca em profundidade:

A ideia da busca em profundidade é ir percorrendo o grafo a partir de um nó inicial ir “descendo’ no grafo pelos vizinhos até um ponto onde não há mais caminho, voltando e repetindo o processo. Diferente da busca em largura que se cria uma árvore, a busca em profundidade cria uma floresta, ou seja, um conjunto de árvores.

Realizando a busca:

A busca em profundidade também marcar seus vértices de alguma forma. A forma usada será a seguinte:

* d[.]: o momento em que o vértice foi descoberto (tornou-se cinza).

* f[.]: o momento em que examinamos os seus vizinhos (tornou-se preto).

O vértice é branco até d, cinza entre d e f e preto a partir de f.

Busca:

Realizando a busca:

A busca em profundidade funciona da seguinte maneira:

*