Graphes bipartis

Définition

Un graphe \( G = (V, E) \) est dit biparti s’il existe une partition de son ensemble de sommets en deux sous-ensembles \( V_1 \subseteq V \) et \( V_2 \subseteq V \) telle que chaque arête de \( E \) a une extrémité dans \( V_1 \) et l’autre dans \( V_2 \).

Question 1

Parmi les graphes suivants, colorie en gris(ou noir) et blanc les sommets des graphes bipartis, pour les autres graphes, écris dessous graphe non biparti.

Question 2

Justifie brièvement qu'un grpahe biparti ne peut pas posséder un cylce de longueur impair.

Question 3

Complète le code suivant

def est_bipart(g: list) -> bool:
    ...