Théorie des graphes

Sommaire

1. Généralités

1.1 Concepts orientés

1.2 Concepts non orientés

1.3 Hypergraphes

1.4 Suites d’arêtes. Connexité

2. Modes de représentation

2.1 Listes de succession

2.2 Matrice d’adjacence

2.3 Matrice d’incidence

3. Nombres et ensembles caractéristiques des graphes

3.1 Degrés attachés à un graphe

3.2 Rang et nombre cyclomatique

3.3 Nombre de stabilité interne (externe)

3.4 Noyau

3.5 Points et ensembles d’articulation. Nombre de connexité

3.6 Centres d’un graphe

3.7 Nombre chromatique

3.8 Indice chromatique

3.9 Problème de l’isomorphisme et problèmes NP-difficiles

4. Chemins et circuits

4.1 Réseaux

4.2 Chemins et circuits eulériens

4.3 Chemins et circuits hamiltoniens

4.4 Recherche du plus court chemin

4.5 Problème du voyageur de commerce (PVC)

4.6 Algorithmes distribués

5. Arbres et arborescences

5.1 Définition des arbres

5.2 Arbres couvrants sur un graphe

5.3 Notion d’arborescence

6. Réseaux de transport

6.1 Flots dans un réseau de transport

6.2 Méthode de recherche du flot maximal: algorithme de Ford et Fulkerson

6.3 Problème des flots de coût minimal

7. Graphes bipartis et couplages

7.1 Position du problème et vocabulaire

7.2 Problèmes d’affectation

8. Graphes planaires

8.1 Généralités

8.2 Test de planarité d’un graphe

8.3 Coloriage des graphes planaires

9. Implantations d’un graphe dans un autre

Pour en savoir plus

Chacun a vu une fois au moins un plan de métro, une carte de lignes ferroviaires ou aériennes, un plan électrique ou un circuit électronique ; ainsi, tout le monde sait plus ou moins intuitivement ce qu’est un graphe. Toutefois, entre la vague notion d’un schéma incluant des « points » et des « trajets » unissant ces points et...