Cours TP Graphes.pdf
Introduction
Zoologie des graphes

Graphe non orienté simple

Graphe orienté simple

Graphe pondéré
Graphes et arbres

Arbre

Graphe non orienté, pas simple
Définitions
Graphe non orienté simple
Un graphe non orienté simple G est un couple ordonné
(V, E), où :
- V est un ensemble fini non vide de sommets (nœuds)
- E est un ensemble d'arêtes, où chaque arête est un
ensemble non ordonné de deux sommets distincts.
Dans un graphe non orienté simple :
- Pas d’arêtes multiples entre deux sommets
- Pas de boucles
Graphe orienté simple
Un graphe orienté simple G est un couple ordonné (V,A), où :
- V est un ensemble fini non vide de sommets (nœuds)
- A est un ensemble d’arcs (ou flèches), où chaque arc est un couple ordonné de deux sommets distincts
Dans un graphe orienté simple :
- Les relations entre les sommets sont directionnelles
- Pas d’arcs multiples ayant la même direction entre deux sommets
- Pas de boucles
<aside>
💡 Relations unidirectionnelles entre les sommets, sans redondance ni auto-connexion.
</aside>
Adjacence, incidence, degré