Remerciez-le!

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

Ch1 definition de base thg

IChapitre Dé ?nitions de base Partie A Deux dé ?nitions indissociables pour les graphes Comme on vient de le préciser au ? Avertissement un graphe peut être dé ?ni de manière intuitive ou mathématique Ces deux aspects sont indissociables et donnent les deux dé ?nitions suivantes empruntées à C Berge Dé ?nition intuitive d'un graphe Un graphe est un schéma constitué par un ensemble ici supposé ?ni de points et par un ensemble de èches reliant chacune deux de ceux ci Les points sont appelés les sommets du graphe et les èches les arcs du graphe Dans ce document on s'intéressera principalement aux graphes ?nis bien que de nombreuses notions puissent être généralisées Exemple Dans le graphe ci-après on a un ensemble de sommets un ensemble d'arcs C GEOMATIQUE S CH U N EXEMPLE DE GRAPHE Remarque La position des sommets et la forme des arcs sur une ?gure n'importe pas seul importe de savoir comment les sommets sont reliés Les graphes des graphes et ci-après sont dits isomorphes S CH U N GRAPHE ISOMORPHE AU GRAPHE DE LA FIGURE PRÉCÉDENTE CDé ?nitions de base Notation L'arc va du sommet au sommet On dit qu'il est de la forme et on écrit par convention que On remarque que si la forme su ?t pour désigner l'arc de manière univoque la forme ne su ?t pas pour désigner l'arc uniquement car également Dé ?nition mathématique d'un graphe Un graphe est le couple constitué par un ensemble par une famille d'éléments du produit cartésien Partie B Ordre orientation et multiplicité Ordre Selon les dé ?nitions précédentes l'ensemble de sommets est supposé ?ni Ordre du graphe On appelle ordre du graphe le nombre de sommets du graphe Notation L'ordre de est donc le cardinal de et noté Exemple Le graphe de la ?gure un exemple de graphe est d'ordre Orientation Arête Selon C Berge les premiers mathématiciens qui se sont intéressés aux graphes considéraient des graphes non orientés Il n'y a en fait qu'une espèce de graphes et une seule théorie Par contre certaines propriétés ne sont pas directement concernées par l'orientation des arcs Dans ce cas on ne parle plus d'arc mais d'arête du graphe - On peut citer par exemple D K? nig P Erd? s P Turan T Gallai ou G Hajos - La direction indiquée par le sens de la èche C GEOMATIQUE Arête Une arête est un ensemble de sommets ensemble de cardinalité ou Une arête est donc un élément de l'ensemble des parties à deux éléments de l'ensemble Notation La notation pourrait être employée mais il faudrait écrire Soit un graphe on notera donc les arêtes sous la forme Multigraphe Graphe non orienté Un graphe non orienté sera appelé un multigraphe et noté Remarque Dans un multigraphe il peut y avoir plusieurs arêtes entre deux sommets Convention Pour appliquer un concept orienté dans un multigraphe on considérera en fait le graphe orienté associé obtenu en orientant chaque arête dans les deux sens Réciproquement un concept non orienté