Please enable JavaScript.
Coggle requires JavaScript to display documents.
Introdução à Teoria dos Grafos - Coggle Diagram
Introdução à Teoria dos Grafos
🔹 Conceito
Grafo: estrutura matemática composta por vértices (nós) e arestas (ligações).
Usado para representar relações entre objetos.
Exemplos:
Rede social (pessoas ↔ conexões)
Cidades e estradas
Computadores e conexões de rede
🔹 Elementos do Grafo
Vértices (V): pontos ou entidades.
Arestas (E): ligações entre vértices.
Ordem: número de vértices.
Tamanho: número de arestas.
🔹Tipos de Grafos
Grafo simples: não tem laços (arestas que ligam o vértice a si mesmo) nem múltiplas arestas entre os mesmos vértices.
Grafo múltiplo: possui mais de uma aresta entre o mesmo par de vértices.
Grafo com laço: possui aresta que conecta um vértice a ele mesmo.
Grafo completo (Kn): todos os vértices estão conectados entre si.
Grafo bipartido: vértices divididos em dois conjuntos, e arestas só ligam vértices de conjuntos diferentes.
Grafo ponderado: cada aresta tem um peso (distância, custo, tempo etc.).
Grafo dirigido (ou orientado): arestas têm direção.
Grafo não dirigido: arestas sem direção.
🔹Representação de Grafos
Matricial: usa matriz de adjacência (arestas entre vértices) ou matriz de incidência (relação entre vértices e arestas).
Listas de adjacência: armazenam quais vértices estão ligados a cada vértice.
🔹 Grau de um Vértice
Grau: número de arestas incidentes a um vértice.
Em grafos dirigidos:
Grau de entrada (in-degree): número de arestas que chegam ao vértice.
Grau de saída (out-degree): número de arestas que saem dele.
Teorema do aperto de mãos: a soma dos graus de todos os vértices é igual ao dobro do número de arestas.
🔹Subgrafos e Caminhos
Subgrafo: parte de um grafo que contém subconjuntos de vértices e arestas.
Caminho: sequência de vértices conectados por arestas.
Ciclo: caminho que começa e termina no mesmo vértice.
Conexo: existe caminho entre todos os vértices.
Desconexo: há vértices isolados (sem caminho entre si).
🔹Aplicações dos Grafos
Transporte e logística.
Planejamento de rotas (GPS).
Redes elétricas, de comunicação e sociais.
Programação e estruturas de dados.
🔹 8. Estrutura sugerida para o Mapa Mental
Teoria dos Grafos (nó central)
Conceito
Elementos
Vértices
Arestas
Tipos de Grafos
Simples
Múltiplo
Com laço
Completo (Kn)
Bipartido
Ponderado
Dirigido / Não dirigido
Representações
Matriz de adjacência
Matriz de incidência
Lista de adjacência
Grau dos vértices
Grau, entrada, saída
Teorema do aperto de mãos
Subgrafos e Caminhos
Subgrafo
Caminho e Ciclo
Conexo e Desconexo
Aplicações