Resumo - Prova I

Prévia do material em texto

· Grafo é uma coleção de vértices e arestas. Por definição, um grafo deve ter pelo menos 1 vértice
· Vértice é um objeto simples que pode ter nomes e outros atributos
· Aresta é uma conexão entre dois vértices
· Grafo Não Orientado ou Não Direcionado: G = (V,E) é um par (V,E), onde V é um conjunto finito e o conjunto de arestas E consiste em pares não orientados. As arestas (Vi, Vj) e (Vj, Vi) são consideradas a mesma
· Grafo Orientado / Direcionado ou Dígrafo: G é um par (V,E), onde V é um conjunto finito e o conjunto de arestas E é uma relação binária em V
· Loop: Aresta associada ao par de vértices (vi,vi)
· Arestas Paralelas: Duas ou mais arestas associadas ao mesmo par de vértice
· Grafo Simples: Grafo que não possui loops nem arestas paralelas
· Vértices Adjacentes: Dois vértices são ditos adjacentes se eles são pontos finais de uma mesma aresta
· Arestas Adjacentes: Duas arestas não paralelas são adjacentes se elas são incidentes a um vértice comum
· Vértice e Arestas Incidentes: Quando um vértice vi é o vértice final de alguma aresta ej, vi e ej são incidentes
· Grau: O número de arestas incidentes a um vértice vi é chamado de grau, d(vi), do vértice i
· Teorema I: soma dos graus de todos os vértices de um grafo G é duas vezes o número de arestas de G 
· Teorema II: O número de vértices de grau ímpar em um grafo é par
· Grafo Regular: Um grafo no qual todos os vértices possuem o mesmo grau 
· Vértice Isolado: Um vértice com nenhuma aresta incidente é chamado de vértice isolado
· Vértice Pendente: Um vértice com grau 1 é chamado de vértice pendente
· Grafo Nulo: Um grafo sem arestas é chamado de grafo nulo. Todos os vértices em um grafo nulo são vértices isolados
· Grafo Completo: Um grafo G=(V,E) é completo se para cada par de vértices vi e vj existe uma aresta entre vi e vj. Em um grafo completo quaisquer dois vértices distintos são adjacentes (Kn)
· Grafo Conexo: Grafo em que existe pelo menos um caminho entre todos os pares de vértices de G
· Número de Componentes: Um grafo desconexo consiste de 2 ou mais grafos conexos. Cada um dos subgrafos conexos é chamado de componente
· Isomorfismo: Dois grafos G e H são ditos isomorfos se existir uma correspondência um-para-um entre seus vértices e entre suas arestas, de maneira que as relações de incidência são preservadas
Não existe um algoritmo eficiente para determinar se dois grafos são isomorfos
Condições necessárias mas não suficientes para que G e H sejam isomorfos:
· mesmo número de vértices
· mesmo número de arestas
· mesmo número de componentes
· mesmo número de vértices com o mesmo grau
· Grafo Complementar: Seja G = (V,E) um grafo simples, seu grafo complementar, C(G), é um grafo formado da seguinte maneira: Os vértices de C(G) são todos os vértices de G; As arestas de C(G) são exatamente as arestas que faltam em G para formarmos um grafo completo
· Grafo Bipartite ou Bipartido: Grafo não orientado em que o conjunto de vértices V pode ser particionado em 2 subconjuntos V1 e V2 tal que não existem arestas entre dois vértices de um mesmo subconjunto
· Um grafo g é dito ser um subgrafo de um grafo G se todos os vértices e todas as arestas de g estão em G
Observações: 
· todo grafo é subgrafo de si próprio 
· o subgrafo de um subgrafo de G é subgrafo de G 
· um vértice simples de G é um subgrafo de G
· uma aresta simples de G (com suas extremidades) é subgrafo de G
· Subgrafos Disjuntos de Arestas: Dois (ou mais) subgrafos g1 e g2 de um grafo G são disjuntos de arestas se g1 e g2 não tiverem arestas em comum
· Subgrafos Disjuntos de Vértices: Dois (ou mais) subgrafos g1 e g2 de um grafo G são disjuntos de vértices se g1 e g2 não tiverem vértices em comum
· Operações com Grafos: Seja G1 = (V1,E1) e G2 = (V2,E2), tem-se:
· Gunião = G1 U G2 = (V1 U V2, E1 U E2)
· Ginterseção = G1 ∩ G2 = (V1 ∩ V2, E1 ∩ E2)
· Gring sum = G1 G2 = (V1 V2, E1 E2)
· A operação ring sum consiste na união dos grafos G1 e G2, de modo que a interseção entre eles não seja incluída
· Matriz de Adjacências: 
· O espaço ocupado por uma matriz de adjacências é proporcional a V2, sendo V o número de vértices do grafo. 
· No caso de grafos densos, esse espaço é proporcional ao tamanho do grafo. 
· Para grafos esparsos, existem representações mais compactas
· Lista de Adjacências: O vetor de listas de adjacência de um grafo tem uma lista encadeada associada com cada vértice do grafo.
· A lista associada com um vértice v contém todos os vizinhos de v;
· Portanto a lista do vértice representa as saídas de v.
· Matriz de Incidência: 
· Linhas: Vértices
· Colunas: arestas
· M[i,j] = 1 para se a aresta ej incide sobre o vértice vi, caso contrário 0 (zero)
· Matriz B= (bij), de ordem |V| x |E|: 
· bij= 1, se vértice vi e aresta ej forem incidentes 
· bij= 0, caso contrário
· Lista: 
· Linhas: Vértices
· Colunas: arestas
· M[i,j] = 1 para se a aresta ej incide sobre o vértice vi, caso contrário 0 (zero)
· Sequência de arestas: sequência alternada de vértices e arestas começando e terminando com vértice. Cada aresta é incidente ao vértice que a precede e a antecede
· Caminho: sequência de arestas no qual nenhuma aresta aparece mais de uma vez
· Caminho aberto: vértice inicial é diferente do vértice final
· Caminho fechado: caminhos que começam e terminam no mesmo vértice
· Caminho simples: caminho aberto no qual nenhum vértice aparece mais de 1 vez
· Comprimento: de um caminho é o número de arestas do caminho. Se um caminho tem n vértices, seu comprimento é pelo menos n−1; se o caminho é simples, seu comprimento é exatamente n−1
· Circuito: caminho fechado no qual nenhum vértice (exceto o primeiro e o último) aparece mais de uma vez
· Teoremas de Caminhos e Circuitos:
· TEOREMA: Se um grafo possui exatamente 2 vértices de grau ímpar, existe um caminho entre esses dois vértices.
· TEOREMA: Um grafo simples com n vértices e k componentes possui no máximo (n-k)(n-k+1)/2 arestas.
· TEOREMA: O número mínimo de arestas de um grafo simples com n vértices e k componentes é n-k.
· Grafos Eulerianos: Para grafos conexos, se é possível encontrar um caminho fechado que passe por todas as arestas uma única vez, dizemos que G é um grafo euleriano
· TEOREMA: Um grafo conexo é euleriano se, e somente se, todos os seus vértices tiverem grau par
· Grafos Semi-Eulerianos: Teorema: Um GrafoGé atravessável se e somente se G é conexo e tem exatamente dois vértices de grau impar. Consequentemente, qualquer trilha euleriana de Gcomeça em um dos vértices de grau impar e terminano outro vértice de grau impar.
· Algoritmos de Fleury: Comece em qualquer vértice v e percorra as arestas de forma aleatória, seguindo sempre as seguintes regras: 
· 1. Exclua as arestas depois de passar por elas;
· 2. Exclua os vértices isolados, caso ocorram;
· 3. Passe por uma ponte somente se não houver outra alternativa
· Uma aresta é dita ser uma ponte se a sua remoção torna o grafo desconexo
· Grafos Unicursais: Um grafo G é dito unicursal se ele possui um caminho aberto de euler, ou seja, se é possível percorrer todas as arestas de G apenas 1 vez sem retornar ao vértice inicial. 
· Se adicionarmos uma aresta entre os vértices inicial e final do caminho aberto de euler, esse grafo passa a ser um grafo euleriano.
· Um grafo conexo é unicursal se, e somente se, ele possui exatamente 2 vértices de grau ímpar
· TEOREMA: Em um grafo conexo G com exatamente 2K vértices de grau ímpar, existem K subgrafos disjuntos de arestas, todos eles unicursais, de maneira que juntos eles contêm todas as arestas de G
· Casos:
· Grafo euleriano: todos os vértices de grau par
· Grafo unicursal: dois vértices de grau ímpar
· Grafo qualquer: 2K vértices de grau ímpar (k-traçavel)
· Grafos Hamiltonianos: Um Circuito de Hamilton em um grafo conexo é um circuito que passa por todos os vértices do grafo uma única vez (exceto pelo vértice inicial)
· Um Caminho de Hamilton em um grafo conexo é um caminho simples que passa por todos os vértices do grafo exatamente uma única vez 
· Considerações sobre grafos Hamiltonianos:
·O grafo deve ser conexo
· Loops e arestas paralelas podem ser desconsideradas (n ≥ 3)
· Se um grafo é hamiltoniano, então a inclusão de qualquer aresta não atrapalha essa condição
· TEOREMA ORE: Seja G um grafo simples com n vértices (n ≥ 3). Se para todo par de vértices não adjacentes v e w, a soma de seus graus for maior ou igual a n, então G é hamiltoniano
· TEOREMA DIRAC: Seja G um grafo simples com n vértices (n ≥ 3). Se o grau de cada vértice for n/2 no mínimo, G é hamiltoniano
· TEOREMA: Em um grafo completo com n vértices, n ímpar e (n ≥ 3), existem circuitos hamiltonianos disjuntos de arestas 
· TEOREMA: Em um grafo completo com n vértices, n par e (n ≥ 4), existem circuitos hamiltonianos disjuntos de arestas
· Grafos eulerianos e hamiltonianos são caminhos que usam todos ou todas as arestas
· Algoritmo de Dijkstra: Este algoritmo não encontra o menor caminho, e sim a menor distância ente um par de vértices.
· Encontrar a menor distância entre um par de vértices
· Encontrar a menor distância entre todos os pares de vértices
· Algoritmo de FLOYD: Utiliza uma matriz de distâncias. Menor Caminho entre todos os pares de vértices