Comme on l'a déjà vu, les graphes sont formés par des points, connus comme sommets, lesquels sont unis par des arêtes Ce sont les termes généraux mais il y a beaucoup de types différents de sommets et d'arêtes qu’on va étudier dans cette partie, pour comprendre comment sont formés les graphes.

 

Arêtes : elles forment les chemins d’un graphe. Ce sont les liens qu'unissent les sommets qui puissent être des objets, des personnes ou des lieux, entre autres. La nomenclature pour écrire les arêtes est simple, elles sont nommées par les points de ses fins, c’est-à-dire les sommets unis par une arête donnent le nom à son lien. 

 

• Arêtes adjacentes : ce sont des arêtes qui coïncident dans le même sommet. Dans ce cas, les arêtes AB et AC coïncident dans le sommet A, donc elles sont adjacentes. 

​

​

​

 

• Arêtes parallèles : ont le principe et la fin aux mêmes sommets. Dans ce cas l’arête AB et l’arête BA, auxquels on peut donner le nom indifféremment parce que les sommets qui unissent sont les mêmes, sont parallèles car elles ont le principe au sommet A et la fin au sommet B, ou vice-versa, si bien qu’elles n’ont pas une direction concrète. 

 

​

​

• Arêtes cycliques ou nœuds : les arêtes cycliques commencent et finissent son parcours au même sommet. L'arête alors, dans ce cas, aura le nom AA, bien qu’elle commence et finisse dans le même sommet. Les nœuds content comme deux quand on calcule le degré, donc le degré de A c’est : gr (A) =2. 

    

 

​

​

​

• Croisement : deux arêtes qui se croissent, et coïncident en un point. Dans ce cas on voit que les arêtes AD et BC froment un croisement.  

 

​

​

​

 

Sommet : les sommets sont les points pour lesquels est formé un graphe. Ils peuvent représenter des objets, des lieux, des personnes... Graphiquement ils sont souvent représentés par des figures géométriques, la plupart de fois par des points, si bien qu'on peut aussi les trouver en forme de triangle, carré ou aucune figure géométrique. 

 

​

​

​

​

​

 

 

​

​

​

​

​

​

​

​

• Sommet adjacent : deux sommets sont adjacents s’ils sont unis par une arête. Dans ce cas, par exemple les sommets A et C sont adjacents parce qu’ils sont unis par l'arête AC. Par contre, les sommets A et D ne sont pas adjacents parce qu’ils ne sont unis par aucune arête.

​

​

​

 

​

• Sommet isolé : c’est un sommet qui n’est pas uni aucun autre par des arêtes et donc il a degré 0. Ici on peut voir que le sommet D est un sommet isolé parce que ce respect la norme de que gr (D)= 0

 

​

​

​

​

• Sommet terminal : c’est un sommet qui a degré 1 bien qu’il est seulement l'extrême d’une arête. Dans ce cas, le sommet D est un sommet terminal puisque gr (D) =1.

​

​

​

​

​

Chemin: Dernièrement les chemins sont les successions de sommets et arêtes qu’on peut suivre pour arriver d’un sommet à un autre. Il peut avoir plusieurs chemins différents. Dans ce cas, le chemin pour arriver d’A à E c’est: [AB],[BC],[CD],[DE]. Il y a aussi différents types de chemins, qu’on va voir à continuation. 

 

D’abord il faut mentionner deux termes: 

 

• Longueur d’un graphe: c’est le nombre d'arêtes d’un chemin. Donc dans l’exemple antérieur, la longueur du chemin entre A et E était 4. 

• Extrêmes du chemin: ce sont les sommets desquels on commence et on finit le chemin. On peut les appeler Vo aux sommet duquel on part et Vn au sommet oú on arrive. Dans ce cas Vo=A et Vn=E. 

 

Ensuite on va commenter les différents types de chemins qu’il y a et ses caractéristiques:

 

• Chemin fermé: ses extrêmes et donc le sommet initial et final sont le même, Vo=Vn. On peut passer plusieurs fois par les mêmes arêtes ou sommets. 

• Chemin simple: tous les sommets et arêtes sont différents, c’est-à-dire, on ne passe pas deux fois pour le même point. 

• Cycle: c’est un chemin fermé auquel les seuls sommets répétés sont le premier et le dernier. 

• Circuit: c’est un chemin fermé qui ne répète pas d'arêtes.

 

 

​