Introduction à la théorie des graphes/Définitions

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

Il est nécessaire, pour étudier la théorie des graphes, de se munir d'un crayon et d'un brouillon. En effet, pour comprendre la majorité des concepts, il sera plus qu'utile de faire un dessin.

Graphe

Un graphe est un objet mathématique particulier, nous devons donc commencer par le définir avant d’en étudier la théorie :

Définition

Un graphe G est un couple (V(G),E(G)) tel que V(G) est un ensemble non vide de sommets et E(G) un ensemble d'arêtes. Une arête de G étant une paire de sommets de G.

Pour simplifier, nous noterons V et E les ensembles V(G) et E(G).

Pour mieux comprendre cette définition, voici un exemple :

Début de l'exemple

Exemple

Soit le graphe G=(V,E) défini par V={1,2,3,4} et E={e1,e2,e3,e4} avec e1={1,2}, e2={1,3}, e3={1,4} et e4={3,4}.

Le graphe G peut être représenté par la figure ci-contre.

Notons que, d’après la définition, un graphe n'a pas une unique représentation graphique. La position des sommets et la forme des arêtes (une arête peut être courbe) n'ayant pas d'importance. Le choix de cette représentation s'appuie donc plus sur des critères esthétiques et de lisibilité.

Fin de l'exemple

Arêtes adjacentes, sommets voisins, arête incidente à un sommet

Voilà trois termes à ne pas confondre, voici leur définition :

Définition

Deux arêtes d'un graphe sont adjacentes si elles ont au moins un sommet en commun.

Définition

Dans un graphe, une arête $e$ est incidente à un sommet $v$ si $v\in e$.

Définition

Deux sommets d'un graphe sont voisins ou adjacents s'ils ont au moins une arête incidente en commun.

Début de l'exemple

Exemple

Ainsi, dans le graphe présenté dans l'exemple précédent, les arêtes e1 et e2 sont adjacentes car elles ont le sommet 1 en commun. De même, nous pouvons dire qu'e1 est incidente au sommet 1, et que 1 et 2 sont voisins car ils sont reliés par l'arête e1.

Fin de l'exemple

Graphe simple

Définition

Lorsque plusieurs arêtes relient deux sommets, on les appelle des arêtes multiples.

Définition

Une boucle est une arête dont les deux extrémités sont identiques.

Définition

Un graphe est simple s'il ne contient ni boucle ni arêtes multiples.

Début de l'exemple

Exemple

Le graphe que nous avons étudié dans les exemples précédents était donc un graphe simple, mais ce n'est plus le cas du graphe représenté ci-contre.

En effet, en rouge nous pouvons observer des arêtes multiples, et en bleu une boucle.

Un graphe qui n’est pas simple est aussi appelé multigraphe.

Fin de l'exemple

Degré d'un sommet

Définition

Dans un graphe, le degré d'un sommet v, noté d(v), correspond au nombre d'arêtes incidentes à v.

Par convention, une boucle, touchant deux fois le sommet, sera comptée comme deux arêtes incidentes.

Cette définition nous permet maintenant d'introduire notre premier théorème :

Début d’un théorème

Théorème

Dans un graphe simple, $\sum _{v\in V}d(v)=2|E|$

Fin du théorème

Début d'une démonstration

Démonstration

Dans un graphe simple, chaque arête relie deux sommets. Donc, quand on fait la somme des degrés, chaque arête est comptée deux fois : une fois dans le degré de sa première extrémité et une fois dans le degré de la seconde.

Fin de la démonstration

Il existe d'autres démonstrations pour ce théorème qui sont sans doute plus formelles. Cependant, nous n'avons pas encore les outils pour les étudier.

Début d’un théorème

Théorème

Dans un graphe simple, le nombre de sommets de degré impair est pair.

Fin du théorème

Début d'une démonstration

Démonstration

D'après le théorème précédent, nous avons :

$\sum _{v\in V}d(v)=2|E|$

Notons $W=\{v\in V|d(v){\mbox{ impair}}\}$

$\sum _{v\in W}d(v)+\sum _{v\in V\backslash W}d(v)=2|E|$

Donc $\sum _{v\in V\backslash W}d(v)$ est pair.

On en déduit que le nombre de sommets de degré impair ($\sum _{v\in W}d(v)$) est pair.

Fin de la démonstration

Quelques graphes particuliers

Graphe régulier

Définition

Un graphe est dit k-régulier si tous ses sommets sont de degré k.

• 
  graphe 0-régulier
• 
  graphe 1-régulier
• 
  graphe 2-régulier
• 
  graphe de Petersen 3-régulier

Graphe complet

Définition

Un graphe complet à n sommets, noté $K_{n}$, est le graphe simple dont tous les sommets sont reliés deux à deux.

• 
  $K_{1}$
• 
  $K_{2}$
• 
  $K_{3}$
• 
  $K_{4}$

Propriété

* Un graphe complet à n sommets :

• • est (n-1)-régulier.
  • possède ${\frac {n(n-1)}{2}}$ arêtes.