Please enable JavaScript.
Coggle requires JavaScript to display documents.
Grafos - Coggle Diagram
Grafos
Tipos
Não direcionado
Pares de vértices são não ordenados (u, v) = (v, u)
Vértices u e v são adjacentes
Arestas não direcionadas (u, v)
Direcionado (digrafo)
Pares de vértices são ordenados (u, v) ≠ (v, u)
Aresta (u, v) é direcionada de u (cauda) para v (cabeça)
Arestas direcionadas (u, v)
Lacetes
Arestas conectando vértices a si mesmos (não considerados por padrão)
Grafos Ponderados
Definição: Grafos com pesos atribuídos às arestas
Aplicações: Caminho mais curto, problema do caixeiro viajante
Representação
Matriz de Pesos: A[i, j] contém o peso da aresta de i para j
Listas de Adjacência: Incluem pesos das arestas
Caminhos e Ciclos
Ciclo
Caminho que começa e termina no mesmo vértice
Acíclico: Grafo sem ciclos
Conectividade
Grafo Conectado: Caminho entre qualquer par de vértices
Componentes Conectados: Subgrafos conectados maximalmente
Caminho
Sequência de vértices adjacentes de u a v
Simples: Todos os vértices distintos
Comprimento: Número de arestas no caminho
Notação e Exemplos
Exemplo de grafo não direcionado: 6 vértices, 7 arestas
V = {a, b, c, d, e, f}
E = {(a, c), (a, d), (b, c), (b, f), (c, e), (d, e), (e, f)}
Exemplo de digrafo: 6 vértices, 8 arestas
V = {a, b, c, d, e, f}
E = {(a, c), (b, c), (b, f), (c, e), (d, a), (d, e), (e, c), (e, f)}
Definição
Formal
G = (V, E)
V: Conjunto finito de vértices
E: Conjunto de pares de vértices (arestas)
Informal
Pontos (vértices/nós) e segmentos de linha (arestas/arcos)
Representação
Matriz de Adjacência
Matriz boolean n x n
Elemento (i, j) = 1 se há aresta de i para j, 0 caso contrário
Simétrica para grafos não direcionados
Listas de Adjacência
Coleção de listas ligadas
Cada lista contém vértices adjacentes a um vértice específico
Usado para grafos esparsos devido ao uso eficiente de espaço
Completo, denso e esparso
Grafo Completo: Cada par de vértices está conectado (K|V|)
Grafo Denso: Poucas arestas faltantes
Grafo Esparso: Poucas arestas em relação ao número de vértices