Il existe actuellement plusieurs petits jeux en Flash ou Java dont le principe est le suivant. On nous donne un graphe non orienté connexe G=(V,E), où V est l'ensemble des sommets et E l'ensemble des arêtes, et chaque sommet a initialement une couleur choisie parmi un ensemble fini fixé de c couleurs. On appelle une zone de couleur du graphe un sous-ensemble connexe de sommets ayant la même couleur.
Le jeu démarre avec un sommet particulier marqué/inondé(dans Flood-it)/contaminé(dans MadVirus)/... Ensuite le joueur choisit une suite de couleurs avec le mécanisme suivant : à chaque nouvelle couleur proposée, toutes les zones de cette couleur adjacentes à au moins un sommet marqué/inondé/contaminé deviennent marquées/inondées/contaminées. Le but du jeu est de parvenir à marquer/inonder/contaminer tous les sommets du graphe, en utilisant une suite de couleurs aussi courte que possible.
Dans Flood-It, le graphe est une grille carrée (les sommets sont des cases carrées qui sont adjacentes si elles partagent un coté commun). Dans MadVirus, le graphe est une grille hexagonale (idem avec des cases hexagonales). Au-delà du jeu, on modélise avec ces graphes et ces séquences de couleurs une dynamique de propagation par contact. Dans le jeu, on cherche à optimiser cette propagation pour qu'elle soit rapide.
Propagation de la zone marquée après la séquence de couleurs (bleu,vert,rouge,bleu) pour un damier 6×6
de Flood-It avec 3 couleurs.
Le sommet de départ est dans le coin en haut à gauche. La zone marquée est entourée par un trait gras, elle est remplie
par la dernière couleur proposée.
Trouver une suite de couleurs de longueur minimum pour marquer tout le graphe est un problème d'optimisation. En général le jeu se présente sous la forme du problème de décision associé : à chaque niveau correspond un graphe coloré avec son sommet initial marqué et un entier T, il faut alors trouver une suite qui parvient à marquer tout le graphe en moins de T étapes.
Est-ce que ces jeux sont faciles ? Quels algorithmes utiliser pour les résoudre ? Avec quelle complexité ? Très récemment une équipe de chercheurs de Bristol a obtenu plusieurs résultats théoriques pour Flood-It, notamment le fait que calculer la longueur minimum d'une suite qui marche est NP-dur, même s'il n'y a que 3 couleurs en jeu. Il reste malgré tout un bon nombre de questions à élucider.
Soient G1=(V1,E1) et G2=(V2,E2) deux graphes non orientés (resp. orientés), leur produit cartésien noté G1□G2 a pour sommets V1×V2 et pour arêtes (u1,u2)-(v1,v2) (resp. arcs (u1,u2)→(v1,v2)), si u1=v1 et u2v2∈E2, ou si u1v1∈E1 et u2=v2. Le produit cartésien de graphes a quelques bonnes propriétés comme le fait d'être associatif, commutatif et le graphe-singleton est un élément neutre (tout ça à isomorphisme près, car les étiquettes des sommets changent suivant la combinaison).
Exemple : produit cartésien C4□K3 de deux graphes orientés C4
et K3.
Dans les années 60, Sabidussi et Vizing ont montré que tout graphe non orienté fini se factorise de manière unique (à un isomorphisme près) sous forme d'un produit cartésien de graphes premiers (c'est à dire non factorisable par un plus petit graphe différent du singleton) comme illustré ci-dessous. Du point de vue algorithmique, une série d'algorithmes ont été proposés pour calculer cette factorisation pour les graphes non orientés. Le dernier en date par Imrich et Peterin (2007) effectue ce calcul depuis le graphe initial avec une complexité linéaire O(n+m) en n (nombre de sommets) et m (nombre d'arêtes). Pour les graphes orientés, Feigenbaum a montré en 1986 que la décomposition en facteurs premiers est aussi unique (à un isomorphisme près) et a proposé un algorithme qui commence par la factorisation d'un graphe non orienté, suivi d'un traitement supplémentaire de complexité O(n2log2n). Il semble donc qu'il n'y ait pas encore d'algorithme linéaire pour calculer la factorisation dans le cas orienté (il reste à faire un tout petit peu de bibliographie pour s'en assurer, par exemple il existe un algorithme alternatif dans le cas orienté par Walker dont la complexité est à vérifier).
Exemple de factorisation en graphes premiers : la décomposition du graphe non orienté G est
C5□K2□K2.
Récemment en étudiant la catégorie des treillis distributifs bornés, deux auteurs, Krebs et Schmid, ont été amené à développer un algorithme qui teste si un ordre (qui peut être vu comme un graphe orienté acyclique) peut se décomposer sous la forme P□K2 (noté P×2 dans le contexte des ordres). Ce problème est clairement plus simple que la factorisation complète d'un graphe orienté. Pourtant ces auteurs annoncent avoir un algorithme en O(n8) où n est le nombre de sommets. Cela semble un peu gros comme complexité, on doit pouvoir faire mieux rien qu'avec ce qu'il y a dans la littérature et il est vraisemblable qu'il existe une solution de complexité linéaire en le nombre de sommets et arcs (chaque arc représentant la relation "plus petit"). En tout cas, il reste des choses intéressantes à dire sur le problème de la factorisation des graphes pour le produit cartésien.