Algorithmique de graphes

Jin-Kao Hao

Département d’Informatique
Université d'Angers

email : [Link]@[Link]
web : [Link]/pub/hao
 Plan

1. Introduction
2. Notions de base
3. Exemples de problèmes de graphes
4. Parcours de graphes
5. Le plus court chemin
6. Arbre couvrant minimum
7. Flow maximum dans un réseau
 Références

Introduction to Algorithms
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
PHI Learning Pvt. Ltd. (Originally MIT Press); Third edition (February 2, 2010)

Combinatorial Optimization: Algorithms and Complexity.

Christos H. Papadimitriou , Kenneth Steiglitz.
Dover Publications; Unabridged edition (January 29, 1998)

Concepts fondamentaux de l'informatique

Alfred Aho, Jeffrey D. Ullman
Dunod (1993)

Tout livre « Graph theory » « graph algorithms »

 Introduction

Le graphe est un concept mathématique qui permet de mettre en relation entre deux éléments d’un
ensemble fini.

Le graphe est un outil très puissant et pratique permettant la modélisation de nombreuses applications
pratiques

Exemples
- Organigramme (université, entreprise)
- Carte routière
- Carte des départements français
- Réseaux sociaux
- Emploi du temps
- Ordonnancement des tâches sur machines
- Science en général
 Généralités – Graphe orienté (digraph)
Déf: Soit 𝑉𝑉 un ensemble fini, 𝐸𝐸 une relation binaire sur 𝑉𝑉, i.e., 𝐸𝐸 ⊆ 𝑉𝑉 × 𝑉𝑉; alors le couple 𝐺𝐺 = (𝑉𝑉, 𝐸𝐸) est un graphe orienté.
𝑉𝑉 : l’ensemble des sommets (ou nœuds) de 𝐺𝐺; 𝐸𝐸 : l’ensemble des arcs de 𝐺𝐺; 𝑉𝑉 : l′ ordre de 𝐺𝐺.

Commentaires:
1) Chaque élément 𝑥𝑥, 𝑦𝑦 ∈ 𝐸𝐸 est un couple ordonné , donc 𝑥𝑥, 𝑦𝑦 ≠ (𝑦𝑦, 𝑥𝑥)
2) 𝑥𝑥, 𝑦𝑦 ∈ 𝐸𝐸 ⇔ 𝑥𝑥, 𝑦𝑦 est un arc ⇔ 𝑥𝑥𝑥𝑥𝑥𝑥 ⇔ 𝑥𝑥 𝑦𝑦 (graphiquement)
𝑥𝑥 : prédécesseur de 𝑦𝑦 et origine de l’arc; 𝑦𝑦 : successeur de 𝑥𝑥 et extrémité de l’arc 𝑦𝑦
…
3) Ensemble des successeurs ∶ 𝑅𝑅 𝑥𝑥 = 𝑦𝑦 𝑥𝑥, 𝑦𝑦 ∈ 𝐸𝐸} 𝑥𝑥 𝑦𝑦
𝑥𝑥
4) Ensemble des prédécesseurs : 𝑅𝑅 − 1 𝑦𝑦 = 𝑥𝑥 𝑥𝑥, 𝑦𝑦 ∈ 𝐸𝐸} … 𝑦𝑦
5) Si 𝑥𝑥, 𝑦𝑦 ∈ 𝐸𝐸, alors 𝑥𝑥 et 𝑦𝑦 sont dits adjacents ou voisins 𝑥𝑥

𝑒𝑒. 𝑔𝑔. 𝐺𝐺 = 𝑉𝑉, 𝐸𝐸 où 𝑉𝑉 = 1,2, … , 6 et 𝐸𝐸 = { 1,2 , 2,4 , 2,5 , 4,1 4,4 , 4,5 , 5,4 , (6,3)}

Déf: 𝐺𝐺 = (𝑉𝑉, 𝐸𝐸) et 𝑥𝑥 ∈ 𝑉𝑉

Le demi-degré intérieur de 𝑥𝑥 : 𝑑𝑑𝑖𝑖 𝑥𝑥 = 𝑅𝑅 − 1 𝑥𝑥 (nombre d′ arcs rentrant)
Le demi-degré extérieur de 𝑥𝑥 : 𝑑𝑑𝑒𝑒 𝑥𝑥 = 𝑅𝑅 𝑥𝑥 (nombre d′ arcs sortant)
Le degré de 𝑥𝑥 : 𝑑𝑑 𝑥𝑥 = 𝑑𝑑𝑖𝑖 𝑥𝑥 + 𝑑𝑑𝑒𝑒 𝑥𝑥
𝑒𝑒. 𝑔𝑔. 𝑑𝑑 5 = 𝑑𝑑𝑖𝑖 5 + 𝑑𝑑𝑒𝑒 5 = 2 + 1 = 3
 Sous graphe et graphe partiel
Déf: Soit 𝐺𝐺 = (𝑉𝑉, 𝐸𝐸) et 𝐴𝐴 ⊂ 𝑉𝑉. Le sous−graphe engendré par 𝐴𝐴 est le graphe 𝐺𝐺𝐴𝐴 = 𝐴𝐴, 𝐸𝐸𝐴𝐴 𝑜𝑜𝑜 𝐸𝐸𝐴𝐴 = 𝐸𝐸 ∩ 𝐴𝐴 × 𝐴𝐴.

𝑒𝑒. 𝑔𝑔.
𝐴𝐴 = 1,2,4,5
𝐸𝐸𝐴𝐴 = { 1,2 , 2,4 , 2,5 , 4,1 4,4 , 4,5 , 5,4 }

Déf: Soit 𝐺𝐺 = (𝑉𝑉, 𝐸𝐸) et 𝐿𝐿 ⊂ 𝐸𝐸. Le graphe partiel engendré par 𝐿𝐿 est le graphe 𝐺𝐺𝐿𝐿 = 𝑉𝑉, 𝐿𝐿

𝑒𝑒. 𝑔𝑔.
𝐿𝐿 = { 1,2 , 2,4 , 2,5 , 4,1 4,4 , 4,5 , 5,4 }
 Chemin et cycle
Déf (chemin): Un chemin de longueur 𝑘𝑘 ≥ 0 est une suite d′ arcs α1, α2, … , α𝑘𝑘 tq pour tout 𝑖𝑖 entre 1 et 𝑘𝑘 − 1,
l′ extrémité de α𝑖𝑖 est l′ origine de α𝑖𝑖 + 1.
Remarques:
1) Pour tout chemin 𝑘𝑘 > 0, le chemin peut être codé par une suite de sommets 𝑥𝑥0, 𝑥𝑥1, … , 𝑥𝑥𝑘𝑘 tq α𝑖𝑖 = (𝑥𝑥𝑖𝑖 − 1, 𝑥𝑥𝑖𝑖)
2) Si pour tout 𝑖𝑖 ≠ 𝑗𝑗, 𝑥𝑥𝑖𝑖 ≠ 𝑥𝑥𝑗𝑗 , alors le chemin est dit simple ou élémentaire.

Déf (cycle/circuit): Un chemin non-vide codé par 𝑥𝑥0, 𝑥𝑥1, … , 𝑥𝑥𝑘𝑘 est un cycle ou circuit si 𝑥𝑥0 = 𝑥𝑥𝑘𝑘 .
Si en plus, pour tout 𝑖𝑖, 𝑗𝑗 ≠ 0, 𝑘𝑘 , 𝑥𝑥𝑖𝑖 ≠ 𝑥𝑥𝑗𝑗 , alors le cycle est dit élémentaire.

Déf (cycle hamiltonien): Un cycle élémentaire d’un graphe G est dit hamiltonien s’il contient tous les sommets de G.

Remarque:
• Voyageur de commence – le circuit hamiltonien le plus court d’un graphe valué. (Combiens de circuits possibles ?)

Déf (cycle eulérien): Un cycle d’un graphe G est dit eulérien s’il contient tous les arcs de G une seule fois.

e.g. Graphe papillon : cycle eulérien, mais pas de cycle hamiltonien

 Fermeture
Déf: Soit 𝐺𝐺 = 𝑉𝑉, 𝐸𝐸 , la fermeture transitive de 𝐺𝐺 est le graphe 𝐺𝐺 + = 𝑉𝑉, 𝐸𝐸 + tq pour tout 𝑥𝑥, 𝑦𝑦 ∈ 𝑉𝑉,
𝑥𝑥𝐸𝐸 + 𝑦𝑦 ⇔ il exists un chemin non vide de 𝑥𝑥 à 𝑦𝑦.

Déf: Soit 𝐺𝐺 = 𝑉𝑉, 𝐸𝐸 , la fermeture reflexive transitive de 𝐺𝐺 est le graphe 𝐺𝐺 ∗ = 𝑉𝑉, 𝐸𝐸 ∗ tq pour tout 𝑥𝑥, 𝑦𝑦 ∈ 𝑉𝑉,
𝑥𝑥𝐸𝐸 ∗ 𝑦𝑦 ⇔ 𝑥𝑥 = 𝑦𝑦 ou il exists un chemin non vide de 𝑥𝑥 à 𝑦𝑦.
 Graphe valué et graphe non-orienté

Déf (graphe valué/pondéré) : Soit 𝐺𝐺 = 𝑉𝑉, 𝐸𝐸 , A et B deux ensembles;

- une fonction de valuation 𝑓𝑓𝑣𝑣 ∶ 𝑉𝑉 → 𝐴𝐴
- une fonction de valuation 𝑓𝑓𝑒𝑒 ∶ 𝐸𝐸 → 𝐵𝐵
alors 𝐺𝐺 = 𝑉𝑉, 𝐸𝐸, 𝐴𝐴, 𝐵𝐵, 𝑓𝑓𝑣𝑣 , 𝑓𝑓𝑒𝑒 est un graphe valué pondéré .

Rm:
1) On peut pondérer uniquement les arcs ou les sommets;
2) Applications types : réseaux routiers, réseaux de distribution…

Déf (graphe non-orienté): 𝐺𝐺 = 𝑉𝑉, 𝐸𝐸 est un graphe non-orienté si les couples de 𝐸𝐸 ne sont pas ordonnés.
i. e. , 𝐸𝐸 = 𝑥𝑥, 𝑦𝑦 𝑥𝑥 ∈ 𝑉𝑉, 𝑦𝑦 ∈ 𝑉𝑉} où chaque 𝑥𝑥, 𝑦𝑦 est une arête de G.

Remarques:
1. 𝑥𝑥, 𝑦𝑦 ∈ 𝐸𝐸 ⇔ 𝑦𝑦, 𝑥𝑥 ∈ 𝐸𝐸 est un arête ⇔ 𝑥𝑥 𝑦𝑦 (graphiquement);
2. si 𝑥𝑥, 𝑦𝑦 ∈ 𝐸𝐸, 𝑥𝑥 et 𝑦𝑦 sont dits adjacents ou voisins;
3. Le degré 𝑑𝑑 𝑥𝑥 d’un sommet 𝑥𝑥 est le nombre de ses voisins.

𝑒𝑒𝑒𝑒: 𝐺𝐺 = 𝑉𝑉, 𝐸𝐸 𝑜𝑜𝑜

𝑉𝑉 = 1,2,3,4,5 , 𝐸𝐸 = 1,2 , 1,3 , 1,4 , 2,3 , 2,5
𝑑𝑑 1 = 𝑑𝑑 2 = 3; 𝑑𝑑 3 = 2; 𝑑𝑑 4 = 𝑑𝑑 5 = 1
 Equivalence et connexité

Déf : Soit 𝐺𝐺 = 𝑉𝑉, 𝐸𝐸 , deux sommets 𝑥𝑥, 𝑦𝑦 ∈ 𝑉𝑉; 𝑥𝑥 𝑒𝑒𝑒𝑒 𝑦𝑦 sont équivalents 𝑠𝑠𝑠𝑠 𝑥𝑥 = 𝑦𝑦 ou s′il existe un chemin entre 𝑥𝑥 et 𝑦𝑦.

Déf : Une composante fortement connexe d’un graphe est un sous-graphe engendré par une classe de sommets
équivalents.

Rm: Dans une composante fortement connexe, il existe un chemin entre chaque pair de sommets.

ex: {1,2,4,5} est classe d’équivalence.

Le sous-graphe engendré par {1,2,4,5} est une composante fortement connexe.
 Graphe planaire
Déf : Soit 𝐺𝐺 = 𝑉𝑉, 𝐸𝐸 , un graph non-orienté; 𝐺𝐺 est dit planaire si G peut être dessiné sur un plan (2D) sans croisement
d’arêtes.

ex: carte des départements français

K1-K4 : planaire
K5 et K3,3 non planaire

Théorème (Kuratowski): Un graphe est planaire si et seulement s'il ne contient pas de sous-graphe qui est
une « copie » (un graphe isomorphe) de K5 ou K3,3.
 Graphe bipartie

Déf : Soit 𝐺𝐺 = 𝑈𝑈 ∪ 𝑉𝑉, 𝐸𝐸 où 𝑈𝑈 ∩ 𝑉𝑉 = ∅, 𝐺𝐺 est dit 𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏, si pour tout 𝑢𝑢, 𝑣𝑣 ∈ 𝑈𝑈, 𝑜𝑜𝑜𝑜 𝑢𝑢, 𝑣𝑣 ∈ 𝑉𝑉 ,
𝑢𝑢 et 𝑣𝑣 ne sont pas adjacents 𝑖𝑖. 𝑒𝑒. , 𝑢𝑢, 𝑣𝑣 ∉ 𝐸𝐸 .
Si de plus pour tout 𝑢𝑢 ∈ 𝑈𝑈 𝑒𝑒𝑒𝑒 𝑣𝑣 ∈ 𝑉𝑉, 𝑢𝑢, 𝑣𝑣 ∈ 𝐸𝐸, alors 𝐺𝐺 est un 𝑔𝑔𝑔𝑔𝑔𝑔𝑔𝑔𝑔𝑔𝑔 𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏 𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐𝑐.
ex: conception de système nanoélectronique: Chaque commutateur se situe à une
intersection de deux nanofils. Cependant, en présence de défauts, certains nanofils
ou interrupteurs peuvent être inutilisables. Ainsi, une tâche clé dans cette
application est de trouver le plus grand sous-ensemble de 𝑛𝑛 × 𝑛𝑛 nanofils sans
défaut de la barre transversale, de sorte que les commutateurs entre deux nanofils
orthogonaux quelconques soient fonctionnels.

Autres ex.: acteurs-films, personnes-groupes de discussions (réseau social),

Graphe bi-partie complet personnes-compétences, personnes-tâches…
 Biclique
Déf : Soit 𝐺𝐺 = 𝑈𝑈 ∪ 𝑉𝑉, 𝐸𝐸 , soit 𝑋𝑋 ⊂ 𝑈𝑈, 𝑌𝑌 ⊂ 𝑉𝑉, et 𝐺𝐺 𝑋𝑋, 𝑌𝑌 = 𝑋𝑋 ∪ Y, 𝐸𝐸𝑋𝑋 ∪ 𝑌𝑌 le sous−graphe engendré par 𝑋𝑋 ∪ 𝑌𝑌,
alors 𝐺𝐺 𝑋𝑋, 𝑌𝑌 est une 𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏 de 𝐺𝐺 si 𝐺𝐺 𝑋𝑋, 𝑌𝑌 est un graphe bi−partie complet,
𝑖𝑖. 𝑒𝑒. 𝐸𝐸𝑋𝑋∪𝑌𝑌 = 𝑋𝑋 × 𝑌𝑌. Si de plus, |X | = |Y |, alors 𝐺𝐺 𝑋𝑋, 𝑌𝑌 est une 𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏 é𝑞𝑞𝑞𝑞𝑞𝑞𝑞𝑞𝑞𝑞𝑞𝑞𝑞𝑞𝑞𝑞𝑞.

Biclique donnée par X et Y K5,3 (bi-clique) Biclique équilibrée

Rm: Le problème de déterminer la biclique maximale équilibrée (maximum balanced biclique problem) est NP-difficile
(alors que le même problème sans la contrainte d’équilibre est polynomial).
 Graphe complet
Déf : 𝐺𝐺 = 𝑉𝑉, 𝐸𝐸 est un graph complet ssi pour tout 𝑥𝑥, 𝑦𝑦 ∈ 𝑉𝑉, 𝑥𝑥, 𝑦𝑦 ∈ 𝐸𝐸.

Rm: un graphe complet est aussi appelé « clique »

 Clique
Déf : Soit 𝐺𝐺 = 𝑉𝑉, 𝐸𝐸 , une clique 𝐶𝐶 de 𝐺𝐺 est un sous-ensemble de 𝑉𝑉 tq chaque pair de sommets de 𝐶𝐶 sont adjacents,
i.e., pour tout 𝑥𝑥, 𝑦𝑦 ∈ 𝐶𝐶, 𝑥𝑥, 𝑦𝑦 ∈ 𝐸𝐸.

Une clique est maximale si elle n'est contenue dans aucune autre clique, une clique est maximum si sa cardinalité est la
plus grande parmi toutes les cliques du graphe.

Rm: Problème de clique maximum (Maximum clique problem) : déterminer la clique maximum d’un graphe (NP-difficile)
 Clique, ensemble indépendant (stable) et couverture par sommets
Déf : Soit 𝐺𝐺 = 𝑉𝑉, 𝐸𝐸 , un ensemble indépendant ou stable 𝐼𝐼 de 𝐺𝐺 est un sous-ensemble de 𝑉𝑉 tq aucune pair de
sommets de 𝐼𝐼 sont adjacents, i.e., pour tout 𝑥𝑥, 𝑦𝑦 ∈ 𝐼𝐼, 𝑥𝑥, 𝑦𝑦 ∉ 𝐸𝐸.
Un stable 𝐼𝐼 est maximale si 𝐼𝐼 n'est pas un sous-ensemble d'un autre stable. Il est maximum si sa cardinalité est la plus
grande parmi tous les stables.

Rm: Problème de stable maximum (Maximum stable problem) : déterminer le stable maximum d’un graphe (NP-difficile)

Déf : Soit 𝐺𝐺 = 𝑉𝑉, 𝐸𝐸 , une couverture par sommets (vertex cover) est un sous-ensemble 𝑆𝑆 ⊂ 𝑉𝑉 tq
pour toute arête 𝑥𝑥, 𝑦𝑦 ∈ 𝐸𝐸, 𝑎𝑎𝑎𝑎 𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚 𝑢𝑢𝑢𝑢 𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑥𝑥 ∈ 𝑆𝑆 ou 𝑦𝑦 ∈ 𝑆𝑆. On dit que lʹensemble 𝑆𝑆 couvre les arêtes de 𝐺𝐺.

Rm: Problème de couverture minimum par sommets (Vertex cover problem) : déterminer la couverture par sommets de
cardinalité minimale (NP-difficile)
 Graphe complément, clique, ensemble indépendant (stable) et couverture par sommets

Déf : Soit 𝐺𝐺 = 𝑉𝑉, 𝐸𝐸 , le graphe complémentaire de 𝐺𝐺 est le graphe 𝐺𝐺̅ = 𝑉𝑉, 𝐸𝐸� tq
pour tout 𝑥𝑥, 𝑦𝑦 ∈ 𝑉𝑉, 𝑥𝑥, 𝑦𝑦 ∈ 𝐸𝐸� 𝑠𝑠𝑠𝑠𝑠𝑠 𝑥𝑥, 𝑦𝑦 ∉ 𝐸𝐸.

Rm:
1) 𝐺𝐺 + 𝐺𝐺̅ = graph complet
2) Le complément du graph complémentaire est le graphe initial

Théorème : Soit 𝐺𝐺 = 𝑉𝑉, 𝐸𝐸 , 𝐶𝐶 une clique de 𝐺𝐺

alors 𝐶𝐶 est un stable de 𝐺𝐺,̅ et V\C est une couverture par sommets de 𝐺𝐺̅

Rm: Problème de clique maximum = Problème de stable maximum = Problème de couverture minimum par sommets
 K-coloration de graphe

Déf (𝑘𝑘-coloration) : Soit 𝐺𝐺 = 𝑉𝑉, 𝐸𝐸 , et 𝑘𝑘 couleurs, déterminer s′ il est possible de colorier les sommets de 𝐺𝐺 tq
deux sommets adjacents ne recevoient pas la même couleur. Si une telle coloration existe, 𝐺𝐺 est dit 𝑘𝑘-coloriable.

Rm: Une 𝑘𝑘-coloration peut être

- définie par une fonction 𝑐𝑐 ∶ 𝑉𝑉 → 1,2, … 𝑘𝑘 tq pour tout 𝑥𝑥, 𝑦𝑦 ∈ 𝑉𝑉, 𝑠𝑠𝑠𝑠 𝑥𝑥, 𝑦𝑦 ∈ 𝐸𝐸, alors 𝑐𝑐(𝑥𝑥) ≠ 𝑐𝑐(𝑦𝑦).
- considérée comme une partition des sommets de 𝑉𝑉 dans 𝑘𝑘 classes de couleurs (stables) où chaque classe de couleurs regroupe
les sommets qui sont coloriés par la même couleur (donc tous non-adjacents deux-à-deux ⇒ stable).

2-coloriable & non 2-coloriable 3-coloriable 4-coloriable

Chaque classe de couleur forme un stable (un ensemble indépendant).

Rm: Le problème de 𝑘𝑘-coloration est NP-complet.

 Coloration de graphe et nombre chromatique

Déf (coloration et nombre chromatique) : Le problème de coloration est de déterminer le nombre 𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚𝑚
de couleurs 𝑘𝑘 pour un graphe 𝐺𝐺 tq 𝐺𝐺 est 𝑘𝑘−coloriable. Une telle 𝑘𝑘 est le nombre chromatique de 𝐺𝐺, noté 𝜒𝜒 𝐺𝐺 .

𝜒𝜒 𝐺𝐺 =3 (3 stables) 𝜒𝜒 𝐺𝐺 =4 (4 stables)

Exemple d’application : Problème de carré Latin partiel (Sudoku)

Autres appli (pb d’incompatibilité):
- allocation de fréquence (réseau mobile)
- allocation de registres (compilateur)
- emploi du temps (examen…)
- Cohabitation avec incompatibilité (personnes, animaux…)

Rm: Déterminer le nombre chromatique d’un graphe arbitraire est un problème NP-difficile.
 Coloration de graphe – cas particuliers

Graphe planaire (théorème de 4 couleurs, 1974)

Tout graphe planaire peut être colorié avec 𝑘𝑘 ≤ 4 couleurs.
i.e., soit 𝐺𝐺 un graphe planaire, alors 𝜒𝜒(𝐺𝐺) ≤ 4.

e.g. : Carte des départements français

Graphe Complet : Soit 𝐺𝐺 un graphe complet 𝐾𝐾𝑛𝑛 d’ordre 𝑘𝑘, alors 𝜒𝜒(𝐺𝐺) = 𝑛𝑛.

Rm: Une clique dans 𝐺𝐺 est une minorant (borne inférieur) de 𝜒𝜒(𝐺𝐺).

Graphe bi-partie: Soit 𝐺𝐺 un graphe bi-partie, alors 𝜒𝜒(𝐺𝐺) = 2.

Théorème: G est bi-coloriable ssi G est un graph bi-partie.

 Isomorphisme de graphes

Déf: Soit 𝐺𝐺 = 𝑉𝑉, 𝐸𝐸 et 𝐻𝐻 = 𝑉𝑉′, 𝐸𝐸′ sont isomorphes s’il existe une fonction bijective
𝑓𝑓: 𝑉𝑉 → 𝑉𝑉 ′ tel que pour tout 𝑥𝑥, 𝑦𝑦 ∈ 𝐸𝐸, {𝑓𝑓 𝑥𝑥 , 𝑓𝑓(𝑦𝑦)} ∈ 𝐸𝐸𝐸.

𝑓𝑓 est un isomorphisme de 𝐺𝐺 et 𝐻𝐻.

degré 4 (sommet 1)

degré 3 maximum

Ex. Combien y a-t-il de graphes simples non isomorphes avec n sommets, quand n vaut 2,3 ou 4

Rm: Déterminer si deux graphes sont isomorphes est un problème NP-intermédiaire (NP, mais ni NP-complet ni P).
 Applications

• Social network graphs: to tweet or not to tweet. Graphs that represent who knows whom, who communicates with
whom, who influences whom or other relationships in social structures. An example is the twitter graph of who
follows whom. These can be used to determine how information flows, how topics become hot, how communities
develop, or even who might be a good match for who, or is that whom.
 Applications
• Semantic networks. Vertices represent words or concepts and edges represent the relationships among the words or
concepts. These have been used in various models of how humans organize their knowledge, and how machines
might simulate such an organization.
 Applications

• Biological network graphs. Protein-protein interactions graphs - Vertices represent proteins and edges represent
interactions between them that carry out some biological function in the cell. These graphs can be used, for example,
to study molecular pathways—chains of molecular interactions in a cellular process. Humans have over 120K
proteins with millions of interactions among them.
 Applications
• Graphs in epidemiology. Vertices represent individuals and directed edges the transfer of an infectious disease from
one individual to another. Analyzing such graphs has become an important component in understanding and
controlling the spread of diseases.

• Graphs in compilers. Graphs are used extensively in compilers. They can be used for type inference, for so called data
flow analysis, register allocation and many other purposes. They are also used in specialized compilers, such as query
optimization in database languages.

• Constraint graphs. Graphs are often used to represent constraints among items. For example the GSM network for
cell phones consists of a collection of overlapping cells. Any pair of cells that overlap must operate at different
frequencies. These constraints can be modeled as a graph where the cells are vertices and edges are placed between
cells that overlap.

• Dependence graphs. Graphs can be used to represent dependences or precedences among items. Such graphs are
often used in large projects in laying out what components rely on other components and used to minimize the total
time or cost to completion while abiding by the dependences.
 Applications

• Neural networks. Vertices represent neurons and edges the synapses between them. Neural networks are used to
understand how our brain works and how connections change when we learn. The human brain has about 1011
neurons and close to 1015 synapses.

• Network packet traffic graphs. Vertices are IP (Internet protocol) addresses and edges are the packets that flow
between them. Such graphs are used for analyzing network security, studying the spread of worms, and tracking
criminal or non-criminal activity.

• Scene graphs. In graphics and computer games scene graphs represent the logical or spacial relationships between
objects in a scene. Such graphs are very important in the computer games industry.

• Finite element meshes. In engineering many simulations of physical systems, such as the flow of air over a car or
airplane wing, the spread of earthquakes through the ground, or the structural vibrations of a building, involve
partitioning space into discrete elements. The elements along with the connections between adjacent elements
forms a graph that is called a finite element mesh.

• Robot planning. Vertices represent states the robot can be in and the edges the possible transitions between the
states. This requires approximating continuous motion as a sequence of discrete steps. Such graph plans are used, for
example, in planning paths for autonomous vehicles.
 Applications

• Transportation networks. In road networks vertices are intersections and edges are the road segments between
them, and for public transportation networks vertices are stops and edges are the links between them. Such
networks are used by many map programs such as Google maps, Bing maps and now Apple IOS 6 maps (well perhaps
without the public transport) to find the best routes between locations. They are also used for studying traffic
patterns, traffic light timings, and many aspects of transportation.

• Utility graphs. The power grid, the Internet, and the water network are all examples of graphs where vertices
represent connection points, and edges the wires or pipes between them. Analyzing properties of these graphs is
very important in understanding the reliability of such utilities under failure or attack, or in minimizing the costs to
build infrastructure that matches required demands.

• Document link graphs. The best known example is the link graph of the web, where each web page is a vertex, and
each hyperlink a directed edge. Link graphs are used, for example, to analyze relevance of web pages, the best
sources of information, and good link sites.