====== Graphes ======

===== Définition =====

{{ :nsi:terminales:graphes:graphe_1.svg|}}

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$

<WRAP important>La position des sommets n'a pas d'importance. Seuls importent l'ensemble des sommets et leurs connexions. Ces deux graphes sont équivalents au précédent.

<WRAP group>
<WRAP half column>
{{ :nsi:terminales:graphes:graphe_2.svg |}}
</WRAP>

<WRAP half column>
{{ :nsi:terminales:graphes:graphe_3.svg |}}
</WRAP>
</WRAP>
</WRAP>

===== Vocabulaire =====

  * 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.

<WRAP group>
<WRAP half column>
**Exemple de graphe complet**
{{ :nsi:terminales:graphes:graphe_5.svg |}}
</WRAP>

<WRAP half column>
**Exemple de graphe non connexe**
{{ :nsi:terminales:graphes:graphe_4.svg |}}
</WRAP>
</WRAP>

===== Graphe orienté =====

{{:nsi:terminales:graphes:graphe_6.png?direct&200 |}}

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.

===== Matrice d'adjacence =====

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}$$

===== Graphe pondéré =====

{{:nsi:terminales:graphes:graphe_7.png?direct&200 |}}

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.