les graphes

Construire une matrice d’adjacence ?

2 particularités d’une matrice d’adjacence ?

• ordre croissant/alphabetique

• Visualise le truc comme un tableau ou on note le nombre d’arrêtes reliant 2 sommets

• - elle est symétrique si non orienté

• - somme des coefficients = arrêtes*2

Combien de possibilités dans un graphe permettent de relier A à B en n arrêtes ?

M^{n};m_{A.B}^{(n)}

1. Ligne

2. Colonne

Def degré d’un sommet ?

Présenter le degré des sommets d’un graphe ?

• noté d(s) le nombre d'arêtes dont le sommet est une extrémité

• Tableau :

.Sommet.| A | B | C |

..Degré…| X | Y | Z |

Somme des degrés d’un graphe = ?

= somme des coefficients de la matrice d’adjacence = 2*nombre d’arrêtes

Def boucle

Arrête qui sort et rentre dans un sommet

Elle compte double : 1entrante et 1sortante

Graphe orienté vs non orienté

Orienté → les arrêtes ont un sens

Non orienté → les arrêtes n’ont pas de sens

Prouver que des graphes sont ou ne sont pas les memes ?

Leurs matrices d’adjacence

Def chaine fermée vs cycle « d’origine A »

• Chaine qui va d’un point à lui même

• Chaine qui va de A en A sans repasser par le meme point

Def chaine eulerienne vs cycle eulerien

• Chaine qui passe par toutes les arrêtes 1 seule fois

• Chaine eulerienne qui a le meme sommet de début et de fin

Quand est ce qu’un graphe admet des cycles euleriens ?

Quand tous ses sommets sont de degré pair

Quand est ce qu’un graphe admet des chaînes euleriennes ?

Quand il a exactement 2 sommet de degré impair

Sommet de départ

Sommet d’arrivée

Trouver une chaine eulérienne qui relie 2 points A et B ?

On crée une petite chaine entre les deux puis on utilise les cycles qui passent par un point

Déterminer l’ordre du graphe ?

Compter les sommets

Combien d’arrêtes ?

Somme des degrés des sommets / 2

Le graphe est il connexe ?

Oui → donner une chaine qui passe par tous les sommets

Non → donner 2 sommets qui ne peuvent pas être reliés par une chaine

Le graphe est-il complet ?

Oui → tous les sommets sont d’ordre n et il y a n+1 sommets

Non → donner 2 pts non adjacents

Peut-on passer par tous les points mais une seule fois chaque arrete ?

Oui → admet chaine d’Euler (2sommets impairs) (donc forcément connece)

Non → il y a « tant » de sommets impairs

Compléter une matrice de graphe ?

Utiliser le symetrique

Calculer en détaillant le coeff precis d’une matrice à une puissance ?

Je veux M^5 (=M^4 * M)

→ le coeff 8,2 = ligne 8 de M^4 * colonne 2 de M (ou l’inverse)

Presenter les degrés des sommets d’un graphe orienté

....Sommet….. |A | B | C |

.Degré entrant | X | Y | Z |

.Degré sortant.| U | V |W|

Def arc ou « arc orienté »

= arrête dans un graphe orienté

Def chemin

= chaine dans un graphe orienté

Def circuit

= cycle (≠ cycle eulerien) dans un graphe orienté

Dans quel sens on ecrit la matrice d’adjacence d’un graphe orienté ?

On compte le nombre d’arc permettant d’aller du sommet de la ligne au sommet de la colonne

Pk y a autant de degrés in que out ?

A → B

= 1 degré sortant de A

= 1 degré entrant dans B

Def puit

Un sommet qui n’a pas d’arc sortant

Def sommet répulsif

Sommet qui n’a pas d’arc rentrant

Def graphe simple ?

Graphe sans boucle ni arrêtes multiples