Graphes

Un graphe est composé de sommets – vertex – liés par des arêtes – edges.

On pourra noter $G(\mathcal{S}, \mathcal{A})$ pour désigner le graphe G qui possède un ensemble S de sommets et un ensemble A d'arêtes – en anglais, G(V, E), pour vertex et edge.

Dans cet exemple,

• $\mathcal{S} = \lbrace A, B, C, D, E\rbrace$,
• $\mathcal{A} = \lbrace (A,D), (A,B), (A,C), (B,E), (B,C), (D,E) \rbrace$

• Le degré d'un sommet est le nombre d'arête ayant ce sommet pour extrémité.
  Le degré de A est 3.
• L' ordre d'un graphe est le nombre de sommets.
  Le graphe est d'ordre 5.
• Deux sommets sont adjacents s'ils liés par une arête.
  A et B sont adjacents mais pas A et E.
• Un chemin ou chaîne, est une suite de sommets adjacents décrivant un chemin dans le graphe.
  E-B-C-A-B est un chemin mais pas E-B-D-E car il n'y a pas d'arête B-D.
• Une chaîne fermée est un chemin dont le premier point est égal au dernier. Une chaîne fermée

où aucun sommet n'est répété (sauf le point de départ) est un cycle.
E-B-A-D est une chaîne fermée et un cycle.
E-B-A-C-B-A-D-E est toujours une chaîne fermée mais pas un cycle (peut dépendre des définitions)

• Un graphe complet est ou chaque sommet est adjacent avec tous les autres.
• Un graphe connexe est un graphe dans lequel on peut trouver un chemin reliant toute paire de sommets.

Si les arêtes sont dotées d'une orientation, on dit que le graphe est orienté .

• Ci-contre, le passage C → A est possible mais pas A → C.
• Le parcours en double sens B → E et E → B nécessite deux arêtes.
• A → B → C → A est un cycle mais pas A → D ← E → B ← A.
• On peut envisager le cas d'un sommet pointant sur lui-même.
• On peut arriver à D mais pas en partir.

La matrice est une grille représentant l'existence de connexion d'un sommet à l'autre. Nous avons n sommets. La matrice sera une grille de n × n.

• Le chiffre à la ligne i et la colonne j est 1 si l'arête sommet i → sommet j existe.
• Ainsi le 1 représente la l'arête E → B.

$$\begin{pmatrix}1 & 1 & 0 & 1 & 0\\ 0 & 0 & 1 & 0 & 1\\ 1 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0\\ 0 & \textbf{1} & 0 & 1 & 0\end{pmatrix}$$

Les arêtes sont pondérées par un nombre, un poids.

Cet exemple est orienté mais on pourrait pondérer un graphe non-orienté.

Par exemple, si les sommets représentent des lieux dans une ville, les arêtes des rues, les pondération pourraient représenter un temps de trajet. Il y a des sens unique et le parcours en sens contraire peut-être plus long s'il faut faire un détour.

Un problème classique est justement de chercher le chemin le plus court d'un point à un autre.