Yop les gars, je dois coder une appli en C#, et une classe de cette appli concerne des calculs sur des graphes à partir de leur matrice d'adjacence.
Je dois faire une méthode qui calcul le noyau d'un graphe. Pour cela j'applique l'algorithme suivant :

-> Trouver si il y a au moins une ligne de 0.
-> Si oui, prendre la colonne à l'indice de cette ligne.
-> Si il y a des 1 sur cette colonne, supprimer les lignes et les colonnes à l'indice des 1.
-> Si il y a une nouvelle ligne de 0 qui apparaît, recommencer l'opération.

L'algorithme ne me pose pas de problème en soit, mais la question est : quand l'appliquer ? En effet, il n'est pas valable pour un graphe de ce genre : 1 relié à 2, 2 relié à 3, 3 relié à 4, 4 relié à 1, qui a pourtant 2 noyaux possibles : soit {1, 3} soit {2, 4}.
Est ce que je n'applique l'algo qu'au cas où il n'y a pas de lignes de 0 dans ma matrice ? Sachant qu'en cours on nous a dit qu'il y en avait forcément, affirmation réfutée par l'exemple du dessus ... £


Merci

This post was edited by Bremen on Oct 12 2013 11:04am

la réponse D

Ton algo a pas l'air de traiter le cas des graphes cycliques ou t'auras jamais de ligne de 0, après s'ils t'ont dit l'inverse en cours ça me parait bizarre mais t'es sûr qu'ils ne parlaient pas juste des graphes acycliques ?

L'algo que tu décris n'a aucun sens pour un graphe non orienté. Il trouvera juste les sommets isolés. A mon humble avis, il ne marche que sur les graphes orientés sans cycle.

This post was edited by Hubbard on Oct 12 2013 11:29am

Ouais justement c'est bien le problème, je sais pas quoi appliquer dans le cas d'un graphe non orienté / cyclique. Après pour les graphes non orientés le seul problème c'est les boucle, suffit juste que je transforme les 2 de la matrice en 1 et ca fonctionne aussi bien je suppose.

Décider si un graphe orienté quelconque admet un noyau est NP-complet. Je ne pense pas qu'ils te demandent de coder un solveur pour un problème de ce type-là...

hm ok ... Du coup je me demande comment je vais faire xD

ça a l'air trop frais ce que tu fais lol

En regardant vite fait sur internet, ton algo correspond à la recherche d'un noyau dans un graphe orienté sans circuit.
En effet, dans ce cas précis tu as l'existence et l'unicité du noyau (une démo possible est l'application de ton algo).

Comme l'a précisé Hubbard, ça m'étonnerait que tu ais à trouver un noyau dans un graphe non orienté, ou orienté avec circuit.
Surtout que dans le cas orienté avec circuit, le noyau n'existe pas forcément... Ex : 3 sommets qui forment une boucle.

Btw, si tu trouves un algo qui résout un problème NP-Complet, je pense que ça risque d'en intéresser plus d'un...

Ok, merci de votre aide les gars, j'ai envoyé un mail à mon prof pour en savoir un peu plus, pas envie de me faire piéger quand il va nous filer son main