anotações P1 Grafos

Prévia do material em texto

Resumo Grafos
Algoritmo de Floyd-Warshall
Complexidade? 
O(n³)
O que faz? 
Acha o caminho de custo mínimo de todos os vértices. 
Como? 
Testando caminhos intermediários entre dois vértices, por exemplo, há 5 vértices no grafo, o
algoritmo pega o vértice 1 e tenta achar o menor caminho dele, para isso ele pega todos os
vértices do grafo e pega um vértice intermediário e compara se o caminho entre o vértice 1 e
outro vértice qualquer é menor que o caminho v1 e vInter + vInter e vQualquer.
Ilustrando:
Algoritmo de Dijkstra:
Complexidade? 
Depende da forma como é implementado varia de O(mlogn) se utilizar heap binário até O(n²) 
se usa vetor para armazenar Q (fila de prioridades).
O que faz?
Encontra o menor caminho entre um vértice e todos os outros vértices do grafo. Em
determinados momentos é mais interessante executar esse algoritmo para achar todos os
caminhos mínimos ao invés do algoritmo de Floyd-Warshall.
Como?
Primeiro ele cria um array/dicionário em que o índice/chave é o vértice do grafo, para o vértice 
que nós queremos achar o menor caminho o valor será igual a zero, o restante seria um 
número suficientemente alto para representar o infinito, em seguida cria-se uma fila de 
prioridades(array) Q que terá todos os vértices relacionados com seus custos, criamos um array
vazio S que irá armazenar os vértices que já possuem menor caminho.
Busca Profundidade:
Complexidade?
Depende da implementação: Se for feito com listas, o total de arestas na lista é 2e, logo o 
tempo para completar a busca é O(e). Se for feito com matriz de adjacência, para determinar 
todos os nós adjacentes a um dado nó v é O(n) como são visitados no max n nós, o tempo total
será O(n²). 
O que faz?
Busca um determinado vértice no grafo ou pode percorrer todo o grafo.
Como faz?
Indo do vértice que você considerar raiz até o último vértice mais profundo do grafo, após 
completar volta um vértice para cima, vê se há mais vértices filhos e busca eles.
Busca Largura:
Complexidade?
Se usar listas O(e), se usar matriz adjacência O(n²).
O que faz?
Busca um determinado vértice ou percorre todo o grafo a partir de um determinado vértice.
Como faz?
Percorre o grafo pegando todos os vértices adjacentes a um vértice passado como parâmetro 
adiciona-os a uma lista, pega os adjacentes dos adjacentes desse vértice, e faz o mesmo 
processo.
Árvore Geradora Mínima
Complexidade?
Algoritmo de Kruskal – O(mlgm).
Algortimo de Prim – O(E log V) – Considerando heap binário.
O que faz?
Cria uma árvore geradora mínima, que pela definição de árvore possuirá n-1 arestas, e o custo
de cada aresta será mínimo, ou seja, só farão parte do subgrafo aquelas arestas que possuem o
menor custo.
Como faz?
 Algoritmo de Kruskal:
 Crie uma floresta F (um conjunto de árvores), onde cada vértice no grafo é uma árvore
separada
 Crie um conjunto S contendo todas as arestas do grafo
 Enquanto S for não-vazio, faça:
 Remova uma aresta com peso mínimo de S
 Se essa aresta conecta duas árvores diferentes, adicione-a à floresta, combinando duas
árvores numa única árvore parcial
 Do contrário, descarte a aresta.
Grafos Eulerianos:
Um grafo G é dito ser euleriano se há um ciclo em G que contenha todas as suas arestas.
Desta definição segue-se dois teoremas importantes.
T1 – Define se o grafo é euleriano.
T1: Um grafo M é euleriano sse M é conexo e cada vértice de M tem grau par.
T2 – Define se o grafo é atravessável, não se refere a grafos euleriano e sim a caminhos
eulerianos, ou seja, existe um caminho a partir de um vértice (grau ímpar) que vai permitir
percorrer todo o grafo e passar por cada aresta apenas uma vez.
T2: Um multigrafo M é atravessável se e somente se M é conexo e tem exatamente dois ou
nenhum vértices de grau ímpar. Consequentemente, qualquer trilha euleriana de M começa
em um dos vértices de grau ímpar e termina no outro vértice de grau ímpar.
Grafos Hamiltonianos:
Um grafo G é dito ser hamiltoniano se existe um ciclo em G que contenha todos os seus
vértices, sendo que cada vértice só aparece uma vez no ciclo. Este ciclo é chamado de ciclo
hamiltoniano. Sendo assim um grafo é hamiltoniano se ele contiver um ciclo hamiltoniano.
Não há métodos para determinar se um grafo é Hamiltoniano, há alguns teoremas que servem
para determinador grafos, como por exemplo:
Teorema: Se G é um grafo de ordem p (>=3) tal que o grau(v) >= p/2 para cada vértice v de G,
então G é hamiltoniano.
Planaridade: 
Um grafo G(V,A) é dito ser planar quando existe alguma forma de se dispor seus vértices em
um plano de tal modo que nenhum par de arestas se cruze. Um grafo não será planar se ele
possuir um subgrafo K3,3 ou um K5.
Coloração:
Uma coloração de G é uma atribuição de alguma cor de C para cada vértice de V, de tal modo
que a dois vértices adjacentes sejam atribuídas cores diferentes.
Número Cromático:
Denomina-se número cromático X(G) de um grafo G ao menor número de cores k, para o qual
existe uma k-coloração de G.
Alguns Exemplos de número cromático:
Árvore - ≤ 2
Bipartido - ≤ 2
Ciclo – 2 par, 3 ímpar
Hamiltoniano - ≤ n (não dá pra saber)
Planar - ≤ 4
Regular - ≤ n
Ordenação Topológica:
Uma ordenação topológica de 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. Cada DAG tem
uma ou mais ordenações topológicas.
Para existir um ordenação topológica é necessário:
1. Existir pelo menos um vértice fonte e um sumidouro
2. Não pode haver dependência cíclica (formar um circuito).
Prova Indução Estrutural:
2 Passos:
1 – Passo Base: Prove que a hipótese é verdadeira usando o grafo mais simples que pode ser
construído a partir dessa hipótese.
2 – Passo Indutivo:
Pegue um G’ a partir de G e prove que a hipótese não será violada se:
- Adicionar um vértice.
- Adicionar uma aresta.
Seja G(V,A) um grafo não orientado e conexo com n vértices. Então G contém pelo menos n-1
arestas.
Passo Base: o grafo G(1,0) é orientado e conexo, e a hipótese de G conter pelo menos n-1
arestas é verdadeira.
Passo Indutivo:
Seja G’ um grafo obtido a partir de G:
Inserir vértice: Ao inserir um vértice serei obrigado a inserir uma aresta para manter o grafo
conexo, o que tornará o grafo G’ (2,1) e a propriedade se mantém verdadeira.
Inserir aresta: A inserção de aresta não altera a propriedade n-1 arestas. 
Portanto G contém pelo menos n-1 arestas.
OBS COMPLEXIDADE: Se há um for que varre todos os vértices adjacentes à x esse for varrerá
m vezes e não n vezes, porque se trata da quantidade de vértices ligados a ele e não do total de
vértices do grafo, e assim no pior caso podemos transformar m em n².