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ù :

1. V est un ensemble fini non vide de sommets (nœuds)
2. 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é