abdou.py

Created on March 28, 2024
1.85 KB
# Type your text here
chaine = chemin reliant 2 sommets 
chaine fermé = allant de a et revenant a a
cycle = chaine fermé sans passer 2 fois a la mm arrets
connexe = un graphe est connexe si deux sommets dinstincs peuvent
etre reliés par une chaine 
matrice adjacence = tableau
soit G un graphe do'rdre n , la matrice d'adjacence A associe a g une matrice carré
d'ordre n ou chaque coef est egal au nbr d'arretes partant du sommet etudié
la matrice d'un graph non orienté est tjrs symetrique 
le  coef Pi,j de matrice A^p est egal au nbr de chaines de longueur  P qu irelie
le sommets i au sommet j


non orienté = pas fleche
orienté = fleche 
ordre d'un graph = nbr de sommets
degré = nbr d'arrets dont ce sommet est une extremité
graphe simple= pas de boucle + si 2 sommets distincts sont relié 
par au plus une arrets 
adjacents si 2 sommets sont relié par un pts

graphe d'ordre n>1 = complet si ses sommets sont 2 a 2 adjacents
 Dans un graphe non orienté, une chaîne est dite fermée lorsque son 
 premier sommet est également son dernier sommet.
 
 Dans un graphe orienté, un chemin est une liste ordonnée de sommets 
 telle que chaque sommet de cette liste soit adjacent au suivant en respectant 
 le sens de parcours.
  Un graphe est dit connexe si toute paire de sommets peut être reliée par 
  une chaîne.
  
  une chaine eulerienne est une chaine qui contient une fois et une seule fois 
  chaque arrets du graphe. un cycle eulerien est une chaine eulerienne fermée 
  theoreme d'euler : soit G un graph connexe, le graph G aune chaine eulerienne
  si et seulement si le nbr de sommets de degré impair est 1 ou 2 
  
  
  somme des degrés = 2 fois le nbr d'arrets 
  simple si complet et tout sommets adjacents
  chaine= suite d'arretse consecutives 
  
  pour avoir un cycle eulerien il faut que tte les sommets soit de degré pair