Théorie des graphes - 1

Embed Size (px)

Citation preview

  • 8/3/2019 Thorie des graphes - 1

    1/40

    Introduction la thorie des

    graphes

  • 8/3/2019 Thorie des graphes - 1

    2/40

    Elments de cours

    Algorithme decoloriage

    Algorithme de Kruskal

    Algorithme des CFC

    Applications

    Introduction

    Introduction

  • 8/3/2019 Thorie des graphes - 1

    3/40

    Introduction

    Quest ce quunGraphe ?

    ntroduction

    Pourquoi la thorie desgraphes ?

    A.A.A

  • 8/3/2019 Thorie des graphes - 1

    4/40

    IntroductionElm

    ents decours

    Elments decours

    A.A.A

  • 8/3/2019 Thorie des graphes - 1

    5/40

    Dfinition dunGraphes

    Un graphe G est dfini par :

    Un ensemble de sommets X. Un ensemble dartes U.

    On utilise alors la notation : G = (X, U)

    ments de cours

    Exemple

    a

    b

    d

    c

    X = {a, b, c, d}U = {u1, u2, u3, u4}

    Avec : u1 = (a,b) u2 = (a,c)u3 = (a,d) u4 = (b,d)

    u3u2

    u4

    u1

    Elments decours

    A.A.A

  • 8/3/2019 Thorie des graphes - 1

    6/40

    Elments decours

    ments de cours

    Graphes Orients

    a d

    bc

    Graphes NonOrients

    a

    b

    d

    c

    A.A.A

  • 8/3/2019 Thorie des graphes - 1

    7/40

    Elments decours

    ments de cours

    Ordre dun Graphe

    Lordre du graphe G(X,U), not |G|, est le nombre desommets du graphe.

    On a alors : |G| = card(X)

    a

    d

    c

    a

    b

    d

    c

    a

    b

    Graphedordre 4

    Graphedordre 3

    Graphedordre 2A.A.A

  • 8/3/2019 Thorie des graphes - 1

    8/40

    Elments decours

    ments de cours

    Graphe Simple

    Un graphe G est dit simple, si et seulement sil ne contientni boucle ni artes parallles.

    a

    b

    d

    c

    a

    d

    c

    a

    d

    c

    Ce graphe nest pas

    simple car il contient 2artes parallles

    Graphe

    simple

    Ce graphe nest pas

    simple car ilcontient une boucle A.A.A

  • 8/3/2019 Thorie des graphes - 1

    9/40

    Elments decours

    ments de cours

    GrapheComplet

    Un graphe G est dit complet si et seulement sil est simpleet si chacun de ses sommets est li tous ses autressommets.

    a

    b

    d

    c

    a

    d

    c

    a

    d

    c

    Ce graphe nest pas

    complet car les deuxsommets b et c ne sont pas

    Graphe

    complet

    Ce graphe nest pas

    complet car il nestpas simple A.A.A

  • 8/3/2019 Thorie des graphes - 1

    10/40

    Elments decours

    ments de cours

    Degr dunsommet

    On appelle degr dun sommet d(x), le nombre de liaisonsdu sommet x.

    d : X ---> Nx ----> d(x)

    Exemple

    a

    b

    c

    d

    d(a) = 3

    d(b) = 2

    d(c) = 4

    d(d) = 1 , on dit que le sommet d est pendant

    d(e) = 0 , on dit que le sommet e est isol

    e

    A.A.A

  • 8/3/2019 Thorie des graphes - 1

    11/40

    Elments decours

    ments de cours

    Degr positif et degrngatif

    Pour les graphes orients, on dfinit les deux notions :

    - degr positif d + (x) : nombre darcs sortants dusommet x

    - degr ngatif d - (x) : nombre darcs entrants ausommet xExemp

    le

    a

    bc

    d+ (a) = 0d- (a) = 2

    d(a) = 2d+ (b) = 1d- (b) = 1

    d(b) = 2d+ (c) = 3 d- (c) = 1

    d(c) = 4

    A.A.A

  • 8/3/2019 Thorie des graphes - 1

    12/40

    Elments decours

    ments de cours

    Graphe Rgulier

    Un graphe G est dit rgulier si et seulement si tous sessommets ont le mme degr.

    a

    d

    c

    d(a) = d(b) = d(c) = 2

    Graphe rgulier

    Exemple

    A.A.A

  • 8/3/2019 Thorie des graphes - 1

    13/40

    Elments decours

    ments de cours

    Source / Puit

    Un sommet x est dit source si d+ (x) > 0 et d- (x) = 0

    Un sommet x est dit puit si d- (x) > 0 et d+ (x) = 0

    x

    x

    A.A.A

  • 8/3/2019 Thorie des graphes - 1

    14/40

    Elments decours

    ments de cours

    Notion dadjacence

    On dit que deux sommets x et y sont adjacents si x et ysont lis par au moins un arc u.

    On dit aussi que x et y sont deux extrmits terminales de

    larc u.

    ab

    Pour les graphes orients on parle aussi dextrmit

    initiale et extrmit finale.

    ab

    A.A.A

  • 8/3/2019 Thorie des graphes - 1

    15/40

    Elments decours

    ments de cours

    Matrice dadjacence / Graphes nonorients

    A =

    00011

    00121

    01010

    12101

    11010

    a

    b

    d

    e

    c

    a b c d e

    a

    bcde

    Matrice symtrique

    Aij = 2m N

    m tant le nombre darcs du graphe (y compris

    les boucles) et N le nombre de boucles

    Matrice carredordre n

    A.A.A

  • 8/3/2019 Thorie des graphes - 1

    16/40

    Elments decours

    ments de cours

    Matrice dadjacence / Graphes nonorients

    Matrice symtrique

    Aij = 2m N

    La somme des nombres dune mme ligne (ou dune mmecolonne) donne le degr du sommet correspondant.

    Si le graphe est simple la matrice sera compose que pardes 0 et 1 et la diagonale ne contiendra que des zros

    A.A.A

  • 8/3/2019 Thorie des graphes - 1

    17/40

    Elments decours

    ments de cours

    Matrice dadjacence / Graphesorients

    1 1 1 0 0

    0 0 1 0 0

    0 1 0 1 0

    1 0 0 1 1

    1 0 0 1 0

    A =a d

    bc

    e Matrice non symtrique

    Aij = mAvec m = card(U)

    A.A.A

  • 8/3/2019 Thorie des graphes - 1

    18/40

    Elments decours

    ments de cours

    Pondration

    Soit G = (X,U) un graphe

    On dfinit dans U lapplication l :

    l : U ---> Ru ----> l(u) : pondration

    Selon la nature du problme, l(u) peut reprsenter unelongueur, un cot, un poids,

    a

    b

    d

    c

    139

    1012

    2

    A.A.A

  • 8/3/2019 Thorie des graphes - 1

    19/40

    Algorithme deColoration

    Algorithme decoloration

    A.A.A

  • 8/3/2019 Thorie des graphes - 1

    20/40

    Algorithme deColoration

    Principe

    Le principe est de colorier les sommets dun graphe, de tellefaon attribuer:

    Pour deux sommets adjacents deux couleurs diffrentes

    Un nombre de couleur minimal

    Exemples

    a b

    c

    a b

    Algorithme deColoration

    A.A.A

  • 8/3/2019 Thorie des graphes - 1

    21/40

    Algorithme deColoration

    Nombrechromatique

    Le nombre chromatique est le plus petit nombre decouleurs ncessaires pour colorier le graphe.

    Si un graphe G contient un sous-graphe G completdordre

    p, alors son nombre chromatique est suprieur ou gal p.(G) >= (G)

    c

    a b

    c

    a b

    d(G)= 3

    (G)= 4

    Algorithme deColoration

    A.A.A

    l i h d

  • 8/3/2019 Thorie des graphes - 1

    22/40

    Algorithme deColoration

    Algorithme deColoration

    1. Classer les sommets du graphe dans une liste dans l'ordredcroissant de leur degr.

    2. En parcourant la liste dans l'ordre, attribuer une couleur nonencore utilise au premier sommet non encore color, et

    attribuer cette mme couleur chaque sommet non encorecolor et non adjacent un sommet de cette couleur.

    Exemple

    c

    a b

    d

    e

    x d(x) Couleur

    a 4b 2c 2d 1e 1

    C1C2

    C2

    C2

    C3a b

    d

    e

    c

    Algorithme de

    Coloration

    A.A.A

    l i h d

  • 8/3/2019 Thorie des graphes - 1

    23/40

    Algorithme deColoration

    Il est noter que le nombre de couleurs minimal obtenupar lalgorithme de coloration nest pas ncessairementoptimal. Ce dernier donne une coloration parmi plusieurspossibles.

    Le nombre de couleurs trouvs par lalgorithme est suprieurou gal au nombre chromatique.

    Le nombre chromatique du graphe est le plus petit nombrepossible de couleurs.

    Algorithme de

    Coloration

    Algorithme deColoration

    A.A.A

    l i h d

  • 8/3/2019 Thorie des graphes - 1

    24/40

    Algorithme deKruskal

    Algorithme deKruskal

    Algorithme deKruskal

    A.A.A

    Al i h d

  • 8/3/2019 Thorie des graphes - 1

    25/40

    Algorithme deKruskal

    Algorithme deKruskal

    Algorithme de

    Kruskal

    Le principe de cet algorithme est de dgager dun graphe nonorient pondr un arbre de poids minimal.

    Un arbre est un graphe sans cycles.

    Pour former donc notre arbre partir du graphe, on emprunteles artes dans lordre croissant de leur poids sans formeraucun cycle.

    Pour un graphe dordre n (n sommets), on sarte lorsquonaura emprunt n-1 artes.

    A.A.A

    Al ith d

  • 8/3/2019 Thorie des graphes - 1

    26/40

    Algorithme deKruskal

    Algorithme deKruskal

    Exempl

    es

    c

    a b

    d

    e

    c

    a b

    d

    e

    Arbre

    Ce graphe nest pasun arbre car il

    contient un cycle

    5 sommets 4artes

    A.A.A

    Al ith d

  • 8/3/2019 Thorie des graphes - 1

    27/40

    Algorithme deKruskal

    Algorithme deKruskal

    Exempl

    es

    On considre le graphe suivant et on essaie de chercher unarbre de poids minimal.

    c

    a b

    d

    e

    1

    55

    323

    5

    Effectivement, pour 5 sommets on obtient 4 artes.Poids de larbre = 1 + 2 + 3 + 5 = 11

    A.A.A

  • 8/3/2019 Thorie des graphes - 1

    28/40

    Algorithme desCFC

    Algorithme descomposantes

    fortement connexes

    A.A.A

    Algorithme des

  • 8/3/2019 Thorie des graphes - 1

    29/40

    Algorithme desCFC

    Algorithme desComposantes

    Fortement ConnexesGraphe fortement

    connexe

    Un graphe est dit fortement connexe si, entre tous

    sommetsxetyquelconques, il existe un cheminc = {u1 ,

    , um} qui commence enxet se termine eny.

    a

    c

    ba

    c

    b

    Ce graphe nest pasfortement connexe

    Ce graphe est fortementconnexe

    A.A.A

    Algorithme des

  • 8/3/2019 Thorie des graphes - 1

    30/40

    Algorithme desCFC

    Algorithme desComposantes

    Fortement ConnexesComposantes fortement

    connexes

    a d

    b

    f

    c e

    Ce graphe nest pas fortement connexe mais on dit quilcontient deux composantes fortement connexes

    A

    B

    A = {a, b, c} et B = {d, e, f}

    A.A.A

    Algorithme des

  • 8/3/2019 Thorie des graphes - 1

    31/40

    Algorithme desCFC

    Algorithme desComposantes

    Fortement ConnexesGraphe

    rduit

    a d

    b

    f

    c e

    AB

    Le graphe rduit du graphe ci-

    dessus est :

    Avec : A = {a, b, c} et B = {d, e, f}

    A B

    A.A.A

    Algorithme des

  • 8/3/2019 Thorie des graphes - 1

    32/40

    Algorithme desCFC

    Algorithme desComposantes

    Fortement Connexes

    Choisir un sommet x

    Marquer x par le signe +

    Marquer du signe + tout successeur de x et toutsuccesseur dun sommet marqu dun +

    Marquer x par le signe - Marquer du signe - tout prdcesseur de x et tout

    prdcesseur dun sommet marqu dun

    Lensemble des sommets marqus du signe + et - constituentla composante fortement connexe maximale issue dusommet s.

    Algorithme des Composantes

    fortement connexes

    A.A.A

    Algorithme des

  • 8/3/2019 Thorie des graphes - 1

    33/40

    Algorithme desCFC

    Algorithme desComposantes

    Fortement ConnexesExempl

    e

    a d

    b

    f

    c e

    +

    -+

    -

    + ++

    ++

    -+

    -

    -

    -

    +

    Cherchons les composantes fortement connexes dugraphe suivant, en appliquant notre algorithme :

    A.A.A

  • 8/3/2019 Thorie des graphes - 1

    34/40

    Applications

    A.A.A

    pplications

  • 8/3/2019 Thorie des graphes - 1

    35/40

    pplications

    Exercic

    e 1A, B, C, D, E, F, G et H dsignent huit poissons. Dans le tableau ci-dessous, une croix signifie que les poissons ne peuvent pascohabiter dans un mme aquarium:

    1. Formuler ce problme comme un problme de coloration dans ungraphe o les poissons reprsenteront les sommets du graphe.2. Utiliser lalgorithme donn au cours pour trouver une coloration.3. a) Que peut on dire du sous graphe G engendr par {A, C, D, H}.

    b) En dduire le nombre chromatique.

    A.A.A

    pplications

  • 8/3/2019 Thorie des graphes - 1

    36/40

    pplications

    Exercic

    e 21 2 3 4 5

    6 7 8 9 10

    11 12 13 14

    15 16 17 18

    1. Trouver les composantes fortement connexes.2. Tracer le graphe rduit.3. Changer lorientation dun seul arc pour que tout le graphe devienne

    fortement connexe. A.A.A

    pplications

  • 8/3/2019 Thorie des graphes - 1

    37/40

    pplications

    Exercic

    e 3

    1 2 3 4 5

    6 7 8 9 10

    11 12 13 14

    15 16 17 18

    1

    2

    5

    7

    45

    3 10 8 27

    9

    7

    813

    9

    10

    124

    39

    2

    4 8

    94 11

    2

    7 5

    109

    uver dans le graphe suivant larbre de poids minimum et calculer son poids

    A.A.A

    pplications

  • 8/3/2019 Thorie des graphes - 1

    38/40

    pplications

    Exercic

    e 4

    ste-t-il un graphe simple dordre 11 dont tous les sommets sont de degr 3 ?ui, dessinez-en un.

    A.A.A

    Le graphe est dordre 11 donc il contient 11 sommets

    t on a chaque sommet est de degr 3

    onc d(x) = 11 * 3 !!! Absurde !!

    ar la somme totale des degrs dun graphe est toujours paire

    pplications

  • 8/3/2019 Thorie des graphes - 1

    39/40

    pplications

    Exercic

    e 5onsidrons les deux graphes suivants :

    1 32 1 32

    On dsigne par A1 (resp. A2) la matrice dadjacence de G1 (resp. G2).

    1. Donner A1 et A22. Calculer A1n et A2n pour tout entier naturel n non nul.

    3. Retrouver les valeurs de A1n et A2n sans calcul, partir desgraphes G1 et G2 seulement.4. Considrons un graphe G orient et simple et A sa matricedadjacence. Donner une condition ncessaire et suffisante pour queAn devienne nulle partir dun certain entier n.

    G

    1

    G

    2

    A.A.A

    MERCI

  • 8/3/2019 Thorie des graphes - 1

    40/40

    Applications

    MERCI

    Merci pour votreattention