Généralités sur les graphes

Concepts élémentaires de base

Concept de graphe Devant un grand nombre de situations ,le mathématicien ,comme d’ailleurs le psychologue, le planificateur ou le chimiste, a été amené à tracer sur le papier des points (représentant des nombres ,des localités, des opérations, des molécules chimiques etc …) et des lignes continues reliant certaines paires de ces points et symbolisant une relation, une route, une préférence ,etc.… Pour raisonner sur de telles situations on a convenu d’appeler graphe de tels schémas. Les points sont appelés « sommets ».Les « arcs » ou « arêtes » sont les lignes (suivant qu’elles sont orientées ou non). Définition formalisée 1 De façon plus formalisée, un graphe G = (S , A) est le couple constitué. Par un ensemble S = {s1 ,s2 …sn } dont les éléments sont appelés sommets . Par une famille A = {a1 ,a2 ;……..an}d’éléments du produit cartésien SxS  S  = card.( S) est appelé ordre du graphe. Les sommets si et sj tels que (si ;sj) Є A sont les extrémités de (s i , sj) Exemple 1 a1 a2 a3 a4 a5 a7 a5 Dans la séquence A , il peut y avoir plusieurs couples identiques par exemple a1= (a, b) , a2 = (a, b) , a3 = (a, b) . Lorsque le nombre de couples identiques ne dépasse pas un entier p on dira que G est un p- graphe. figure1  Exemple 2 Le graphe G de la figure 1est donc un 3- graphe Définition 2 Si les sommets si et sj sont les extrémités de aij Є A alors on dit que aij = (si, sj ) est un incident à si et sj , d(si) qui est le nombre d’éléments de A incidents à si est le degrés du sommet si d(si) = 0 alors le sommet est si isolé d(si) = 1 alors le sommet est si est pendant . Remarque 1 Le graphe à n sommets tel que tous ses sommets soient isolés est appelé le graphe nul. Il est noté Nn Définition 3 Soit G = (S , A) un graphe deux sommets si et sj sont adjacent s’il existe aij = (si ;sj ) Є A. Exemple 3 G = {1,2,3,4,5} et A = { (1 ,2) , (1, 3) , (1, 5), (3 ;4) , (3, 5) , (4, 5) }

Graphes non orientés

Définition 7 un graphe G = (S, A) est dit non orienté si les éléments de A sont non orientés . Dans ce cas les éléments de A sont appelés arêtes Définition 8 Soit (si, sj ) Є A ;alors si et sj sont les extrémités deux arêtes sont adjacents si elles ont au moins une extrémité commune. I-4 Sous graphe Pour caractériser de manière moins locale la structure d’un graphe, il est possible de rechercher des parties remarquables du graphe, en restreignant soit l’ensemble des sommets (sous graphes) soit l’ensemble des arêtes Définition 9 Soit G= (S , A) et H = (V, B) avec V ⊂ S et B ⊂ A alors H est un sous graphe de G Définition 10 Soit G= (S , A) un graphe et V ⊂ S . Le sous graphe de G engendré par V est le graphe Gv = (V, Av ) avec Av = {(si ,sj ) /si Є V et sj Є V} Définition 11 Soit G= (S, A) un graphe et B ⊂ A .On appelle graphe partiel de G engendré par B le graphe (S , B) 14 Définition 12 On appelle sous graphe partiel d’un graphe G = (S , A) le sous graphe d’un graphe partiel de G Exemple 5 Soit G H Le graphe H est un sous graphe de G il est engendré par { s1, s2, s3, s4} 1-5 Chaîne Cycle Chemin Circuit Dans un graphe il est naturel de vouloir se déplacer en sommet en suivant les arêtes .Une telle marche est appelée chaîne ou chemin. Un certain nombre de questions peuvent alors se poser : pour deux sommets du graphe , existe-t-il un chemin pour aller de l’un à l’autre ? Quel est l’ensemble des sommets que l’on peut atteindre depuis un sommet donné ?. Définition 13 Une chaîne d’un graphe G=(S , A) est une séquence d’arcs (a1, ….an ) telle que chaque arc ai de la séquence est attaché à a i-1 par une de ses extrémités et a a i+1 par l’autre de ses extrémités Remarque 4 La longueur L de la chaîne est le nombre d’arcs de la séquence -La chaîne est élémentaire si elle n’utilise pas deux fois le même sommet . -Dans une chaîne {(s0, s1)…(sn-1, sn)} le premier sommet s0 est appelé extrémité initiale tandis que le dernier Sn est l’extrémité finale.