Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Chap1 intro ESSECT ?? BC Théorie des graphes et optimisation CHAPITRE INTRODUCTION AUX GRAPHES DÉFINITIONS ET REPRÉSENTATIONS N Ben Azzouna Théorie des graphes - ESSECT CDé ?nitions Un graphe est un ensemble ?ni de sommets et d'arcs ou d ? arêtes dé ?ni c

ESSECT ?? BC Théorie des graphes et optimisation CHAPITRE INTRODUCTION AUX GRAPHES DÉFINITIONS ET REPRÉSENTATIONS N Ben Azzouna Théorie des graphes - ESSECT CDé ?nitions Un graphe est un ensemble ?ni de sommets et d'arcs ou d ? arêtes dé ?ni comme des couples G S A ou S est l ? ensemble des sommets et A l ? ensemble des arcs ou arêtes qui est un ensemble de couples de sommets si sj S Si e ? A et e ? a b a b S ?? a b sont les extrémités de l ? arc e ? Les sommets a et b sont dits adjacents Exemple G S A S a b c d A a b a d b d c d N Ben Azzouna Théorie des graphes - ESSECT CDé ?nitions Un sommet qui n ? appara? t dans aucune arête est dit isolé Le nombre de sommets est dit l ? ordre du graphe Un graphe discret d ? ordre n ? est dénoté par Dn et correspond à G S A S n A ? Une boucle est un arc ou une arête reliant un sommet à luimême N Ben Azzouna Théorie des graphes - ESSECT CDé ?nitions Un graphe partiel d ? un graphe est le graphe obtenu en supprimant certains arcs ou arêtes Un sous-graphe d ? un graphe est le graphe obtenu en supprimant certains sommets et tous les arcs ou arêtes incidents aux sommets supprimés N Ben Azzouna Théorie des graphes - ESSECT CGraphe orienté Dé ?nitions Dans un graphe orienté les couples si sj A sont orientés c ? est à dire que si sj est un couple ordonné o? si est le sommet initial et sj le sommet terminal Un couple si sj est appelé un arc et est représenté graphiquement par si ?sj N Ben Azzouna Théorie des graphes - ESSECT CGraphe orienté Dé ?nitions Un graphe orienté est un p-graphe s ? il comporte au plus p arcs entre deux sommets Le plus souvent on étudiera des -graphes Un graphe orienté est dit élémentaire s ? il ne contient pas de boucle Un graphe orienté est dit complet s ? il comporte un arc si sj et un arc sj si pour tout couple de sommets di ?érents si sj S On appelle clique un sous-graphe complet de G Dans un graphe orienté on distingue les sommets successeurs des sommets prédécesseurs ??succ si sj si sj A ??pred si sj sj si A N Ben Azzouna Théorie des graphes - ESSECT CGraphe orienté Dé ?nitions Dans un graphe orienté le demi-degré extérieur d ? un sommet si noté do si est le nombre d ? arcs partant de si dans le cas d ? un -graphe on aura do si succ si Le demi-degré intérieur d ? un sommet si noté do- si est le nombre d ? arcs arrivant à si dans le cas d ? un graphe on aura do- si pred si N