Arc-en-ciel

On se donne un graphe non orienté de n sommets A, B, C ... dont les arêtes sont coloriées par les n couleurs a, b, c ...
Un tel graphe se trouve sur le schéma ci-contre. Les arêtes sont coloriées de huit couleurs différentes nommées a, b, c ...
Vous trouverez aisément un cycle hamiltonien (passant par tous les sommets) de ce graphe.
Vous remarquerez peut-être que les arêtes de ce cycle hamiltonien sont toutes de couleurs différentes, si c'est le cas, ce cycle s'appelle un "arc-en-ciel".

Plutôt qu'un diagramme du graphe on préfère souvent dessiner un tableau, c'est ce qui sera fait systématiquement pour chaque graphe, dans la suite.
Chaque case vide du tableau indique qu'il n'y a pas d'arête entre les deux sommets indiqués dans les marges, à gauche et en haut du tableau. (Les lettres Majuscules sont utilisées pour les sommets).
Lorsqu'une case contient une couleur a, b, c ... c'est qu'il existe une arête entre les deux sommets et que cette arête a la couleur indiquée dans la case du tableau (sous la forme d'une lettre minuscule).

Comme le graphe est non-orienté, le tableau est symétrique. Chaque arête correspond à deux arcs d'orientations contraires (et de même couleur).
Le graphe proposé est sans boucles, la diagonale principale du tableau est vide. Le graphe est propre, (deux arêtes ayant une même extrémité sont de couleurs différentes), chaque ligne et chaque colonne du tableau ne contient pas deux fois la même lettre.

Les graphes proposés ici sont construits pour contenir au moins un cycle hamiltonien multicolore appelé "arc-en-ciel".

La règle du jeu est de trouver un "arc-en-ciel".
Rien de plus simple ici, cliquez successivement sur certaines cases pour faire disparaître progressivement les arêtes jusqu'à obtenir n cases coloriées ou moins de couleurs différentes, au plus une par ligne et par colonne.
Avec un peu de chance vous aurez un cycle hamiltonien, sinon recommencez ou regardez la solution.
Pour simplifier la lecture du résultat, seul l'un des deux sens de parcours est affiché.
Attention, vous devez obtenir un seul cycle passant par tous les sommets et pas une réunion de deux cycles ou plus.

Lorsque vous cliquez dans une case (X, Y) du tableau contenant une lettre x, c'est que vous ne gardez que cet arc (X, Y) dans la couleur x.
L'application est capable d'en déduire un certain nombre d'actions qui consistent toutes à éliminer des arcs qui ne peuvent pas apparaître dans l'arc-en-ciel, compte tenu des choix précédents.
Deux niveaux sont proposés, cochez la case "Effectue toutes les simplifications possibles" pour effectuer un maximum les déductions. Vous pouvez annuler vos choix, dans l'ordre inverse, sauf si vous consultez la solution. Vous pouvez aussi revenir à la grille de départ, tant que vous ne changez pas de grille.

Nombre de sommets

Densité   1   2   3   4   5

Effectue toutes les simplifications possibles

1)  Cliquez ici ou encore là pour afficher cinq nouvelles grilles et leurs solutions ou pour les effacer.

2)  Inversement, entrez le graphe dans l'espace ci-dessous, selon le modèle indiqué et Cliquez ici.
(Vous pouvez aussi effacer l'espace) dim : 8 proba : 0.2 2 grille : --c-a-b----g-e--c---hg---g--fbdaa-hf-dec-egbd---b--de--f---ac-f- cycle : --c--------g--------h----------a-----d---e------b-------------f-

Dix feuilles contenant sur leurs premières pages six grilles de niveaux différents et sur leurs secondes pages les solutions. Les couleurs sont notées par des chiffres 1, 2 ... au lieu des lettres a, b ...
1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 .

Grilles 20×20 de la très simple à la compliquée 1 , 2 , 3 , 4 , 5 .