Remerciez-le!

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

Cours math theorie des graphes bac economie amp gestion 2010 2011 mr hidouri mosbah

Les graphes ? ? ? ? ? I Graphe Non Orienté Simple Soit le graphe G ci-dessous I ème Sciences de l'Informatiques ? Un graphe non orienté simple est la donnée d ? un ensemble ?ni non vide de points appelés sommets et d ? un ensemble de liens entre deux sommets appelés arêtes deux sommets étant reliés par au plus une arrête une arête reliant A et B est une paire A B ou simplement A ??B ? Deux sommets reliés par une arête sont dits adjacents Exemple A et B sont adjacents mais A et C ne le sont pas ? L ? ordre d ? un graphe est le nombre de sommets de ce graphe Exemple l'ordre de G est égal à ? Le degré d ? un sommet est le nombre d ? arêtes dont ce sommet est une extrémité Exemple le degré de A est égal à et celui de C est égal à ? Un graphe complet est un graphe tel qu ? il existe toujours une arête entre deux sommets quelconques Exemple G n'est pas complet car A n'est pas relié à C par une arrête ? Un sous graphe d ? un graphe G est un graphe G ? composé de certains sommets de G ainsi que de toutes arêtes qui le relient ? Un sous graphe stable est un sous graphe sans arête les sommets sont dits isolés Exemple Le sous graphe ci-dessous est un sous graphe de complet G Lemme des poignées de mains La somme des degrés des sommets d ? un graphe non orienté est égale à deux fois le nombre d ? arêtes du graphe Application Pour le graphe G On a Deg A Deg B Deg C Deg D Deg E ? Remarque Deg veut dire degré une notation non adaptée dans le chapitre ? Une cha? ne est une liste ordonnée de sommets telle que chaque sommet de la liste est adjacent au suivant Exemple A ??B ??C ??D est une cha? ne ? La longueur d ? une cha? ne est le nombre d ? arêtes qui la composent Exemple A ??B ??C ??D est de longueur égale à ? Une cha? ne est fermée lorsque l ? origine et l ? extrémité sont confondues Exemple A ??B ??C ??D ??A est une cha? ne fermée ? Un cycle est une cha? ne fermée dont toutes les arêtes sont distinctes Exemple A ??B ??C ??D ??B ??A est une cha? ne mais n'est pas un cycle Mr HIDOURI Mosbah CLes graphes ? ? ? ? ? I ème Sciences de l'Informatiques ? La distance entre deux sommets est la plus courte longueur des cha? nes qui le relient Exemple la distance entre A et C est la longueur de la cha? ne A ??B ??C qui est ? Le diamètre d ? un graphe est la plus grande distance entre deux sommets du graphe Exemple le diamètre de G est la distance entre A