Trouver tous les sous-graphiques complets dans un graphique

Est-il un algorithme connu ou méthode pour trouver tous les sous-graphes dans un graphique? J'ai un non-orienté, graphe non pondéré et j'ai besoin de trouver tous les sousgraphes dans lequel chaque nœud du graphe est connecté à chaque autre nœud dans le graphe.

Est-il un algorithme pour cela?

source d'informationauteur Mantas Vidutis

  1. 14

    Ceci est connu comme la problème de la clique; il est dur et est NP-complet en général, et oui il existe de nombreux algorithmes pour ce faire.

    Si le graphe possède des propriétés supplémentaires (par exemple, il est bipartite), alors le problème devient beaucoup plus facile et est résoluble en temps polynomial, mais sinon c'est très dur, et est complètement résoluble uniquement pour les petits graphes.

    De Wikipedia

    En informatique, le problème de la clique se réfère à l'un des problèmes lié à la découverte de particulier complète sousgraphes ("cliques") dans un graphe, c'est à dire, des ensembles d'éléments où chaque paire d'éléments est connecté.

    Clique problèmes sont les suivants:

    • trouver le maximum d'une clique (un clique avec le plus grand nombre de sommets),
    • trouver un poids maximum d'une clique dans un graphe pondéré,
    • liste de toutes les cliques maximales (cliques qui ne peut pas être agrandie)
    • résoudre le problème de décision de tester si un graphe contient une clique de taille supérieure à une taille donnée.

    Ces problèmes sont tous dur: la clique problème de décision est un problème NP-complet (l'un de Karp 21 NP-complet problèmes), le problème de trouver la clique maximale est à la fois à paramètre fixe insolubles et dur à approximatives, et le listing de toutes les cliques maximales peut exiger de temps exponentiel qu'il existe des graphes de façon exponentielle avec beaucoup de cliques maximales. Néanmoins, il existe des algorithmes pour ces problèmes qui s'exécutent en temps exponentiel ou qui traitent certains plus spécialisés entrée des graphiques en temps polynomial.

    Voir aussi