Diaporama n°26¶

Graphes - Introduction¶

"Définition"¶

Un graphe =

Des ronds (les sommets)

Reliés par des traits (arêtes) (ou des flèches : arcs)

Formellement : $G = (\mathcal{S}, \mathcal{A})$

où $\mathcal{S}$ est l'ensemble des sommets
et $\mathcal{A}$ est un ensemble d'arêtes (ou arcs)

Graphe (non-orienté)¶

lorsque la relation entre sommets est symétrique

Graphe orienté¶

lorsque la relation entre sommets est asymétrique

On parle de prédécesseur et de successeur

Exemples de graphes¶

Réseaux physiques : routiers, transports, internet ...¶

Voies romaines : 150000 km de routes reliant les principales villes de l'empire Romain

Réseau bus Limoges : 1000 arrêts, 55 lignes

Reseau Fibre (Proxad / Free) : > 100000km de fibre

Graphe orienté - rues à sens unique¶

Graphe de dépendances¶

Réseaux virtuels¶

Pages web : 1,7 milliards de sites, ... milliards de pages, ... milliards de liens
Réseaux sociaux : Facebook : 3 milliards d'utilisateurs, 300 fois plus de liens d'"amitié"

...

Un très gros réseau¶

Le cerveau humain : 100 milliards de neurones, 1000 fois plus de connections ...

Exemples de problèmes¶

(Historique) Leonhard Euler (1735) : Le problème des sept ponts de Königsberg¶

"Est-il possible de se promener dans la ville en passant une et une seule fois par chaque pont ?"

Les 4 sommets sont 4 zones vertes
Les 7 arêtes sont les 7 ponts

Existe-t-il un chemin qui emprunte une et une seule fois chaque arête ? (chemin eulérien)

Réponse : sur cet exemple, Non ! (démontré par Euler)

Labyrinthe¶

Peut-on aller de A à B dans ce labyrinthe ?

Les sommets sont les emplacements
Les arêtes sont les liens entre emplacements voisins

Existe-t-il un chemin entre A et B ?

Réponse : sur cet exemple, Oui !

Problème du "voyageur de commerce"¶

Quel le plus court trajet pour visiter les villes indiquées?

Problème "NP-Complet"