Comment savoir si un graphe est biparti?

Prises de GeeksforGeeks

Qui suit est un algorithme simple pour savoir si un graphe est Birpartite ou non à l'aide de Largeur de Recherche (BFS) :-

1. Attribuer la couleur ROUGE à la source de vertex (mise en jeu de U).
2. Couleur de tous les voisins qui est de couleur BLEUE (mise en jeu de V).
3. La couleur tout de voisin du voisin du par la couleur ROUGE (mise en jeu de U).
4. De cette façon, attribuer une couleur à tous les sommets tel qu'il satisfait à toutes les contraintes de m manière de coloriage problème où m = 2.
5. Lors de l'attribution des couleurs, si nous trouvons un voisin qui est de couleur avec la même couleur que l'actuel sommet, alors le graphe ne peut pas être coloré avec 2 sommets (ou graphique n'est pas Bipartite).

Un graphe biparti est possible que si le graphe de coloriage est possible à l'aide de
deux couleurs tels que les sommets dans un ensemble sont de couleur avec le même
couleur.

Aussi, REMARQUE :-

-> Il est possible de la couleur d'un cycle de graphique avec le même cycle à l'aide de deux couleurs.

-> Il n'est pas possible de la couleur d'un cycle de graphique avec odd cycle à l'aide de deux couleurs.

EDIT :-

Si un graphe n'est pas connecté, il peut ont plus d'un dédoublement. Vous devez vérifier que tous les composants séparément avec l'algorithme comme mentionné ci-dessus.

Donc, pour divers déconnecté sous-graphe de la même graphe, vous devez effectuer ce dédoublement vérifier sur chacun d'eux séparément à l'aide du même algorithme discuté ci-dessus. Tous ceux divers déconnecté sous-graphe de la même graphe en compte de son propre jeu de dédoublement.

Et, le graphique sera appelé bipartite, SI ET SEULEMENT SI chacune de ses composantes connexes sont révélés être bipartite .

OriginalL'auteur Am_I_Helpful

Ici est un Prologue de CLP(FD) solution. Juste le modèle de chaque arête dans le graphe en tant que variable dans le domaine 0..1. Ensuite, le modèle de chaque sommet comme une équation:

X #\= Y.

Ensuite question de l'étiquetage. Si l'étiquetage trouve une solution, vous avez terminé. Il pourrait trouver de multiples solutions. Ici est un terme pour votre exemple:

Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 7.3.23)
Copyright (c) 1990-2015 University of Amsterdam, VU Amsterdam

:- use_module(library(clpfd)).
problem(L) :- L=[A,B,C,D,E,F,G],
    A #\= E, A #\= F,
    B #\= E,
    C #\= E, C #\= F, C #\= H,
    D #\= G, D #\= H,
    E #\= A, E #\= B, E #\= C,
    F #\= A, F #\= C, F #\= G,
    G #\= F, G #\= D,
    H #\= C, H #\= D.

?- problem(L), L ins 0..1, label(L).
L = [0, 0, 0, 1, 1, 1, 0] ;
L = [1, 1, 1, 0, 0, 0, 1].

Travaille également en GNU Prolog, SICStus Prolog, Jekejeke Minlog etc.. surtout avec tout Prolog système qui met en œuvre le règlement CLP(FD). Peut également utiliser CLP(B) ou dif/2.

OriginalL'auteur j4n bur53

Ce qui suit est une BFS approche pour vérifier si le graphe est biparti.

• c = 0
• choisir un nœud x et définir x.class = c
• laisser ys être les nœuds obtenus par BFS
  • c = 1-c
  • pour y dans ys ensemble y.class = c
  • si tout y dans ys a un voisin z avec z.class == c alors le graphe n'est pas bipartite
  • répétez jusqu'à ce que plus les nœuds sont trouvés
• le graphe est biparti

Cela suppose que le graphe est une seule composante connexe, si elle n'est pas, il suffit de faire cette procédure pour chaque composant.

OriginalL'auteur mitchus

Faire plus simple.

Exécuter la composante fortement connexe de l'algorithme.

Si tout nœud de metagraph obtenu a plus de deux sommets alors le graphe n'est pas bipartite.

OriginalL'auteur Gurman SIngh