pgcd.py

Created on February 21, 2024
1.39 KB
une arête est incidente quand elle 
relie 2 sommets

ordre : nbr total de sommets

degré d'un sommet: nbr d'arrêtes 
incidentes a ce sommet

graphe simple : si au plus une arête 
relie 2 sommets et s'il n'y a pas de 
boucle sur un sommet

graphe complet : s'il est non-orienté 
et ssi tous ses sommets sont adjacents

graphe orienté : ssi ses arêtes sont 
définies par une origine et une extrémité

chaîne : suite de sommets dans laquelle 2 
sommets consécutifs sont adjacents

longueur d'une chaîne : nbr d'arêtes qui 
composent la chaîne

chaîne fermée : premier et dernier sommet 
sont confondus

un cycle : chaîne fermée dont les arêtes 
sont distinctes

connexe : ssi 2 sommets distincts 
quelconques peuevent être reliés par une 
chaîne

une chaîne eulérienne est une chaîne qui 
contient chaque arête du graphe une et 
une seule fois. un cycle eulérien est une 
chaîne eulérienne fermée

dans le cas d'un graphe non-orienté, 
un graphe connexe admet une chaîne eulérienne 
ssi le nbr de sommets de degré impair vaut 0 
ou 2

il admet une cycle eulérien ssi ts ses sommets 
sont de degré pair. sinon s'il admet deux somment 
de degré impair alors se sont les 2 extrémités de 
la chaîne eulérienne. un graphe ayant plus de 2 
sommets de degré impair ne possède pas de chaîne 
eulérienne

la matrice d'adjacence est symétrique pour les 
graphes non-orientés