Trova tutti i sotto-grafo completo all'interno di un grafico

Question

C'è un algoritmo noto o metodo per trovare tutti i sub-grafo completo all'interno di un grafico? Ho un non orientato, grafo pesato e ho bisogno di trovare tutti sottografi all'interno di esso dove ciascun nodo del sottografo è collegato ad ogni altro nodo della sottografo.

C'è un algoritmo esistente per questo?

Answer 1

Questo è noto come il cricca problema ; è difficile ed è in NP-completo, in generale, e sì, ci sono molti algoritmi per farlo.

Se il grafico ha proprietà aggiuntive (ad esempio esso è bipartito), allora il problema diventa considerevolmente più facile ed è risolvibile in un tempo polinomiale, ma per il resto è molto difficile, ed è completamente risolvibili solo per piccole grafici.

Da Wikipedia

  

In informatica, il problema della cricca si riferisce a qualsiasi dei problemi legati alla ricerca di particolari sottografi complete ( "cricche") in un grafico, cioè insiemi di elementi in cui è connesso ogni coppia di elementi.

     

problema della cricca includono:

     

  
• trovare il massimo cricca (una cricca con il maggior numero di vertici),
  
• trovare una cricca peso massimo in un grafo pesato,
  
• elenco di tutte le cricche massimali (cricche che non può essere ingrandita)
  
• risolvere il problema decisionale di verificare se un grafo contiene una cricca più grande di una determinata dimensione.
  

     

Questi problemi sono affatto difficile: il problema decisionale cricca è NP-completo (uno dei 21 problemi NP-completi di Karp), il problema di trovare la massima cricca è sia-parametro fisso intrattabile e difficile da approssimare, e che elenca tutti massimale cricche possono richiedere un tempo esponenziale poiché esistono grafici con il esponenzialmente molte cricche massime. Tuttavia, ci sono algoritmi per questi problemi che vengono eseguiti in tempo esponenziale o che gestiscono talune grafici ingresso più specializzati in tempo polinomiale.

Vedi anche

• Bron-algoritmo Kerbosch

Answer 2

Bene il problema di trovare un sottografo k vertici in un grafico di dimensione n è di complessità

  

O (n ^ k k ^ 2)

Poiché ci sono sottografi n^k per controllare e ciascuno di essi hanno bordi k^2.

Cosa si sta chiedendo, trovando tutte le sottografi in un grafo è un problema NP-completo ed è spiegato nel algoritmo di Bron-Kerbosch sopra elencati.