Remerciez-le!

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

Chapitre I Définitions de base Partie A. "Deux définitions indissociables" pour

Chapitre I Définitions de base Partie A. "Deux définitions indissociables" pour les graphes Comme on vient de le préciser au § "Avertissement", un graphe peut être défini de manière "intuitive" ou mathématique. Ces deux aspects sont indissociables et donnent les deux définitions suivantes (empruntées à C. Berge) : 1. Définition "intuitive" d'un graphe "Un graphe est un schéma constitué par un ensemble (ici supposé fini [*]) de points et par un ensemble de flèches reliant chacune deux de ceux ci. Les points sont appelés les sommets du graphe, et les flèches les arcs du graphe." [* Dans ce document, on s'intéressera principalement aux graphes finis 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 : S CH . 1 : U N EXEMPLE DE GRAPHE Remarque "La position des sommets et la forme des arcs sur une figure n'importe pas ; seul importe de savoir comment les sommets sont reliés". Les graphes des graphes 1 et ci-après sont dits isomorphes . S CH . 2 : U N GRAPHE ISOMORPHE AU GRAPHE DE LA FIGURE PRÉCÉDENTE 10 GEOMATIQUE Notation : L'arc 3 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 suffit pour désigner l'arc 6 de manière univoque, la forme ne suffit pas pour désigner l'arc 1 uniquement car également. 2. Définition mathématique d'un graphe "Un graphe est le couple constitué : 1. par un ensemble 2. par une famille d'éléments du produit cartésien Partie B. Ordre, orientation et multiplicité 1. Ordre Selon les définitions précédentes, l'ensemble de sommets est supposé fini. 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 figure "un exemple de graphe" est d'ordre 8. 2. Orientation 2.1. Arête Selon C. Berge, les premiers mathématiciens [1 ]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 [2] des arcs. Dans ce cas, on ne parle plus d'arc mais d'arête du graphe. [1 - On peut citer par exemple : D. König, P. Erdös, P.Turan, T. Gallai ou G. Hajos.] [2 - La "direction" indiquée par le sens de la flèche.] Définitions de base 11 Arête Une arête est un ensemble de sommets (ensemble de cardinalité 1 ou 2). 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 . 2.2. 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é pourra être appliqué à un graphe (orienté) en omettant l'orientation des arcs. S CH . 3 : M ULTIGRAPHE ASSOCIÉ AU GRAPHE DE L ' IMAGE 1 12 GEOMATIQUE 3. Multiplicité 3.1. Boucle et extrémités Boucle et extrémités Un arc de la forme est une boucle . Soit un arc de la forme , et sont appelés les extrémités de l'arc : ♦ est l' extrémité initiale de l'arc ; ♦ est l' extrémité finale de l'arc. S CH . 4 : U N EXEMPLE DE BOUCLE ET D ' EXTRÉMITÉS 3.2. Multiplicité d'une paire x , y Multiplicité d'une paire x,y La multiplicité d'une paire est le nombre d'arcs (du graphe ) ayant comme extrémité initiale et comme extrémité finale. Notation La multiplicité d'une paire est notée : . On pose . est le nombre d'arcs ayant une extrémité en et une en . vaut deux fois le nombre de boucles en . Convention Si et sont deux sous ensembles de , on note également : et Définitions de base 13 3.3. p-graphe p-graphe Soit un graphe , si le nombre d'arcs qui va d'un sommet à un sommet de est inférieur ou égal à (pour tous les sommets et de ) alors on dit que est un p-graphe . Notation est un p-graphe Exemple Le graphe de la figure "un exemple de graphe" est un 2-graphe ( ). 3.4. Graphe simple Graphe simple Un graphe simple est un multigraphe : ♦ sans boucles ; ♦ tel qu'il n'y ait jamais plus d'une arête entre deux sommets quelconques S CH . 5 : U N EXEMPLE DE GRAPHE SIMPLE 14 GEOMATIQUE Partie C. Relations entre les éléments d'un graphe 1. Relations entre sommets 1.1. Sommets voisins Le sommet est un successeur du sommet s'il existe un arc de la forme : Le sommet est un prédécesseur du sommet s'il existe un arc de la forme : Le sommet est un voisin du sommet s'il existe un arc de la forme ou de la forme (autrement dit si est un successeur ou un prédécesseur de ). Un sommet pendant est un sommet qui n'a qu'un seul voisin. Notation L'ensemble des successeurs du sommet est noté : L'ensemble des prédécesseurs du sommet est noté : L'ensemble des voisins du sommet est noté : Convention On utilise aussi le terme de sommets adjacents pour parler de sommets voisins. Exemple Dans le graphe de la figure "un exemple de graphe" : 1.2. Sommet adjacent à un ensemble de sommets Sommet adjacent à un ensemble de sommets alors on dit que est un sommet adjacent à l'ensemble . Exemple Dans le graphe de la figure "un exemple de graphe", si on définit l'ensemble comme suit : alors . Définitions de base 15 1.3. Degré d'un sommet Degré d'un sommet Soit un sommet d'un graphe , le nombre d'arcs de la forme se note et s'appelle le demi-degré extérieur de . De même, le nombre d'arcs de la forme se note et s'appelle le demi-degré intérieur de . Le nombre est le degré du sommet , c'est le nombre d'arcs ayant une extrémité en (chaque boucle étant comptée deux fois). Si tous les sommets d'un graphe ont même degré, ce graphe est un graphe régulier . Remarque On peut remarquer que Par conséquent, on a (dans le cas d'un 1-graphe, il y a égalités). Exemple Dans le graphe de la figure "un exemple de graphe" : Ce graphe n'est pas régulier car par ailleurs : 2. Relations entre arcs et sommets 2.1. Arc incident à un sommet Arc incident à un sommet Si un sommet est l'extrémité initiale d'un arc alors est un arc incident au sommet vers l'extérieur . Si par contre, est l'extrémité finale d'un arc alors l'arc est un arc incident au sommet vers l'intérieur . Dans les deux cas, on dit que l'arc est un arc incident au sommet . Convention On utilise également l'appellation arc entrant pour incident vers l'intérieur et arc sortant pour incident vers l'extérieur. Un arc pendant est incident à un sommet pendant. 16 GEOMATIQUE 2.2. Arc incident à un ensemble Arc incident à un ensemble si l'extrémité initiale d'un arc appartient à mais pas son extrémité finale alors on dit que est un arc incident à l'ensemble vers l'extérieur . Par contre, si l'extrémité finale d'un arc appartient à mais pas son extrémité initiale alors on dit que est un arc incident à l'ensemble vers l'intérieur . Notation Si est incident à l'ensemble vers l'extérieur alors on note : . Si est incident à l'ensemble vers l'intérieur alors on note : L'ensemble des arcs incidents à l'ensemble est noté : Exemple Dans le graphe de la figure "un exemple de graphe", si on définit l'ensemble comme suit : alors 2.3. Arcs adjacents Deux arcs sont dits adjacents s'ils ont au moins un sommet commun (une extrémité commune). S CH . 6 : D EUX ARCS ADJACENTS 3. Qualificatifs des graphes 3.1. Sous-graphe partiel Soit un graphe quelconque. alors le sous graphe engendré par est le graphe dont les sommets sont les éléments de et dont les arcs sont les arcs de ayant leurs deux extrémités dans . alors le graphe partiel engendré par est le graphe ayant le même ensemble de sommets que , et dont les arcs sont les arcs de (on Définitions de base 17 élimine de les arcs de ). Un sous-graphe partiel de est un sous-graphe d'un graphe partiel de ou un graphe partiel d'un sous-graphe de . Exemple Le graphe de la figure "deux arcs adjacents" est un sous-graphe du graphe de la figure "un exemple de graphe". S CH . 7 : U N GRAPHE PARTIEL DU GRAPHE DE LA FIGURE 6 Le graphe de la figure "un graphe partiel du graphe de uploads/s3/ ch1-definition-de-base-thg.pdf