QCM - Couplage dans un graphe biparti

QCM - Couplage maximum dans un graphe biparti

Question 1. Un couplage d'un graphe est :

Un ensemble de sommets sans arête entre euxUn ensemble d'arêtes sans sommet communUn chemin passant par tous les sommetsUn cycle de longueur paire

Question 2. Un sommet est couvert par un couplage M si :

Il n'appartient à aucune arête de MIl appartient à exactement une arête de MIl appartient à au moins deux arêtes de MIl est adjacent à tous les autres sommets

Question 3. Un couplage parfait existe si :

Tous les sommets sont couverts par le couplageLe couplage contient $n$ arêtesLe couplage est maximalLe graphe est complet

Question 4. Un chemin $M$-augmentant est un chemin :

Dont toutes les arêtes sont dans $M$Alternant entre arêtes de $M$ et hors $M$, dont les extrémités sont libresDe longueur maximalePassant par tous les sommets couverts

Question 5. Si $P$ est un chemin $M$-augmentant, alors $M \Delta P$ est :

Un couplage de taille $|M| - 1$Un couplage de taille $|M| + 1$Un cheminUn cycle

Question 6. $M$ est un couplage maximum si et seulement si :

$M$ est maximalIl n'existe pas de chemin $M$-augmentantTous les sommets sont couverts$M$ contient $n-1$ arêtes

Question 7. Un graphe est biparti si :

Il possède un couplage parfaitSes sommets peuvent être partitionnés en deux ensembles sans arête à l'intérieur de chaque ensembleIl a un nombre pair de sommetsIl est connexe

Question 8. Un graphe est biparti si et seulement si :

Il est connexeIl n'a pas de cycle de longueur impaireIl a un couplage parfaitIl est planaire

Question 9. La complexité de l'algorithme de couplage maximum par chemins augmentants dans un graphe biparti est :

$O(n)$$O(n + p)$$O(n \cdot p)$$O(n^2)$

Question 10. La différence symétrique $A \Delta B$ est égale à :

$A \cap B$$A \cup B$$(A \setminus B) \cup (B \setminus A)$$A \times B$