Théorie des graphes

Objectifs

• Définir les termes de base de la théorie des graphes
  • Graphe
  • Sommet
  • Arête
  • Arc
  • Boucle
  • Voisinage
  • Degré
  • Poids
  • Chaîne/Chemin
  • Cycle/Circuit
• Différencier graphe orienté et non orienté
• Reconnaître les différents topologies de graphes
• Modéliser un problème sous forme de graphe

Cours

Théorie des graphes

Graphes

Théorie des graphes

F pour passer en plein écran ou O pour afficher la vue d'ensemble.
Versions sans animation, plein écran, imprimable.

Exercices

Exercice 1

Donner les caractéristiques du graphe ci-dessus :

1. Graphe orienté ou non orienté ?
2. Graphe pondéré ou non pondéré ?
3. Nombre de sommets ?
4. Nombre d'arêtes ?
5. A une boucle ?
6. A un cycle ?
7. Quel est le degré du sommet b ?
8. Quel est le voisinage du sommet c ?
9. Quelle est la longueur de la chaîne a → c → d ?
10. Quel est le poids de la chaîne a → c → d ?
11. Quel est le chemin le plus court (chaîne de poids minimal) entre a et d ?

Solution

1. Graphe non orienté
2. Graphe pondéré
3. 4 sommets
4. 5 arêtes
5. Pas de boucle
6. Cycle, par exemple a → b → c → a
7. 3
8. a, b et d
9. 2
10. 7
11. a → b → d

Exercice 2

Pour se rendre à Zürich depuis Lausanne, les trains suivants sont disponibles :

• Direct :
  • Lausanne → Zürich
• Correspondance avec un changement :
  • Lausanne → Berne → Zürich
  • Lausanne → Bâle → Zürich
• Correspondance avec deux changements :
  • Lausanne → Berne → Olten → Zürich
  • Lausanne → Bâle → Olten → Zürich

Modéliser ces différents vols sous forme de graphe orienté.

Solution

Exercice 3

Pour chaque graphe, indiquer quelles sont leurs topologies parmi :

• Homogène
• Hiérarchique
• Cyclique
• Centralisé
• Quelconque

Solution

• Homogène
• Cyclique

Solution

• Hiérarchique

Solution

• Hiérarchique
• Centralisé

Exercice 4

Voici le plan du musée archéologique d'Olympie :

Modéliser ce plan sous forme de graphe.
Que représente chaque sommet et chaque arête ?

Solution

Exercice 5

Modéliser les interactions entre les personnes suivantes sous forme de graphe :

• Anna est amie avec Bob, Céline et Emile
• Céline est amie avec Bob et François
• Guillaume est ami avec Hector, François et Anna

Serait-ce plutôt un graphe orienté ou non orienté ? Pourquoi ?

Que représente chaque sommet et chaque arête ?

Que pourrait signifier une pondération du graphe ?

Solution

Non orienté, car l'amitié est réciproque.

Chaque sommet représente une personne et chaque arête représente une amitié.

Le poids d'une arête pourrait représenter la proximité entre deux personnes (nombre d'intérêts en commun par exemple).

Références

• https://fr.vikidia.org/wiki/Graphe_(th%C3%A9orie_des_graphes)
• https://fr.wikipedia.org/wiki/Th%C3%A9orie_des_graphes
• https://fr.wikipedia.org/wiki/Graphe_(math%C3%A9matiques_discr%C3%A8tes)
• https://fr.wikipedia.org/wiki/Probl%C3%A8me_des_sept_ponts_de_K%C3%B6nigsberg