pichegru.net

Physique-Chimie & NSI

Cours complets et originaux de Physique-Chimie & NSI

3-01. Généralités sur les graphes

Dans ce chapitre, nous allons aborder du vocabulaire et des notions propres aux graphes – indépendamment de tout aspect algorithmique. Rien de très complexe, mais il y a beaucoup de vocabulaire à maîtriser pour les chapitres à suivre.

Un peu d’histoire

Les graphes ont été introduits pour la première fois en 1735 par le mathématicien Leonhard Euler afin de répondre au problème appelé « Problème des sept ponts de Königsberg ».

En 1736, la ville de Königsberg (actuelle Kaliningrad) est construite autour de deux îles situées sur la Pregel et reliées entre elles par un pont. Six autres ponts relient les rives de la rivière à l’une ou l’autre des deux îles comme représentés sur la figure ci-dessous.

Les 7 ponts de Königsberg
Les sept ponts de Königsberg

Les habitants se demandaient s’il existe ou non une promenade dans les rues de Königsberg permettant, à partir d’un point de départ au choix, de passer une et une seule fois par chaque pont et de revenir à son point de départ, étant entendu qu’on ne peut traverser la Pregel qu’en passant sur les ponts.

À partir de cette date, une théorie des graphes a été progressivement construite afin de répondre à des problèmes de plus en plus complexes.

Aujourd’hui, les graphes font partie des objets fondamentaux en algorithmique. En effet, leur structure relationnelle intrinsèque leur permettent de modéliser naturellement de très nombreux problèmes dans des domaines variés comme, par exemple :

  • les réseaux de communications,
  • les réseaux routiers,
  • les optimisations de chemins,
  • la gestion des ressources mémoires d’un ordinateur,
  • les réseaux sociaux,
  • le traitement automatique des langues,
  • et bien d’autres choses…

Graphes

De manière simplifiée, un graphe est un ensemble de points reliés entre eux.

Ensemble : collection non ordonnée d’éléments distincts.
Par exemple {a, b, c} et {a, c, b} sont deux ensembles identiques.

Multi-ensemble : collection non ordonnée d’éléments pouvant apparaître plusieurs fois
Par exemple {a, b, b, c, c} et {a, b, c, b, c} sont deux multi-ensembles identiques.

Graphes non orientés

Un graphe non orienté est un ensemble fini d’éléments appelés sommets associé à un multi-ensemble A de paires non ordonnées d’éléments appelées arêtes.

Une arête entre deux sommets $*u*$ et $*v*$ est notée indifférement par le couple $*(u,v)*$ ou par le couple $*(v,u)*$.
Deux sommets peuvent être reliés par plusieurs arêtes.

Quelques termes à connaître

  • ordre du graphe : le nombre de sommets.
  • taille du graphe : le nombre d’arêtes.
  • boucle : arête reliant un sommet à lui-même.
  • graphe non connexe : graphe pour lequel il existe au moins une paire de sommets entre lesquels aucun chemin n'existe. Le graphe se compose alors de plusieurs composantes connexes.
  • graphe simple : pas de boucle et au plus une arrête entre deux sommets quelconques.
  • multi-graphe : graphe ayant au moins une boucle et/ou deux sommets reliés par plus d’une arête.

Exemples de graphes non-orientés

figure 1-a
figure 1-a
figure 1-b
figure 1-b
figure 1-c
figure 1-c

Dans le graphe non orienté $*G=(S,A)*$ de la figure 1a, on a :

$*S = \{a; b; c; e; f\}*$ et $*A = \{ (a,b); (a,e); (b,c); (c,e); (e,f) \}*$

Cette notation définit entièrement le graphe.

Mais… avec cette notation on ne sait rien de l’apparence du graphe… 🤔 Par exemple, on ne sait pas que le sommet $*e*$ est tout en haut !

Exact ! Et on s’en fiche. Regardez de nouveau la définition d’un graphe non orienté donnée au début de ce paragraphe. Un graphe, c’est des sommets et des arrêtes qui les relient. Vous avez une infinité de représentations graphiques possibles pour un même graphe, et elles sont toutes valables.

figure 1-d
Autre représentation du graphe 1-a

Graphes orientés

Dans un graphe orienté, les connexions reliant les sommets ont un sens, et sont appelées arcs.

Tout ce qui a été dit avant pour les graphes non orientés est toujours valable, sauf en ce qui concerne les arêtes. À la différence des arêtes, les arcs sont orientés, c’est-à-dire qu’ils ont un point de départ et un point d’arrivée.

Un arc partant d’un sommet $*u*$ et arrivant à un sommet $*v*$ est notée par le couple $*(u,v)*$.

Si le graphe n’a pas de boucle et a au plus un arc entre deux sommets quelconques, on parle de graphe simple.

Exemples de graphes orientés

figure 2-a
figure 2-a
figure 2-b
figure 2-b
figure 2-c
figure 2-c

Structure de graphes

Décrire la structure des deux graphes ci-dessous. Préciser leur ordre et leur taille.

Représentation du graphe 1
Figure 1
Représentation du graphe 2
Figure 2

Graphes valués

Dans un graphe valué, orienté ou non orienté, chaque arête ou arc est associé à une valeur (un nombre réel).

Le mot connexion désigne indistinctement une arête ou un arc. Je m’en servirai dans la suite de mon cours pour simplifier l’écriture lorsque c’est nécessaire.

Remarque

Un graphe probabiliste est un graphe orienté valué dont les coûts sont positifs et dont la somme des coûts des arcs partant de n’importe quel sommet est égale à 1.

Exemples de graphes valués

figure 3-a
figure 3-a
figure 3-b
figure 3-b
figure 3-c
figure 3-c

Adjacence, degré et voisins

Adjacence de sommets

Un sommet $*v*$ est adjacent à un sommet $*u*$ s’il est possible de passer de $*u*$ à $*v*$ par une connexion.

🖐️ N’oubliez pas qu’un arc est orienté. Un arc permettant de passer d’un sommet A à un sommet B ne permet pas de passer de B à A.

Reconnaître des sommets adjacents

Donner les sommets adjacents des sommets suivants :

  1. sommet e du graphe représenté figure 1-a.
  2. sommet e du graphe représenté figure 2-b.
  3. sommet a du graphe représenté figure 2-b.

Degré d’un sommet

Le degré d’un sommet est le nombre de connexions qui lui sont reliées.

Dans le cas d’un graphe orienté, on peut distinguer le degré entrant et le degré sortant.

Quelques remarques

  • Un sommet est dit isolé s’il est de degré 0, c’est-à-dire s’il n’est connecté à aucun autre sommet.
  • Degré minimal et degré maximal : ce sont le plus petit et le plus grand des degrés des sommets.

Déterminer le degré d’un sommet

1. Déterminer le degré de tous les sommets du graphe représenté à la figure 2-b

2. Quels sont les degrés minimal et maximal de ce graphe ?

Voisins d’un sommet

Un sommet est voisin d’un autre si :

  • dans un graphe non orienté, ils sont reliés par une arête ;
  • dans un graphe orienté, il existe un arc allant de l’un vers l’autre (peu importe son sens).

L’ensemble des voisins d’un sommet correspond donc à l’ensemble des sommets auxquels il est directement relié.

Un sommet n’est jamais son propre voisin, alors qu’un sommet peut être adjacent à lui-même s’il y a une boucle.

Remarque

Dans un graphe orienté, si deux sommets A et B sont voisins, B est successeur de A si on peut passer de A a B. B est prédecesseur de A si on peut passer de B à A.

Un graphe est dit complet si chaque sommet a pour voisins l’ensemble des autres sommets.

Déterminer les voisins d’un sommet

Donner les sommets voisins des sommets suivants :

  1. sommet e du graphe représenté figure 1-a.
  2. sommet e du graphe représenté figure 2-b.
  3. sommet a du graphe représenté figure 2-b.

Structure de graphes

Soit les deux graphes représentés ci-dessous.

Représentation du graphe 1
Figure 1
Représentation du graphe 2
Figure 2

1. Graphe de la figure 1

  1. Quels sont les sommets adjacents au sommet 2 et au sommet 3 ?
  2. Quels sont les voisins du sommet 5 ? On précisera ses prédécesseurs et ses successeurs.
  3. Quels sont les degrés entrant et sortant du sommet 4 ? Quel est son degré ?
  4. Le graphe a-t-il un sommet isolé ?

2. Graphe de la figure 2

  1. Quels sont les sommets adjacents au sommet 3 et au sommet 4 ?
  2. Quels sont les voisins du sommet 4 ?
  3. Quel est le degré du sommet 1 ?
  4. Quel est le degré minimal du graphe ? le degré maximal ?

Chemins et connexité

Chemins entre deux sommets

Un chemin entre deux sommets A et B d’un graphe est une suite finie de connexions permettant de passer de A à B.

Quelques termes à connaître

  • chemin simple : chemin constitué de connexions toutes distinctes (on ne repasse pas plusieurs fois par la même connexion).
  • chemin fermé : chemin dont le sommet de départ et le sommet d’arrivé sont identiques.
  • cycle : chemin simple fermé.
  • longueur d’un chemin : nombre de connexions qui le composent
  • distance d’un sommet $*u*$ à un sommet $*v*$ : plus petite des longueurs des chemins partant de $*u*$ et arrivant à $*v*$.
  • diamètre du graphe la plus grande distance entre deux sommets quelconques.

Trouver des chemins entre deux sommets

1. Pour les graphes ci-dessous, indiquer s’il existe toujours un chemin entre deux sommets quelconques et donner le son diamètre.

  1. figure 2b
  2. figure 2c

2. Donner un cycle de longueur 3 dans le graphe de la figure 3b.

3. Le graphe de la figure 3c est-il acyclique ? Quel est son diamètre ?

Chemins, distance et diamètre

Soit les deux graphes représentés ci-dessous.

Représentation du graphe 1
Figure 1
Représentation du graphe 2
Figure 2

1. Graphe de la figure 1

  1. Existe-t-il toujours un chemin entre deux sommets donnés ? Si non, quels sous-graphes vérifient cette propriété ?
  2. Donner un chemin de longueur 4 partant du sommet 1 et arrivant au sommet 5.
  3. Donner un cycle de longueur 5 partant du sommet 2.
  4. Dans le sous-graphe formé par les sommets 1, 2, 4 et 5, existe-t-il un chemin contenant une et une seule fois tous les sommets ?
  5. Quelle est la distance entre les sommets 1 et 5 ? entre les sommets 1 et 3 ?
  6. En déduire le diamètre du graphe.

2. Graphe de la figure 2

  1. Existe-t-il toujours un chemin entre deux sommets ? Si non, quels sous-graphes vérifient cette propriété ?
  2. Existe-t-il un chemin de longueur 3 entre les sommets 1 et 3 ?
  3. Le graphe est-il acyclique ?
  4. Existe-t-il un chemin contenant une et une seule fois toutes les arêtes ?
  5. Quelle est la distance entre les sommets 1 et 5 ? entre les sommets 3 et 5 ?
  6. Quel est le diamètre du graphe ?

Connexité

Un graphe non orienté est dit connexe s’il existe un chemin entre deux sommets quelconques.

Quelques définitions

  • chemin eulérien : chemin qui passe une seule fois par toutes les arêtes
  • graphe semi-eulérien : graphe admettant un chemin eulérien
  • cycle eulérien : chemin eulérien qui revient au sommet de départ.
  • graphe eulérien : graphe admettant un cycle eulérien
  • chemin hamiltonien : chemin qui passe une seule fois par tous les sommets
  • graphe semi-hamiltonien : graphe admettant un chemin hamiltonien
  • cycle hamiltonien : chemin hamiltonien qui revient au sommet de départ
  • graphe hamiltonien : graphe admettant un cycle hamiltonien

Eulérien : on parle des connexions

Hamiltonien : on parle des sommets

Graphe admettant un chemin eulérien
Exemple d'un graphe
admettant un chemin eulérien.
Tracer d’un chemin eulérien
Dessin à la main
sans lever le crayon

Un graphe orienté est dit fortement connexe si, pour toute paire ordonnée de sommets, il existe un chemin entre ces deux sommets.

Vérifier qu’un graphe est semi-eulérien

Montrer que le graphe de la figure 1a est semi-eulérien. Préciser un chemin eulérien et l’arête à ajouter pour que le graphe devienne eulérien.

Modélisation de la structure d’un site web

Le graphe ci-dessous modélise un site web constitué de six pages. Les flèches indiquent les liens entre les pages.

Représentation du graphe des liens d’un site web

1. Peut-on accéder à n’importe quelle page du site à partir de n’importe quelle autre page ? Que cela signifie-t-il pour le graphe ?
2. On est sur la page 1. Peut-on accéder à la page 6 en trois clics ? Que cela signifie-t-il pour le graphe ?
3. Montrer qu’il existe une page à partir de laquelle on peut visiter une et une seule fois tous les liens du site. Sur quelle page se retrouve-t-on à la fin ? Que cela signifie-t-il pour le graphe ?
4. Quel lien unique faut-il ajouter au site pour que, à partir d’une page quelconque, on puisse visiter une et une seule fois tous les liens et revenir à la page de départ ? Que cela signifie-t-il pour le graphe ?