Mapa Mental - Teoria dos Grafos

Prévia do material em texto

Árvores e Florestas Terminologia Fundamental Árvore é um grafo conexo e Nós adjacentes são extremidades acíclico com um nó raiz comuns de algum arco no grafo. especial. Grau de um nó é número total de Profundidade de um nó é arcos incidentes nesse nó. comprimento do caminho da Caminho é uma sequência de nós e raiz até ele. arcos conectados sem repetição de Árvores binárias têm no arcos. máximo dois filhos por nó, Grafo conexo possui caminho entre podendo ser cheias ou qualquer par de nós distintos. completas. Floresta é um conjunto de árvores disjuntas, ou grafo acíclico não necessariamente Teoria conexo. Definições Básicas dos Representação Computacional Grafo é um conjunto finito Matriz de adjacência é uma matriz de nós e arcos que conectam quadrada que indica conexões entre pares de nós. Grafos nós. Grafo direcionado associa Lista de adjacência armazena para cada arco a um par ordenado cada nó uma lista encadeada de seus com sentido definido. vizinhos. Grafo simples não possui Matriz de adjacência para dígrafos laços nem arcos paralelos não é necessariamente simétrica. entre mesmos nós. Listas de adjacência são eficientes Grafo completo conecta todos para grafos com poucos arcos. pares distintos de nós com uma aresta. Algoritmos e Aplicações Busca em largura (BFS) visita nós por níveis, usando fila para controle de visitação. Grafos Especiais Busca em profundidade (DFS) explora ramos do grafo Caminhos Especiais Grafo bipartido completo recursivamente, visitando nós Caminho de Euler percorre divide nós em dois profundamente. todas as arestas exatamente conjuntos disjuntos e Ordenação topológica é ordenação uma vez no grafo. conexos. linear de vértices em grafos Caminho hamiltoniano visita Grafos isomorfos possuem direcionados acíclicos. todos nós exatamente uma bijeções entre nós e arcos Componentes fortemente conexas vez, problema NP-completo. preservando conexões. são subconjuntos de nós Teorema: grafo conexo tem Grafos planares podem ser mutuamente acessíveis em caminho de Euler se possuir desenhados sem que arcos dígrafos. zero ou dois nós de grau se cruzem fora dos nós. ímpar. Grafos homeomorfos são Não existe critério simples obtidos por subdivisões para existência de caminho elementares de arcos. hamiltoniano em grafos gerais.