Please enable JavaScript.
Coggle requires JavaScript to display documents.
Conjunto Independente, Clique, Cobertura e Alocação Linear - Coggle Diagram
Conjunto Independente, Clique, Cobertura e Alocação Linear
-
-
🔹Cliques
-
-
-
Relação:
Encontrar o conjunto independente máximo em um grafo é equivalente a achar a clique máxima em seu grafo complementar.
Aplicações:
Agrupamentos (clusterização): clientes que compram os mesmos produtos.
Laboratórios: substâncias incompatíveis → o tamanho da clique máxima indica o número mínimo de refrigeradores necessários.
🔹Conjuntos Dominantes
Definição: conjunto de vértices tal que todos os outros vértices estão ligados a pelo menos um deles.
-
-
-
Aplicações:
Instalação de câmeras, luzes, radares, pontos de Wi-Fi, etc.
-
-
-
-
🔹 Relações Importantes
-
-
Conjunto Dominante Independente Dominante “cobre” todos os vértices, independente evita adjacência
-
-