Résolution de problèmes à l'aide de graphes

Résumé du document

Un graphe est constitué de sommets dont certains sont reliés par des arêtes.
Deux sommets x et y sont dits adjacent s'ils sont reliés par une arête.
Le degré est le nombre d'arêtes dont il est l'une des extrémités.
L'ordre d'un graphe est le nombre de sommets du graphe (...)

Extraits

[...] Résolution de problème à l'aide de graphe I. Vocabulaire des graphes et matrices associées A. Graphe non orienté Un graphe est constitué de sommets dont certains sont reliés par des arêtes. Deux sommets x et y sont dits adjacent s'ils sont reliés par une arête. Le degré est le nombre d'arête dont il est l'une des extrémités. L'ordre d'un graphe est le nombre de sommet du graphe. Exemples Soit le graphe G : Un sous graphe du graphe G est un graphe G' composé de certains sommets de G avec toutes les arêtes qui les relient : Un sous graphe stable est un sous graphe sans arête : Un graphe complet est un graphe dont chaque sommet est relié à tous les autres : Propriété La somme des degrés des sommets d'un graphe non orienté est égale à deux fois le nombre d'arête du graphe. [...]

[...] Remarque Un graphe complet est connexe. Propriété A est une matrice associée à un graphe G. P est un entier naturel non nul. Le terme situé à l'intersection de la ligne i et de la colonne j de la matrice AP donne le nombre de chaine de longueur P reliant le sommet i au sonnet j. Remarque Il existe une propriété analogue pour les graphes orientés - La distance entre deux sommets est la plus courte longueur de chaine reliant ces deux sommets. [...]