Définitions générales mathématiques

Définitions générales

Arc : Trait ou courbe avec une flèche (orienté) reliant deux sommets. Ex : F-G

Arête : Trait ou courbe (non-orienté) reliant deux sommets.

Ex : A-B

Degré d’un sommet : Nombres de fois où une arête (ou un arc) touche un sommet. Ex : Sommet E = 3, sommet G = 4

Ordre d’un graphe L’ordre d’un graphe correspond au nombre de sommets qu’il détient. Ex : Le graphe ABCDE est d’ordre 5

Graphe : Un ensemble contenant des sommets qui sont reliés par des arêtes (ABCDE) ou des arcs (FGHIJ).

Graphe orienté : Graphe utilisant des arcs au lieu des arêtes. Ex : Le graphe FGHIJ

Graphe valué : Graphe construit avec des arêtes contenant des valeurs positives.

Sommet : Point relié par des arcs ou des arêtes.

Chaîne : Les sommets sont reliés par une arête entre eux de façon continue. Ex : A-B-C-B-E, M-N-O-L-N-O

Chaîne Simple : Une chaîne qui n'utilise jamais deux fois la même arête.

Ex : A-B-C-D, M-N-L-O

Chaîne Eulérienne : Chaîne simple qui passe par toutes les arêtes d'un graphe. Pour y arriver, le graphe doit contenir exactement deux sommets de degré impair. Ex : E-A-B-E-D-B-C-D

Chaîne Hamiltonienne : Chaîne simple qui passe par tous les sommets d'un graphe une seule fois. Ex : E-A-B-C-D, K-L-M-N-O

Cycle : Un cycle est une chaîne qui revient à son point d’origine.

Ex : E-A-B-C-B-E, O-K-M-N-M-O

Cycle simple : C’est un cycle dont toutes les arêtes du cycle sont utilisées une seule fois. Ex : E-A-B-D-E

Cycle Eulérien : Cycle simple qui passe par toutes les arêtes d'un graphe. Tous les sommets du graphe doivent être de degré pair.

Ex : K-L-M-N-O-L-N-K-M-O-K

Cycle Hamiltonien : Cycle simple qui passe par tous les sommets du graphe une seule fois. Ex : A-B-C-D-E-A, K-L-M-N-O-K

Orienté

Chemin : Les sommets sont reliés par des arcs de façon continue.

Circuit : Un circuit est un chemin qui revient à son point d’origine.

...