Avez-vous des conseils sur la façon de déterminer si un graphe non orienté peut être coloré avec seulement 2 couleurs? Comment cela pourrait-il être implémenté dans Java?Déterminer si un graphe non orienté peut être coloré en utilisant seulement 2 couleurs
Faites un breadth-first search sur le graphique. À chaque profondeur égale, coloriez les nœuds d'une couleur, disons rouge, et aux profondeurs impaires, vous coloriez les nœuds en bleu. Chaque fois que vous avez un bord non-arbre (un bord entre deux nœuds que vous avez déjà visité), vérifiez que les couleurs sont différentes. Si le graphique a plusieurs composants connectés, vous répétez simplement la recherche sur chaque composant.
Cela revient à déterminer si le graphique est bipartite. Pour ce faire, vous devez vérifier si un cycle impair existe dans le graphique. Pour cela, vous effectuez une recherche en largeur sur le graphique. Si à n'importe quel niveau dans le BFS, il y a un bord entre les nœuds du même niveau, alors le graphique n'est pas bipartite, c'est-à-dire qu'il ne peut pas être coloré en utilisant seulement 2 couleurs. (En supposant que la contrainte est que les nœuds adjacents doivent être de couleurs différentes)
Des contraintes? juste couleur n/2 nœuds avec couleur 1 et n/2 nœuds avec couleur 2 =) – Enrique
J'ai trouvé une question similaire qui pourrait vous aider, http://stackoverflow.com/questions/1838934/checking-for-odd-cycles-in -an-undirected-graph –
ce qui me trouble est le fait que nous sommes supposés prouver s'il est possible ou non de colorier un graphe non orienté en utilisant 2 couleurs. – rdplt