Corrigé du 2e CC de Graphes, automne 2020

Q1: Par définition, le poids d'une arête est d'autant plus petit que ses extrémités sont éloignées. Donc à chaque étape, on choisira parmi les arêtes disponibles celle dont les extrémités sont les plus éloignées.
i=1: racine 0. Arborescence partielle ({0},{}).
i=2: joindre 0 au plus éloigné parmi 1,2,3,4: arête 04 de poids 3. Arborescence partielle ({0,4},{04}).
i=3: entre 0,4 d'une part et 1,2,3 d'autre part, sélectionner les extrémités les plus éloignées: on a le choix entre les arêtes 03 et 14, toutes deux de poids 4; choisissons 03. Arborescence partielle ({0,3,4},{04,03}).
i=4: entre 0,3,4 d'une part et 1,2 d'autre part, sélectionner les extrémités les plus éloignées: arête 14 de poids 4. Arborescence partielle ({0,1,3,4},{04,03,14}).
i=5: joindre 2 au plus éloigné parmi 0,1,3,4; on a le choix entre les arêtes 02 et 24, toutes deux de poids 6. Le premier choix donne l'arbre couvrant {04,03,14,02}, le deuxième l'arbre couvrant {04,03,14,24}, tous deux minimaux (somme des poids =3+4+4+6=17).
Il n'y a pas d'autre ACM que ces deux-là. En effet, ils utilisent toutes les arêtes des deux plus petits poids (p(04)=3, p(03)=p(14)=4) et une arête (02 ou 24) du troisième plus petit poids 6. La seule autre arête de poids 6 est 13, qui ne connecte pas 2 à {0,1,3,4} mais crée un cycle dans ces 4 sommets. Par conséquent, tout autre arbre couvrant devra avoir au moins une arête avec un poids supérieur, et ne sera pas minimal

Q2: Rappel: "arbre" = "graphe non orienté connexe sans cycle", donc on a trois définitions équivalentes pour une forêt:
- graphe non orienté sans cycle;
- graphe non orienté dont chaque composante connexe engendre un arbre;
- union disjointe d'arbres.

Ainsi: une forêt n'a pas de cycle, donc elle n'a pas de cycle de longueur impair, ce qui par un théorème vu en cours implique: c'est un graphe biparti. Réponse OUI.

Autre façon de voir: dans chaque arbre de la forêt, choisir un sommet racine; l'arbre enraciné peut être vu comme une arborescence, on y colorie en rouge les sommets de profondeur paire et en vert ceux de profondeur impaire; deux sommets adjacents ont leurs profondeurs différant de 1, donc sont de couleurs opposées.

Remarque: en cours, j'ai dit que les deux parties S1 et S2 forment une partition, ce qui sous-entend qu'elles sont toutes deux non vides, en d'autres termes les deux couleurs rouge et vert sont utilisées. Néanmoins, on admet que si une partie est vide ou même les deux le sont, en d'autres termes si on n'utilise pas les deux couleurs, le graphe reste biparti. C'est en particulier le cas pour un graphe à 0 ou 1 sommet, qui est biparti. Il n'est donc pas nécessaire de séparer ce cas particulier.

Q3: Soit N le nombre de sommets et F le nombre de feuilles; on a N = F + 10. Le degré sortant des feuilles est 0, donc la somme des degrés sortants de tous les sommets, tant feuilles que non-feuilles, est 22+0 = 22. Tous les sommets des 3 arborescences ont le degré entrant 1, sauf les 3 racines de degré entrant 0. Donc la somme des degrés entrants de tous les sommets vaut N-3. Par le théorème des degrés, la somme des degrés sortants de tous les sommets est égale à la somme des degrés entrants de tous les sommets. Cela donne l'équation
    22 = N - 3 = F + 10 - 3,
d'où F = 15. Il y a 15 feuilles.

Remarque: On ne peut pas raisonner en comptant "la somme des degrés entrants des sommets non-feuilles" ou "la somme des degrés entrants des feuilles". En effet, un sommet isolé forme une arborescence, où le sommet est à la fois racine et feuille. Ainsi le graphe peut avoir 0, 1 ou 2 sommets isolés, ou racines feuilles, ce qui implique que la somme des degrés entrants des 10 sommets non-feuilles vaut 7, 8 ou 9, tandis que la somme des degrés entrants des 15 feuilles vaut 15, 14 ou 13.

Q4: inutile de dessiner le graphe; d'expérience, cela peut conduire à des erreurs.
Pour le choix des racines et des voisins sortants, je suis l'ordre des sommets et des arcs donné dans l'énoncé.

Liste =  [];
racine a: d(a)=1; pere(a)=NIL;
arc ab: d(b)=2; pere(b)=a;
arc bc: d(c)=3; pere(c)=b;
arc ce: d(e)=4; pere(e)=c;
pas de voisin sortant blanc de e: f(e)=5; Liste = [e];
retour à pere(e)==c;
pas de voisin sortant blanc de c: f(c)=6; Liste = [c,e];
retour à pere(c)==b;
arc bf: d(f)=7; pere(f)=b;
pas de voisin sortant blanc de f: f(f)=8; Liste = [f,c,e];
retour à pere(f)==b;
pas de voisin sortant blanc de b: f(b)=9; Liste = [b,f,c,e];
retour à pere(b)==a;
pas de voisin sortant blanc de a: f(a)=10; Liste = [a,b,f,c,e];
pere(a)==NIL: fin d'arborescence;
racine d: d(d)=11; pere(d)=NIL;
pas de voisin sortant blanc de d: f(d)=12; Liste = [d,a,b,f,c,e];
pere(d)==NIL: fin d'arborescence;
racine g: d(g)=13; pere(g)=NIL;
pas de voisin sortant blanc de g: f(g)=14; Liste = [g,d,a,b,f,c,e];
pere(g)==NIL: fin d'arborescence;
plus de sommet blanc: fin.

Tri topologique: g,d,a,b,f,c,e.

Table des débuts, fins et pères des sommets:

  |d()|f()|pere()
--+---+---+------
a | 1 |10 | NIL
b | 2 | 9 | a
c | 3 | 6 | b
d |11 |12 | NIL
e | 4 | 5 | c
f | 7 | 8 | b
g |13 |14 | NIL