Coloration de graphe, WelshPowell et GreedyColoring ,BAC +3

[louisky]

Bonjour,

Pour un cours de graphe, il nous est demandé d'implémenter des algorithmes de colorations et de les tester avec des graphes différents et des ordres différents (croissant, décroissant, aléatoire : selon le degré).
Il nous est demandé d'implémenter certains algorithmes, tels que WelshPowell et GreedyColoring (sachant que nous ne devons pas re-ranger les graphes pendant WelshPowell ou Greedy).

Mon problème est le suivant : A force de tester WP et Greedy sur différents graphes, j'ai remarque qu'à chaque fois, mes 2 colorations étaient identiques. Je me suis donc demandé si, WP et Greedy renvoie la même coloration malgrè le fait qu'ils ne parcourent pas le graphe de la même façon.

Je ne vois pas comment prouver ou réfuter mon hypothèse. Je pense utiliser un raisonnement par l'absurde mais n'ayant rarement fait des maths ensemblistes, je suis un peu perdu.

J'ai tout d'abord énormément cherché sur internet si quelqu'un avait eu la même question que moi, je n'ai rien trouvé, que ce soit en français ou en anglais. Et actuellement je fais tourner mes 2 algos sur de multiples graphes en les rangeant aléatoirement et en m’arrêtant dès qu'il y aura une différence, je suis actuellement à 53 millions d'essais, d'où le fait que je crois de plus en plus en ma théorie.

Donc si vous pouvez m'aider sur une démonstration de ce problème ou simplement si vous avez un contre exemple en tête, je serais extrêmement reconnaissant de tout aide venant de votre part.

Merci pour votre lecture, et éventuellement, pour votre aide.
Cordialment, Louis.

[fatal_error]

Slt,

Où se trouve le code pour reproduire
Je subodore que tu crois runner les deux algos alors que tu runnes le meme

[GaBuZoMeu]

Si tu pars de la même liste de sommets et de la même liste de couleurs pour les deux algorithmes, c'est normal que tu trouves le même résultat.
Tu peux le démontrer par récurrence sur l'ordre dans la liste des sommets.
Tu as à voir que si tous les sommets avant s ont reçu la même couleur par WP et Greedy, alors c'est aussi le cas pour s.

[louisky]

Les algos WP et Greedy sont assez long, je les mettrais que si nécessaire mais voici comment je les appelle :

Code: Tout sélectionner

             
int sum = 0;
ArrayList<Integer> sortList = new QuickSort2(SortEnumerator.RANDOM).sortList;
long n = 0;
WellshPowell2 wp = new WellshPowell2((ArrayList<Integer>) sortList.clone());
GreedyColoring2 gc = new GreedyColoring2((ArrayList<Integer>) sortList.clone());
while(sum == 0){
    n+=1;
    sortList.clear();
    sortList = new QuickSort2(SortEnumerator.RANDOM).sortList;
    wp = new WellshPowell2((ArrayList<Integer>) sortList.clone());
    gc = new GreedyColoring2((ArrayList<Integer>) sortList.clone());
    sum = 0;
    for (int i = 0; i < Main.graphe.size(); i++){
        if (wp.colorList[i] != gc.colorList[i])
            sum++;
        }
}

Cependant, je ne retrie pas mes graphes, que ce soit dans WP ou Greedy.

[louisky]

Si tu pars de la même liste de sommets et de la même liste de couleurs pour les deux algorithmes, c'est normal que tu trouves le même résultat.
Tu peux le démontrer par récurrence sur l'ordre dans la liste des sommets.
Tu as à voir que si tous les sommets avant s ont reçu la même couleur par WP et Greedy, alors c'est aussi le cas pour s.

D'accord, je vais regarder cela. Merci !

[fatal_error]

On peut rien conclure de ton invocation car on sait pas ce que tu fais avec tes constructeurs Greedy et WP
Si tu fais rien et que dans les deux t'initialises la colorList à "par exemple" [0...], ben t'as même pas runné tes algos et tu trouves de fait la même chose

[GaBuZoMeu]

Si tu fais rien et que dans les deux t'initialises la colorList à "par exemple" [0...], ben t'as même pas runné tes algos et tu trouves de fait la même chose

Peux-tu écrire ça en clair ?


WP travaille en parcourant la liste des couleurs. Greedy travaille en parcourant la liste des sommets.
Je redis ce que j'ai déjà écrit. Si on part de la même liste de sommets et de la même liste de couleurs (en particulier on suppose que WP ne réarrange pas les sommets par ordre de degré décroissant), alors les deux algorithmes produisent le même résultat.

[fatal_error]

Peux-tu écrire ça en clair ?

oui désolé j'ai un peu oublié de changer de vocabulaire

Si tu fais rien et que dans les deux t'initialises la colorList à "par exemple" [0...], ben t'as même pas runné tes algos et tu trouves de fait la même chose ====>
Si les deux constructeurs WellshPowell2 et GreedyColoring2 ne font rien, alors le membre colorList a de forte chance d'être initialisé par le tableau ne contenant que des 0. Par conséquent, wp.colorList[i]===gc.colorList[i]===0

Je redis...

Je connais pas wp ni greedy, et je rejette pas non plus ce que t'as dit
c'était plus sur la méthodo: "je montre ce que j'ai fait et on réfléchit après"

[louisky]

Si tu pars de la même liste de sommets et de la même liste de couleurs pour les deux algorithmes, c'est normal que tu trouves le même résultat.
Tu peux le démontrer par récurrence sur l'ordre dans la liste des sommets.
Tu as à voir que si tous les sommets avant s ont reçu la même couleur par WP et Greedy, alors c'est aussi le cas pour s.

Je suppose donc que H<n> : le n-ième sommet a la même couleur que ce soit pour WP ou Greedy.

H<0> :
Il est clair que WP et Greedy colorient de la même façon le premier sommet.

H<n> => H<n+1>:
On suppose que les n premiers sommets ont été coloré de la même façon. Ici, je vois bien en quoi ça aide pour Greedy mais pas vraiment pour WP..
Pouvez-vous m'éclairer un peu plus ?

Merci

[GaBuZoMeu]

Le sommet s est de couleur c si c est la première couleur tel qu'il n'y a aucun voisin de s de couleur c parmi les sommets précédant s.
Montre que ça vaut à la fois pour Greedy et pour WP.

[louisky]

Le sommet s est de couleur c si c est la première couleur tel qu'il n'y a aucun voisin de s de couleur c parmi les sommets précédant s.
Montre que ça vaut à la fois pour Greedy et pour WP.

Bonjour,
Je vois très bien que, pour Greedy, si les n premiers sommets ont été coloré, alors le n+1 ème sommet dépendra de ses voisins colorés.

Cependant WP ne colore pas dans l'ordre qu'on lui a donné, il attribue la couleur 1, puis la 2 etc. Donc pour la récurrence dois-je partir du principe que WP a déjà tout colorier et que je compare juste les résultats ? Et surtout qu'est ce qui m'assure que WP ne va pas attribuer une couleur a un des voisins de n+1, que Greedy n'aurait pas fait, rendant impossible l'attribution de la même couleur ? C'est à ce point là que je bloque..

Cordialement, Louis.

[GaBuZoMeu]

Cependant WP ne colore pas dans l'ordre qu'on lui a donné, il attribue la couleur 1, puis la 2 etc. Donc pour la récurrence dois-je partir du principe que WP a déjà tout colorier et que je compare juste les résultats ?

Oui bien sûr.

Et surtout qu'est ce qui m'assure que WP ne va pas attribuer une couleur a un des voisins de n+1, que Greedy n'aurait pas fait, rendant impossible l'attribution de la même couleur ? C'est à ce point là que je bloque..

Je t'ai indiqué la marche à suivre et la chose à montrer :

Le sommet s est de couleur c si c est la première couleur tel qu'il n'y a aucun voisin de s de couleur c parmi les sommets précédant s.

C'est clair pour Greedy. Ça demande plus de réflexion pour WP. Tu peux commencer par voir pourquoi, si WP n'a pas encore colorié le sommet s et qu'on en arrive à la couleur d, il ne va pas colorier le sommet s avec la couleur d.

[louisky]

C'est clair pour Greedy. Ça demande plus de réflexion pour WP. Tu peux commencer par voir pourquoi, si WP n'a pas encore colorié le sommet s et qu'on en arrive à la couleur d, il ne va pas colorier le sommet s avec la couleur d.

Bonjour,

Je crois avoir compris avec cette indication :
Supposons que nous sommes à la couleur "d". Si le sommet "n+1" n'a pas encore été coloré, alors c'est que dans les voisins de n+1 il y a au moins toutes les couleurs de 1 à d-1. Si on peut colorer le sommet avec d, d est donc la plus petite couleur possible à attribuer, donc Greedy donnera la même. Si on ne peut pas le colorer avec la couleur d alors c'est que d a été attribué sur l'un des sommets de numéro < n+1, et donc Greedy ne pourra pas le colorer avec une autre couleur que, disons, la couleur "e" et WP devra attendre le tour de "e" pour colorer le somemt n+1.
Si le sommet "n+1" a été coloré, disons par la couleur "c", alors c était la plus petite couleur telle que aucun des voisins de n+1 n'avait cette couleur, et que toutes les couleurs plus petite que c sont présentes dans les voisins de n+1 avec un sommet < n +1.

Est-ce que j'ai bon ou j'oublie un ou des cas / simplie certaines parties ?

Encore merci pour votre aide !

[GaBuZoMeu]

Oui. J'écrirais ça comme ça.

Supposons que nous sommes à la couleur "d". Si le sommet "n" n'a pas encore été coloré, alors c'est que dans les voisins de n qui sont < n il y a toutes les couleurs < d. Si on peut colorer le sommet avec d, c'est donc que d est la plus petite couleur telle qu'il n'y a aucun voisin de n de cette couleur parmi les sommets < n.

[louisky]

Je vous remercie énormément !

[GaBuZoMeu]

Avec plaisir. Ça m'a permis d'apprendre quelque chose.