TG - Sance 1

Recherche oprationnelle applique la gestion des systmes industriels

Pr Adil BELLABDAOUI [email protected] www.tra-log.org/fst-settat/

Thorie des graphes

Mthodes et applications de RO

Recherche Oprationnelle

Prog. Math.

Opt. Comb.

Th. des graphes

Modl. Stochas.

Logique floue

Mth. Multi.

Logistique Gestion de lenvironnnement

Gestion de production

Transport Distribution

Planification

Choix dinvestissementRecherche oprationnelle applique la gestion des systmes industriels Sance 6, page 3 1, 2010 Bellabdaoui

Pourquoi la thorie des graphes ? Modlisation Plusieurs problmes dans diffrentes disciplines (chimie, biologie, sciences sociales, applications industrielles, ) Un graphe peut reprsenter simplement la structure, les connexions, les cheminements possibles dun ensemble complexe comprenant un grand nombre de situations Un graphe est une structure de donnes puissante pour linformatique

Recherche oprationnelle applique la gestion des systmes industriels Sance 6, page 4 2010 Bellabdaoui

Dfinitions Concepts orients Un graphe G(X,U) est dtermin par Un ensemble X={x1,,xn} de sommets Un ensemble U={u1, , um} du produit cartsien X X darcs.Arc u=(xi,xj) boucle

Un p-graphe : pas plus que p arcs (xi,xj)3-graphe

1-graphe = graphe


Dfinitions Successeurs et prdcesseurs xj est successeur de xi si (xi,xj) U Lensemble des successeurs de xi est not (xi) Lensemble des prdcesseurs de xi est not -1(xi) est appele une application multivoque Pour un 1-graphe, G peut tre parfaitement dtermin (ou caractris) par (X, ) Si u=(xi,xj) U, alors : i est lextrmit initiale de larc u, posons i=I(u) j est lextrmit terminale de larc u, posons j=T(u)Recherche oprationnelle applique la gestion des systmes industriels Sance 6, page 6 2010 Bellabdaoui

Dfinitions Concepts non orients On sintresse lexistence darcs entre deux sommets sans en prciser lordre Arc = arte U est constitu de paires non pas de couples Multigraphe : plusieurs artes entre deux sommets Graphe simple = non multigraphe + pas de boucles


Dfinitions Adjacence I et j sont deux sommets adjacents sil existe un arc u=(xi,xj) U Larc u =(xi,xj) est adjacent aux sommets i et j Deux arcs sont adjacents sils sont incidents un mme sommets


Dfinitions Degr dun sommet dG ( x) u U / I (u) x : Le nombre darcs dont x est lextrmit initiale. Il est appel le demi degr extrieur du sommet x dG ( x) u U / T (u) x : Le nombre darcs dont x est lextrmit terminale. Il est appel le demi degr intrieur du sommet x. d G ( x ) d G ( x ) d G ( x ) : Le nombre darc adjacents au sommet x. Il est appel le degr du sommet x


Thorme 1 Soit G=(X,U) un graphe. On a :dG ( x)x X x X

dG ( x)

U

Corollaire 1 Dans un graphe G=(X,U), on a :dG ( x)x X

2* U

Corollaire 2 Dans un graphe G=(X,U), le nombre de sommets de degr impair est pair.Recherche oprationnelle applique la gestion des systmes industriels Sance 6, page 10 2010 Bellabdaoui

Exercice 1

Construire un graphe orient dont les sommets sont les entiers compris entre 1 et 12 et dont les arcs reprsentent la relation tre diviseur de .


Reprsentations dun graphe Matrice dincidence sommets-arcs

Place mmoire : n x m


Reprsentations dun graphe Matrice dadjacence

Place mmoire : n

Pour un graphe numris : remplacer 1 par la valeur de larcRecherche oprationnelle applique la gestion des systmes industriels Sance 6, page 13 2010 Bellabdaoui

Soit G=(X,U) un graphe. Etant donn A X et V U. On appelle : - Sous graphe engendr par A : le graphe GA dont les sommets sont les lments de A et dont les arcs sont les arcs de G ayant leurs deux extrmits dans A. - Graphe partiel engendr par V : le graphe ayant le mme ensemble X de sommets que G et dont les arcs sont les arcs de V. - Sous graphe partiel engendr par A et V : le graphe dont les sommets sont les lments de A et dont les arcs sont les arcs de V ayant deux extrmits dans A.


Connexit dans les graphes Soit G=(X,U) un graphe et x, y X. Une chane de longueur q joignant x y dans G est une squence de q arcs de G : L={u1, u2, ,uq} telle que: Le 1er arc u1 est adjacent x par une de ses extrmits et au second arc u2 par son autre extrmit. Le dernier arc uq est adjacent y par une de ses extrmits et lavant dernier arc uq-1 par son autre extrmit. Chaque arc ur (2 r q-1) est adjacent au prcdent ur1 par une de ses extrmits et au suivant ur+1 par lautre extrmit.


Connexit dans les graphes Une chane est simple si la squence darcs qui la constituent ne comporte pas plusieurs fois le mme lment. Une chane est lmentaire si en la parcourant on ne rencontre pas deux fois le mme somment. Un cycle est une chane simple dont les extrmits sont confondues.

Remarque : une chane lmentaire est videmment simple.


Notations de graphe orient et non orientOrient Non orient G(X,U) G(X,E) Sommets (nuds, points) Arcs Arrtes Chemin Chaine Circuit Cycle


Notations de graphe orient et non orient Chane Cycle

Chemin Circuit


Connexit dans les graphes Le terme parcours regroupe les chemins, les chanes, les circuits et les cycles Un parcours peut tre lmentaire : tous les sommets sont distincts simple : tous les arcs sont distincts hamiltonien : passe une fois et une seule par chaque sommet eulrien : passe une fois et une seule par chaque arc prhamiltonien : ou moins une fois par chaque sommet preulrien : au moins une fois par chaque arc


Connexit dans les graphes Exemple Le problme du voyageur de commerce : un voyageur de commerce doit visiter n villes donnes en passant par chaque ville exactement une fois et doit revenir la ville de dpart. Trouver un circuit hamiltonien de cot minimal dans un graphe valu


Exercice 2a. Montrer que, tout chemin (resp. chane) lmentaire est simple. b. Montrer que si dans un graphe G, il existe un chemin (resp. chane) du sommet x au sommet y, alors il existe un chemin (resp. chane) lmentaire de x y.


Exercice 3Une chvre, un chou et un loup se trouve sur la rive dun fleuve ; un passeur veut les changer de rive, mais sa barque tant trop petite, il ne peut transporter quun seul dentre-deux la fois. Pour des raisons videntes, on ne peut laisser sans surveillance le loup en compagnie de la chvre ou la chvre en compagnie du chou. Montrer que la rsolution de ce problme revient chercher, dans un graphe quon dessinera, un chemin allant de ltat a (o la chvre, le chou, le loup et le passeur se trouvent ensemble sur la rive gauche) ltat b (o rien ne se trouve plus sur la rive gauche).


Exercice 4Montrer que, dans un graphe simple G, il existe au moins deux sommets qui ont le mme degr.


Exercice 5Montrer que tout circuit (resp. cycle) est union disjointe au sens des arcs (resp. artes) de circuits (resp. cycles) lmentaires.


Exercice 6Montrer que si G = (X, E) est connexe alors pour toute arte e de G, G = (X, E {e}) a au plus 2 composantes connexes.


Exercice 7Montrer que si un graphe a exactement deux sommets de degr impair, alors il existe une chane reliant ces deux sommets.


Connexit dans les graphes Connexit


Connexit dans les graphes Forte connexit


Exercice 8Un cycle dun graphe comportant toutes les artes du graphe est appel cycle dEuler. Un graphe contenant un cycle dEuler est appel graphe dEuler.

Montrer que pour un graphe connexe fini G, G est un graphe dEuler si et seulement si tous ses sommets sont de degr pair.


Exercice 91. En partant de la dfinition d1 arbre c'est--dire 1 connexe et sans cycles. Montrer que tout arbre dordre 2 a au moins 2 sommets pendants.

2. Montrer par rcurrence sur lordre de graphe quun arbre dordre n a (n-1) artes. a. En utilisant 2.1 b. Sans utilisation de 2.1


Coloration dun graphe


Coloration dun graphe


Exercice 10Huit pays sont reprsents ci-dessous avec leur frontire (deux pays dont les frontires nont quun nombre fini de points ne sont pas considrs comme voisins)

1. Reprsentez cette situation par un graphe dordre 8 dont les sommets sont les pays et les artes les frontires.

2. Est-il possible de partir dun pays et dy revenir aprs avoir franchi chaque frontire une fois et une seule ?3. est-il possible de partir dun pays, de franchir chaque frontire une fois et une seule et de terminer en un autre pays ?Recherche oprationnelle applique la gestion des systmes industriels Sance 6, page 33 2010 Bellabdaoui

Documents

TG - Sance 1