On vous demande de réaliser une classe Arbre, qui héritera de Graphe, et qui permettra :
- d'obtenir le codage de Prüfer de l'arbre,
- de trouver un arbre couvrant.
Initialisation de la classe
Construire la base de la classe Arbre.Vous lui incorporerez un constructeur,
- qui fera appel au constructeur de la superclasse Graphe,
- qui vérifiera que le graphe est bien un arbre (appel à la méthode est_arbre de la superclasse).
Feuilles et noeuds
Faire les méthodes :
- est_feuille(i), qui renvoie vrai si et seulement si le sommet $i$ est une feuille (i.e. de degré 1).
- est_noeud(i), qui renvoie vrai si et seulement si le sommet $i$ n'est pas une feuille.
Codage de Prüfer
Faire une méthode get_prufer qui renvoie le codage de Prüfer de l'arbre considéré.
De même, faire une méthode set_prufer, qui construit l'arbre à partir de la liste d'entiers donnée en paramètres.
Arbre couvrant
- Ajoutez une méthode est_couvrant(G) à votre classe Arbre.
Elle renverra vrai si l'objet Arbre instancié est effectivement un arbre couvrant du graphe $G$.
- Ajoutez une méthode kruskal à votre classe Arbre, qui retourne l'arbre couvrant de poids minimal pour le graphe considéré.