Mapa Mental - Teoria dos Grafos

Prévia do material em texto

Caminhos e Circuitos Matrizes e Representações Caminho Euleriano passa por Matriz de adjacência representa todas as arestas exatamente conexões entre vértices em grafos uma vez. direcionados. Circuito Hamiltoniano percorre Adição de arestas altera todos vértices uma única diretamente a matriz de adjacência vez formando ciclo. do dígrafo. Existência de caminho Representações gráficas facilitam Euleriano depende do número de visualização de propriedades e nós no grafo. caminhos. Problema do circuito N Função g associa arestas a pares Hamiltoniano é NP-completo, ordenados de vértices em dígrafos. sem algoritmo eficiente conhecido. Teoria Grafos Planaridade dos Grafos Específicos Grafo K32 é planar e Grafo K5 é não planar, isomorfo a outro grafo importante para planar conhecido. Grafos de Grafo K33 não é planar, pois planaridade. arestas se cruzam Grafo K32 possui 5 vértices inevitavelmente. e é planar, com propriedades Relação fundamental: n a + específicas de grau. r = 2 para grafos planos Grafo K33 é conexo, com simples e conexos. todos nós de grau 3, mas Para grafos com n 3 e sem não planar. ciclos de comprimento 3, a > Grafos completos têm arestas 2n 4. Ordenação e Complexidade entre todos pares de Ordenação topológica respeita vértices distintos. direção das arestas em grafos direcionados acíclicos. Algoritmos de Busca Problema do caminho Hamiltoniano tem complexidade O(n!) no pior Árvores e Percursos Busca em largura utiliza fila caso. Altura da árvore é a maior para visitar vértices em Problemas NP-completos não possuem profundidade entre seus nós, ordem de descoberta. algoritmos polinomiais conhecidos raiz tem profundidade zero. Busca em profundidade explora para solução geral. Percurso pré-ordem visita máximo possível antes de Isomorfismo entre grafos implica raiz antes dos filhos, útil retroceder. mesma estrutura, mas não para notação infixa. Busca em largura é útil para necessariamente mesma Percurso pós-ordem visita encontrar caminhos mínimos em representação. subárvores antes da raiz, grafos não ponderados. usado em notação polonesa. Estruturas de dados adequadas Percurso em ordem simétrica são essenciais para gera notação polonesa eficiência dos algoritmos. reversa, importante em computação.