Les graphes seront utilisés tout au long de ce livre. Dans ce chapitre nous donnerons les définitions de base et nous préciserons nos notations. Nous présenterons également quelques théorèmes classiques et quelques algorithmes fondamentaux.
Après les définitions du paragraphe 2.1, nous étudierons quelques structures essentielles souvent rencontrées dans ce livre : les arbres, les cycles, les coupes. Nous démontrerons quelques propriétés importantes, et nous considérerons des systèmes d’ensembles reliés aux arbres au paragraphe 2.2. L’algorithme de recherche des composantes connexes ou fortement connexes sera présenté au paragraphe 2.3. Nous démontrerons le théorème d’Euler relatif aux parcours fermés qui passent une seule fois par chaque arête au paragraphe 2.4. Enfin, nous étudierons les graphes dessinables sur un plan sans que les arêtes se croisent aux paragraphes 2.5 et 2.6.
Un graphe non orienté est un triplet (V, E, Ψ) constitué de deux ensembles finis V et E et d’une application Ψ : E → {X ⊆ V : |X| = 2}. Un graphe orienté est un triplet (V, E, Ψ), constitué de deux ensembles finis V et E et d’une application Ψ : E → {(υ, w) ∈ V × V : υ ≠ w}. V est l’ensemble des sommets du graphe ; E est l’ensemble de ses arêtes si le graphe est non orienté et de ses arcs s’il est orienté. Une arête e = {υ, w} sera également notée e = (υ, w) ou e = (w, υ).
Des arcs ou arêtes distincts e, e′ seront dits parallèles si Ψ(e) = Ψ(e′). Un graphe sans arêtes ou arcs parallèles est un graph…