graphedefinition.py

Created by joelkouakou2080
Created on February 10, 2023
1.6 KB
1) Un graphe G = (X, E) est Eulerien
si il existe un chemin qui traverse
chaque arête exactement une fois. 
Autrement dit, tout sommet doit avoir
un degré pair pour qu'un graphe
soit Eulerien.

2) Un graphe G = (X, E) est Hamiltonien
s'il existe un chemin qui visite
chaque sommet exactement une fois
et retourne à son point de départ.

3) Un graphe G = (X, E) est un arbre
s'il est connexe et sans cycle,
c'est-à-dire s'il n'y a pas de 
chemin qui forme une boucle.

4) Un sous-graphe de G est un graphe 
qui est une partie de G et qui 
est défini par une sous-ensemble 
de sommets et une sous-ensemble 
d'arêtes de G.

5) L'algorithme de Prim est un 
algorithme de construction 
d'arbre couvrant de poids 
minimum dans un graphe connexe.
Il fonctionne en ajoutant 
progressivement des sommets
et des arêtes à un arbre en 
cours de construction, en 
choisissant toujours l'arête
de poids minimum entre un 
sommet déjà dans l'arbre et 
un sommet qui n'en fait pas 
partie. L'algorithme s'arrête 
lorsqu'il n'y a plus de sommets 
à ajouter à l'arbre.

6) Le graphe G' = (S, A') est
un graphe partiel de G, si A'
est inclus dans A. Remarque :
  Autrement dit, on obtient 
  G' en enlevant une ou plusieurs 
  arêtes au graphe G (sans toucher
  à ses sommets).
  
7) Un sous-graphe partiel de 
G est un graphe qui est formé
en prenant un sous-ensemble des
sommets et des arêtes de G. 
Autrement dit, un sous-graphe
partiel est une partie d'un 
graphe plus grand, qui conserve
les relations entre les sommets
sélectionnés. Les sommets et les
arêtes qui ne font pas partie
du sous-graphe sont exclus.