Please enable JavaScript.
Coggle requires JavaScript to display documents.
MM7 - Grafos pt3, Grafos Especiais, Grafos Bipartidos - Coggle Diagram
-
Componentes Conectados
- Conjunto de vértices em que qualquer vértice pode alcançar qualquer outro
- Em grafos direcionados, pode haver componentes fortemente e fracamente conectados
- DFS ou BFS são usados para identificá-los
Grafos Acíclicos
-
- Direcionados acíclicos são chamados de DAGs
- Usados em problemas de dependência e ordenação
Árvores
- Grafos conectados e acíclicos
- Com N vértices e N - 1 arestas
- Qualquer par de vértices possui exatamente um caminho entre eles
- Aplicações em hierarquias, estruturas de diretórios, MSTs
Florestas
- Conjunto de árvores desconectadas
Grafos Completos
- Cada par de vértices está conectado por uma aresta
- Máximo de conexões possíveis
Grafos Ponderados
- Arestas possuem pesos ou custos
- Base para algoritmos de caminho mínimo e árvores geradoras
Grafos Não Ponderados
- Todas as arestas têm o mesmo peso
- Usados em BFS e problemas de distância uniforme
-
-
Grafos Bipartidos
Conceito
- Conjunto de vértices dividido em dois grupos
- Não existem arestas entre vértices do mesmo grupo
- Todas as arestas ligam um vértice de um grupo a outro
Identificação
- Pode ser verificado usando BFS ou DFS
- Alterna cores (ex: vermelho e azul) a cada nível
- Se algum vértice vizinho tiver a mesma cor, o grafo não é bipartido
Aplicações
- Problemas de emparelhamento máximo
- Alocação de tarefas (matching)
- Redes de fluxo e divisão de grupos
Propriedades
- Grafos sem ciclos ímpares são bipartidos
- Grafos bipartidos não contêm triângulos
Representação em código
- Usar vetor de cores para marcar os grupos
- BFS para colorir alternadamente
-
-