17 mar 2012 · Un graphe est cordal (ou triangulé) si tout cycle de longueur ≥ 4 possède une corde G1 est cordal, mais pas G2 Les graphes complets (Kn) et
Previous PDF | Next PDF |
[PDF] Détails mathématiques pour utiliser un ruban en hélice - EUorg
– Lorsque le ressort est allongé, la longueur du ruban restant invariable, calculer le nouveau rayon des spires r1(h0, r0, h1) ? h0 d0 Figure 1 h1 d1 Figure 2
[PDF] Graphes triangulés
6 avr 2016 · induit par les sommets d'un cycle de longueur 4 ou 5 contient un sommet adjacent `a tous les autres sommets du cycle On dit aussi cordal
[PDF] Nombre chromatique et sous-graphes induits (Partie 1) - EJCIM 2020
8 jui 2020 · Aucun cycle (induit) de longueur 4+ ? Graphe cordal ( Clique d'articulation) Marthe Bonamy Nombre chromatique et sous-graphes induits
[PDF] Théorie des graphes - LRDE - Epita
17 mar 2012 · Un graphe est cordal (ou triangulé) si tout cycle de longueur ≥ 4 possède une corde G1 est cordal, mais pas G2 Les graphes complets (Kn) et
[PDF] Paramétrisation optimale de coniques - IRIT
[0,L], où L est la longueur de la courbe paramétrisée par f sur U La norme de sa lise la "déviation cordale”, dans le cas d'un arc de longueur 2ψ du cercle
[PDF] Centrale Informatique optionnelle MP 2015 Corrigé
est cordal si tout cycle de longueur supérieure à quatre possède une corde montré que tout graphe d'intervalles est cordal, le sujet demande de résoudre
[PDF] Examen du module MGDE
Démonstration par récurrence : Dans le graphe G′ renvoyé, il ne peut exister de cycle non cordal de longueur 4 ou plus passant par Xσ(1) En effet, dans un tel
[PDF] NOUVEAUTÉS DE SOLIDWORKS® 2021— CAO - Visiativ Solutions
la longueur de courbes, et non la longueur cordale Simplification et amélioration des assemblages • Modèles simplifiés enregistrés en tant que configuration
[PDF] Centrale 2015 - Graphes I Graphes dintervalles - AlloSchool
Ordre d'élimination parfait pour un graphe cordal IV A Cycles de longueur 4 dans un graphe d'intervalles IV A1 Supposons, par l'absurde, que l'un des
[PDF] longueur corde pour arc 68 pouces
[PDF] Longueur d'arc et angle au centre
[PDF] Longueur d'onde des raies
[PDF] longueur d'ondes sonores
[PDF] Longueur d'un arc de parabole
[PDF] Longueur d'un cercle et d'un arc de cercle
[PDF] Longueur d'un coté d'un carré
[PDF] Longueur d'un rectangle
[PDF] Longueur d'un triangle DM 1ère S
[PDF] Longueur d'un vecteur
[PDF] Longueur d'un vers /poème
[PDF] Longueur d'une cellule bactérienne
[PDF] longueur d'une clôture en fonction de x
[PDF] Longueur d'une courbe (TS)
Théorie des graphes
Alexandre Duret-Lutz
adl@lrde.epita.fr17 mars 2012
A. Duret-LutzThéorie des graphes1 / 31
Huitième partie VIII
Graphes cordaux
1Qui a tué le Duc de Densmore?
2Graphe cordal
3Triangulation
4Exercices
5Stable, clique, séparateur, sommet simplicial
6Ordre d"élimination simplicial
7LexBFS
8Graphes d"intervalles
9Graphes d"Interférences pour l"allocation de registres
10Solution de Qui a tué le Duc de Densmore?
A. Duret-LutzThéorie des graphes2 / 31
Qui a tué le Duc de Densmore? (1/2)
Il s"agit du titre d"une nouvelle policière
1écrite par Claude Berge2
L"intrigue est la suivante :
Le Duc de Densmore est retrouvé carbonisé après l"explosion de son vieux château de l"île privée de White. L"enquête indique que l"explosion est due à une bombe placée dans la cave de château. Dans la période qui précéda l"explosion, le Duc avait invité ses 8 ex-femmes. Le capitaine du bateau qui faisait la navette entre l"île et le continent se souvient d"avoir transporté chacune des 8 femmespour un aller-retour, mais sans se souvenir des dates et heures.1. Bibliothèque Oulipienne n°67, 1994, Réédition Castor Astral, 2000.
2. C. Berge (1926-2002) est un mathématicien français considéré
comme l"un des fondateurs de la théorie des graphes telle que nous la connaissons. Son livreThéorie des Graphes et ses Applications(1954) a été écrit pour unifier une théorie qui existait uniquement de façon dispa- rate à l"étranger.A. Duret-LutzThéorie des graphes3 / 31
Qui a tué le Duc de Densmore? (2/2)
Les femmes ne se souviennent pas non plus des dates et heures, maisse rappellent s"être croisées. Ainsi :Anne a rencontré Félicie, Cynthia, Georgia, Emilie et Betty
Betty a rencontré Cynthia, Anne et Hélène Cynthia a rencontré Anne, Emilie, Diane, Betty et HélèneDiane a rencontré Cynthia et Emilie
Emilie a rencontré Félicie, Cynthia, Diane et AnneFélicie a rencontré Emilie et Anne
Georgia a rencontré Anne et Hélène
Hélène a rencontré Cynthia, Georgia et Betty On sait d"autre part que l"une de ces femmes était désavantagée par le testament. Ce dernier a malheureusement disparu dans l"incendie.A. Duret-LutzThéorie des graphes4 / 31
Graphe cordal
G 1=ab c deG 2=fgh i j kl mUn cycle élémentaire
est un c yclequi ne passe pa splusieurs fois pa r le même sommet. (a;b;c;d;e)est un cycle élémentaire, mais pas(b;c;d;e;c;a).Une corde
d"un cycle élémentaire est un ea rêtequi relie deux sommets non consécutifs du cycle. (a;c)est une corde de(a;b;c;e);(c;e)une corde de(a;c;d;e); toutes deux sont aussi des cordes de(a;b;c;d;e).Un graphe est cordal
(ou triangulé) si tout cycle de longueur4 possède une corde. G1est cordal, mais pasG2. Les graphes complets (Kn) et les arbres
sont des graphes cordaux.A. Duret-LutzThéorie des graphes5 / 31
Triangulation d"un graphe (1/2)
Il s"agit d"ajouter des cordes à un graphe pour le rendre cordal. Approche par élimination sur un grapheG= (V;E).Pouriallant de 1 àjVj:Choisir un sommetxideGConsidérer tous les voisinsN(xi)dexi, et ajouter les arcs
E i=N(xi)N(xi).Supprimer le sommetxi(et les arcs incidents) deG.Le grapheG0= (V;E[E1[E2[:::[EjVj)est cordal.
Note : le graphe obtenu diffère selon l"ordre d"élimination des états.A. Duret-LutzThéorie des graphes6 / 31
Triangulation d"un graphe (2/2)
G=a bc d e fg h x 1=abc d e fg h x 2=bc d e fg h x 3=cd e fg h x 4=de fg h x 5=efg h x 6=fg h x7=g:::x8=h:::G0=a
bc d e fg hA. Duret-LutzThéorie des graphes7 / 31
Triangulation minimale
SoitG= (V;E)un graphe, etG0= (V;E[F)une triangulation de G. (Freprésente les arcs ajoutés pour triangulariser le graphe.)G0 est unetriangulation minimaledeGsi il n"existe pas d"autre triangulation(V;E[F0)avecjF0j00montre une triangulation de 6 arcs, qui est minimale. (Il faut
ajouter au moins un arc par face du cube.) Trouver une triangulation minimale est un problème NP-complet.A. Duret-LutzThéorie des graphes8 / 31
Pause exercices
Exercice 1
Un a rbreest un graphe co rdal.Appliquer l"algo rithme d"élimination présenté précédemment risque de rajouter des arêtes superflues. Pouvez-vous trouver un ordre d"élimination des sommets qui n"ajoute aucune arête?Exercice 2
Le graphe suivant est co rdal.P ouvez-voustrouver unordre d"élimination qui n"ajoute aucune arête?(Indice : vous avez 2 chances sur 6 de bien commencer.)
L"objectif de la suite et de caractériser les sommets que l"on peut retirer ainsi (les sommetssimpliciaux) pour arriver à un algorithme de reconnaissance de graphes cordaux.A. Duret-LutzThéorie des graphes9 / 31
Stable et clique
Nous avons déjà parlé de stable en définissant le noyaux d"un graphe (pour chercher une stratégie gagnante dans un jeu) ou le problème de coloration des sommets d"un graphe.Un stable
dans un graphe G= (V;E)est un sous-ensemble de sommetsSVdeux à deux non adjacents (i.e.,(SS)\E=;).Une clique
est u nsous-ensemble Sdes sommets d"un graphe tels que tous les sommets deSsoit adjacents deux à deux. (Le grapheG[S] induit par ce sous-ensemble est complet). On parle den-clique lorsque la clique possèdensommets.Le complémentaire
d"un graphe G= (V;E)est le grapheG= (V;(VV)nE). Une clique dansGest un stable dansGet vice-versa.A. Duret-LutzThéorie des graphes10 / 31Séparateur minimal
Un séparateur
d"un graphe G= (V;E)est un sous-ensembleSV tel qu"il existe deux sommetsaetbnon adjacents dansGet non connectés dansG[VnS]. On parle aussi de(a;b)-séparateur.Un séparateur minimal
est un sépa rateurminimal si aucune de ses parties n"est un séparateur (note : différents séparateurs minimaux peuvent avoir des tailles différentes).xab c de fx;bg,fx;cg, etfx;dgsont des(a;e)-séparateurs minimaux. fx;b;cgest un(a;e)-séparateur non minimal. fb;c;dgn"est pas un séparateur.A. Duret-LutzThéorie des graphes11 / 31Séparateur minimal et graphe cordal (1/2)
Proposition
Si Gest cordal, tout séparateur minimal est une clique.Démonstration
Soit Sun(a;b)-séparateur minimal deG.
Tout sommet deSest sur un chemin qui connecteaàb, sinon on pourrait le retirer deSet obtenir un séparateur plus petit. Supposons par l"absurde queSpossède deux sommetsxetynon adjacents. Prenons le plus petit cycle qui passe para;x;b;y.x yab Ce cycle est au moins de longueur 4. Comme le graphe est cordal et que les sommets de part et d"autre du séparateur ne sont pas adjacents, le cycle admet nécessairement la corde(x;y): cela contredit notre hypothèse.A. Duret-LutzThéorie des graphes12 / 31
Séparateur minimal et graphe cordal (2/2)
Applicationfb;x;dgest un séparateur minimal du graphe suivant, mais il ne forme pas une clique : le graphe n"est donc pas cordal.a bcd xA. Duret-LutzThéorie des graphes13 / 31
Sommet simplicial
Un sommet simplicial
est un sommet dont les voisins sont to us adjacents deux à deux. Autrement ditN(x)est une clique, ou encoreG[N(x)]est complet.Sixest simplicial,N(x)est une clique (par définition), et fxg [N(x)est aussi une clique (puisquexest adjacent à tous ses voisins).Il s"agit d"une généralisation de la notion de feuille dans un arbre : une feuille est un sommet simplicial.Lesquels de ces graphes sont cordaux?A. Duret-LutzThéorie des graphes14 / 31
Sommet simplicial et graphe cordal
Proposition
Si un graphe G(non vide) est cordal, il possède un sommet simplicial. De plus, siGn"est pas complet il possède deux sommets simpliciaux non adjacents.Démonstration
P arrécurrence sur la taille du gr aphe.Si Gest complet, tous les sommets sont simpliciaux. Éliminons ce cas.Soient deux sommetsaetbnon adjacents, et soitSun
(a;b)-séparateur minimal : notonsG[A]etG[B]les graphes induits par les composantes deGnSqui contiennenta2Aetb2B.Montrons queApossède un sommet simplicial :soitG[A[S]est complet,aest simplicial dansG[A[S]sinon par récurrence il possède deux sommets simpliciaux non
adjacents, et l"un d"entre eux doit être dansA. Dans les deux cas, tous les voisins du sommet trouvé sont dansA[Sdonc c"est aussi un sommet simplicial deG.
On montre de même queBpossède un simplicial.A. Duret-LutzThéorie des graphes15 / 31Ordre d"élimination simplicial
Un ordre d"élimination simplicial
est un o rdre(x1;x2;:::;xjVj)sur les sommets deG= (V;E)tel quexiest un sommet simplicial de G[fxi;xi+1;:::;xjVjg]. Autrement dit, à chaque fois qu"on retire un sommet deGson voisinage forme une clique.Proposition
Un graphe Gest cordal si et seulement si il possède un ordre d"élimination simplicial.Démonstration
En appliquant récursivement la p roposition
précédente, on montre que siGest cordal, on trouve un sommet simplicial. Après suppression, le graphe reste cordal, et on recommence. Dans l"autre sens, si un graphe n"est pas cordal, c"est-à-dire qu"il existe un cycle sans corde de plus de trois sommets, aucun de ces sommets ne pourra être éliminé.A. Duret-LutzThéorie des graphes16 / 31
LexBFS : Parcours en largeur lexicographique (1/2)Algorithme LexBFS(G,s)
Entrée :G= (V;E)et un sommet sources2V.
Sortie := [x1;x2;:::;xjVj]un ordre total des sommets accessibles des.8x2V;label[x] []
label[s] [jVj]PouridejVjà 1 :
Choisir un sommetxd"étiquette lexicographique maximale [i] xPour chaque voisiny2N(x):
Siy62:
Concaténeri1 à la fin delabel[s]
Propriété
Si Gest cordal, le dernier sommet visité par LexBFS est simplicial. (Quelle que soit la source choisie.) L"ordreest donc un ordre d"élimination simplicial.A. Duret-LutzThéorie des graphes17 / 31
LexBFS : Parcours en largeur lexicographique (2/2) [6]6 [5][5][5]65[5;4][5;4][4][4]6
5[5;4;3]4
[4;3][4;3]6 534 [4;3][4;3;2]6 53
4 [4;3;1]26 53
4 12 Sur ce graphe cordal on peut vérifier que l"ordre construit par LexBFS est bien un ordre d"élimination simplicial.
A. Duret-LutzThéorie des graphes18 / 31
Implémentation Naïve de LexBFS
On maintient une file de priorité des sommets (ordonnée suivantl"ordre lexicographique de leurs étiquettes) avec un tas :Retirer le sommet maximal coûteO(logn)oùnest la taille du
tas. On fait cette opérationjVjfois pour des tas de plus en plus petits. Pour tous ces retraits on fait donc O(P1k=jVjlogk) =O(log(jVj!)) =O(jVjlogjVj)opérations.Changer l"étiquette d"un sommet dans le tas coûteO(logn). On
fait cet opérations au plusjEjfois sur un tas de taille ou pire jVj, soitO(jEjlogjVj)opérations. La complexité totale est donc de l"ordre deO((jEj+jVj)logjVj). Et encore : ceci néglige le fait que les comparaisons se font entre deux listes, ce qui ajoute un facteurO(jVj)...On peut obtenirO(jEj+jVj)avec une meilleure implémentation.A. Duret-LutzThéorie des graphes19 / 31
ImplémentationO(jEj+jVj)de LexBFS (1/2)
Au lieu d"une files de priorité de sommets (non numérotés), on utilise une liste ordonnée d"ensemble de sommets (non numérotés) de mêmeétiquettes. NotonsS`=fx2Vjx62;etlabel[x] =`g
Initialement, la liste estL= [S[jVj];S[]], l"ensembleS[jVj]contenant la source, et l"ensembleS[]tous les autres états. À chaque étape, on retire un élémentxde l"ensemble en tête deL, puis on raffine les ensembles deLqui contiennentN(x). Si un ensembleS`doit être raffiné, cela signifie qu"il faut créer un ensemble S `iimmédiatement avantS`dans la listeL, et y déplacer certains éléments deS`.S`devra peut-être être effacé s"il est vide. Chaque ensembleS`est représenté par une liste doublement chaînée. Un tableauSET[x]donne une cellule représentantxdans la liste doublement chaînée de l"ensembleS`contenantx, ainsi qu"un pointeur vers la position représentantS`dans la listeL.A. Duret-LutzThéorie des graphes20 / 31ImplémentationO(jEj+jVj)de LexBFS (2/2)cfb
a de65[5;4][5;4][4][4]SETabcdef
L S [5;4]S [4]S [5;4]S [4]cfb a de65[5;4;3]4
[4;3][4;3]SETabcdef L S [5;4;3]S [4;3]S [5;4;3]S [4;3]A. Duret-LutzThéorie des graphes21 / 31Reconnaissance des graphes cordaux
Théorème
Un gr apheest co rdalsi et seu lementsi un o rdreconstruit par LexBFS est un ordre d"élimination simplicial.ComplexitéOn sait construire un ordre avec LexBFS enO(jEj+jVj).La vérification que cet ordre est simplicial peut se faire avec la
même complexité.La complexité finale est doncO(jEj+jVj).
Plus de détails dans "Algorithmic graph theory and perfect graphs" (Martin Charles Golumbic).A. Duret-LutzThéorie des graphes22 / 31
Calcul d"un diamètre avec LexBFS
Théorème
Deux pa rcoursLe xBFSp ermettentde calcul erle diamètre d"un arbre, et d"approcher à un près le diamètre d"un graphe cordal.Principe
On lance un p remierLexBFS qui termine sur un sommet u. À partir de ce sommetu, on lance un second LexBFS qui termine sur un sommetv. LexBFS étant un BFS, on peut lors de ce parcours en largeur calculer les distances deuà chaque sommet. On a(G) =dist(u;v)sur les arbres. Sur les graphes cordaux (G) =dist(u;v)ou(G) =dist(u;v) +1.A. Duret-LutzThéorie des graphes23 / 31Coloration d"un graphe cordal (1/2)
La coloration minimale (au sens du nombre de couleurs utilisées) d"un graphe quelconque est un problème NP-complet.L"algorithme glouton
de colo riagevisite un graphe dans un o rdre donné et affecte à chaque sommet la plus petite couleur utilisable. Le nombre de couleur utilisées peut-être différents selon l"ordre.Un ordre
tel que l"algo rithmeglouton donne la colo rationminimale existe toujours; mais il n"est pas forcément facile à trouver.Un ordre parfait
est un o rdredes sommets tel que les colo riage effectué par l"algorithme glouton soit minimal pourGet tous ses sous-graphes.Les graphes parfaitement ordonnençable
sont les graphes p ourles quels un ordre parfait existe.Les graphes cordaux
sont pa rfaitemento rdonnençables!Il suffit de choisir l"ordre inverse d"un ordre d"élimination simplicial : c"est-à-dire en fait l"ordre dans lequel LexBFS découvre les états.A. Duret-LutzThéorie des graphes24 / 31
Coloration d"un graphe cordal (2/2)
GreedyColor(G= (V;E),)
Entrée : un grapheG, un ordre sur les sommets
Sortie : un tableau de couleursCindicé par les noeuds pour toute couleurn:Avail(n) 1 pour tout sommetxpris dans l"ordre: pour tout voisiny2N(x)déjà colorié :Avail(C(y)) 0
i 0 // La boucle suivante fait moins de 1+jN(x)jitérations répéteri i+1 jusqu"à ce queAvail(i) =1C(x) i
pour tout voisiny2N(x)déjà colorié :Avail(C(y)) 1
retournerC O(jVj+jEj)opérations.A. Duret-LutzThéorie des graphes25 / 31Graphes d"intervalles
SoitI1;I2;:::;Inun ensemble d"intervalles deR. NotonsG= (V;E) le grapheV=fv1;v2;:::;vnget(vi;vj)2E()Ii\Ij6=; représentant les intersections de ces intervalles.I 1I 2I 3I 4v 1v 2v 3v4Un graphe est un graphe d"intervalles si et seulement si il existe un
ensemble d"intervalles deRqui le réalise (au sens ci-dessus).A. Duret-LutzThéorie des graphes26 / 31