Please enable JavaScript.
Coggle requires JavaScript to display documents.
Representação e Tipos de Grafos - Coggle Diagram
Representação e Tipos de Grafos
🔹Representações de Grafos
Formas de descrever como os vértices e arestas estão conectados:
a) Lista de Arestas
Mostra diretamente quais vértices estão ligados.
Exemplo:
Arestas: (a, b), (b, c), (c, d)
b) Matriz de Adjacência
Representa o grafo em uma matriz quadrada.
Linhas e colunas representam vértices.
Valor 1 → existe aresta entre vértices; 0 → não existe.
Em grafos direcionados, a matriz não é simétrica.
Em grafos não direcionados, é simétrica.
c) Matriz de Incidência
Mostra a relação entre vértices e arestas.
Cada coluna representa uma aresta, e cada linha, um vértice.
d) Lista de Adjacência
Para cada vértice, lista todos os vértices adjacentes.
É uma forma eficiente para grafos grandes e esparsos.
🔹Classificação dos Grafos
a) Grafo Simples
Sem laços e sem múltiplas arestas.
b) Grafo Multigrafo
Permite mais de uma aresta entre o mesmo par de vértices.
c) Grafo com Laço
Possui arestas que conectam um vértice a ele mesmo.
d) Grafo Direcionado (ou Orientado)
Arestas possuem direção (indicada por setas).
Exemplo: redes sociais (seguir ≠ ser seguido).
e) Grafo Não Direcionado
Arestas sem direção — conexão mútua.
Exemplo: amizade entre pessoas.
f) Grafo Ponderado
Cada aresta tem um peso (distância, custo, tempo etc.).
g) Grafo Bipartido
Conjunto de vértices dividido em dois subconjuntos disjuntos, e arestas só ligam vértices de conjuntos diferentes.
h) Grafo Completo (Kn)
Todos os vértices conectados entre si.
Número de arestas = n(n−1)/2.
i) Grafo Regular
Todos os vértices têm o mesmo grau.
🔹Grau de um Vértice
Grau (d(v)): número de arestas incidentes em um vértice.
Em grafos dirigidos:
Grau de entrada (in-degree) = número de arestas que chegam.
Grau de saída (out-degree) = número de arestas que saem.
Propriedade:
A soma dos graus de todos os vértices = 2 × número de arestas.
(Teorema do aperto de mãos)
🔹Tipos Especiais de Grafos
Tipo de Grafo Característica Principal Exemplo
Completo Todos conectados Rede totalmente ligada
Bipartido Dois conjuntos disjuntos Alunos ↔ Projetos
Regular Mesmo grau em todos vértices Malhas elétricas
Ponderado Arestas com peso Mapa de rotas
Direcionado Arestas com direção Redes sociais
🔹 Aplicações
Planejamento de rotas (GPS, logística).
Redes elétricas e de comunicação.
Representação de relacionamentos (amigos, conexões).
Modelagem de processos e fluxos.
🔹Estrutura para o Mapa Mental
Representação e Tipos de Grafos (nó central)
Representações
Lista de Arestas
Matriz de Adjacência
Matriz de Incidência
Lista de Adjacência
Classificação
Simples / Multigrafo / Com laço
Direcionado / Não direcionado
Ponderado
Bipartido
Completo (Kn)
Regular
Grau dos Vértices
Grau, entrada e saída
Teorema do aperto de mãos
Tipos Especiais
Completo
Bipartido
Regular
Ponderado
Direcionado
Aplicações