Les arbres générateurs de poids minimal (ou maximal) sont calculés à l’aide de l’algorithme de Kruskal

Chapitre 3.  Arbres   -   Solutions

Note.  Les arbres générateurs de poids minimal (ou maximal) sont calculés à l’aide de l’algorithme de Kruskal.  Les cas d’égalité sont tranchés de la façon suivante : les arêtes de même poids sont considérées selon l'ordre lexicographique.

3.        Nombre de sommets

Le nombre de sommets est égal à 99.

5.        Arbre générateur de poids minimal

L’arbre générateur obtenu de l’algorithme de Kruskal, en considérant les arêtes selon l'ordre lexicographique en cas d'égalité, contient les arêtes suivantes : 46, 45, 12, 14, 13 et 27.  Son poids est égal 2 + 3 + 4 + 5 + 8 + 12 = 34.

7.         Arbres générateurs de poids extrêmes

1. L’unique arbre générateur de poids minimal est composé des arêtes 28, 47, 49, 26, 59, 16, 65 et 38.  Son poids est de 81.
2. L’arbre générateur obtenu de l’algorithme de Kruskal, en considérant les arêtes selon l'ordre lexicographique en cas d'égalité, contient les arêtes suivantes :  34, 25, 23, 19, 37, 18, 15 et 16.  On obtiendrait un autre arbre optimal en remplaçant l’arête 16 par l’arête 56.  Le poids de ces arbres est de 312.
3. Il est impossible de construire un arbre GT dont tous les sommets aient le même degré (dans GT).  En effet, un arbre dont l’ordre n est supérieur à 1 contient toujours au moins deux sommets de degré 1.

17.         Liste des degrés d’un graphe

        (a)        (b)        (c)        (d)        (e)        (f)                        (g)      

Existence        Oui        Non        Oui        Oui        Oui        Non        Oui

Connexe        Oui        -        Oui ou non        Non        Oui ou non        -        Oui ou non

Arbre        Non        -        Oui ou non        Non        Non        -        Oui ou non

1. Ici, n = 5 + 2 = 7  et  a = [(5×2) +(2×5)] / 2 = 10.  Un tel graphe ne peut être un arbre, car a ≠ n – 1. Un tel graphe est nécessairement connexe : en effet, soit h un sommet de degré 5; alors, la composante connexe Ch de h contient au moins 6 sommets, lui-même et les 5 sommets auxquels il est adjacent; si Ch ≠ G, l’unique sommet n’appartenant pas à Ch est isolé et son degré est 0, ce qui contredit l’hypothèse que v0 = 0.  La figure ci-dessous donne un graphe qui répond aux conditions de l’énoncé.

[pic 1]

1. Il n’existe pas de graphe répondant aux conditions indiquées.  En effet, le total dT des degrés des différents sommets d’un tel graphe se calculerait comme suit :  dT  =  (1×1) + (3×2) +(2×3) = 13.  Or, dans tout graphe, dT est pair puisqu’il est égal à 2a, où a est le nombre d’arêtes.
2. Ici, n = 11  et  a = 10.  Un tel graphe peut être ou non un arbre, peut être ou non connexe.  La figure ci-dessous donne un arbre qui répond aux conditions de l’énoncé.  On obtient un graphe non connexe – et qui n’est donc pas un arbre – en retranchant les arêtes 67 et 68 et en ajoutant des arêtes 56 et 78 (après ces changements, d5 = 4 et d6 = 3).

[pic 2]

1. Ici, n = 9  et  a = 6.  Un tel graphe ne peut être un arbre, car a ≠ n – 1.  Il ne peut non plus être connexe, car a < n – 1 (voir l’exercice 13).  La figure ci-dessous donne un graphe non connexe qui répond aux conditions de l’énoncé.

[pic 3]

1. Ici, n = 9  et  a = 12.  Un tel graphe ne peut être un arbre, car a ≠ n – 1.  Il peut être ou non connexe.  La figure ci-dessous donne un graphe connexe qui répond aux conditions de l’énoncé.  On obtient un graphe non connexe en retranchant les arêtes 17 et 69 et en ajoutant des arêtes 16 et 79.

[pic 4]

1. Il n’existe pas de graphe répondant aux conditions indiquées. En effet, un tel graphe contiendrait seulement n = 2 + 2 + 2 = 6 sommets; or, dans un graphe d’ordre 6, il est impossible de trouver un sommet de degré 6.
2. Ici, n = 9  et  a = 8.  Un tel graphe peut être ou non un arbre, peut être ou non connexe.  La figure ci-dessous donne un arbre qui répond aux conditions de l’énoncé.  On obtient un graphe non connexe – et qui n’est donc pas un arbre – en retranchant l’arête 23 et en ajoutant une arête 38 (après ces changements, d2 = 1 et d8 = 2).

[pic 5]

...