[PDF] Parcours de graphes Mar 28 2011 Parcours en

View - Download Parcours de graphes

Previous PDF

Next PDF

Parcours G´en´erique

Parcours en largeur

Parcours en profondeur

Autres parcours

Applications aux graphes triangul´es

Parcours de graphes

Michel Habib

MPRI 2009

28 mars 2011

Michel HabibMPRI 2009Parcours de graphes

Parcours G´en´erique

Parcours en largeur

Parcours en profondeur

Autres parcours

Applications aux graphes triangul´es

Plan

1Parcours G´en´erique

2Parcours en largeur

BFS classique

LexBFS

3Parcours en profondeur

DFS classique

DFS lexicographique

4Autres parcours

Parcours selon le voisinage maximal MNS

Maximal Cardinality Search

5Applications aux graphes triangul´es

Les parcours *

Michel HabibMPRI 2009Parcours de graphes

Parcours G´en´erique

Parcours en largeur

Parcours en profondeur

Autres parcours

Applications aux graphes triangul´es

1Parcours G´en´erique

2Parcours en largeur

BFS classique

LexBFS

3Parcours en profondeur

DFS classique

DFS lexicographique

4Autres parcours

Parcours selon le voisinage maximal MNS

Maximal Cardinality Search

5Applications aux graphes triangul´es

Les parcours *

Michel HabibMPRI 2009Parcours de graphes

Parcours G´en´erique

Parcours en largeur

Parcours en profondeur

Autres parcours

Applications aux graphes triangul´es

Le probl`eme

´Etant donn´e un grapheG= (V,E) (non-orient´e), explorer l"ensemble des sommetsGen "traversant" les arˆetes du graphe.

R´esultat

Un arbre de parcours

Un ordre total sur les sommets du graphe

Questions

`A quelle condition un ordreσsur les sommets correspond `a un parcours? Quelles sont les propri´et´es de ces ordres?

Michel HabibMPRI 2009Parcours de graphes

Parcours G´en´erique

Parcours en largeur

Parcours en profondeur

Autres parcours

Applications aux graphes triangul´es

R´ef´erence principale :

Ces questions simples n"ont ´et´e pos´ees que tr`es r´ecemment : D.G. Corneil et R. M. Krueger, A unified view of graph searching, SIAM J. Discrete Math, 22, N°4 (2008) 1259-1276

Michel HabibMPRI 2009Parcours de graphes

Parcours G´en´erique

Parcours en largeur

Parcours en profondeur

Autres parcours

Applications aux graphes triangul´es

7 1 2 34
56

Invariant

`A chaque ´etape, on s´electionne une arˆete entre un sommet visit´e et un non-visit´e

Michel HabibMPRI 2009Parcours de graphes

Parcours G´en´erique

Parcours en largeur

Parcours en profondeur

Autres parcours

Applications aux graphes triangul´es

Parcours g´en´erique

S← {s}

pouri←1`anfaire

Extraire un sommet non-num´erot´evdeS

σ(i)←v

pour chaquesommet non-num´erot´e w?N(v)faire

S←S? {w}

Michel HabibMPRI 2009Parcours de graphes

Parcours G´en´erique

Parcours en largeur

Parcours en profondeur

Autres parcours

Applications aux graphes triangul´es

Question?

Soienta,betctrois sommets tels queab/?Eetac?E.

acb `A quelle condition est-il possible de visiterapuisbpuisc?

Michel HabibMPRI 2009Parcours de graphes

Parcours G´en´erique

Parcours en largeur

Parcours en profondeur

Autres parcours

Applications aux graphes triangul´es

Propri´et´e (Gen)

´Etant donn´e un ordreσsurV, siaTh´eor`eme Pour un grapheG= (V,E), un ordreσsurVest un parcours de

Gssiσv´erifie la propri´et´e (Gen).

Michel HabibMPRI 2009Parcours de graphes

Parcours G´en´erique

Parcours en largeur

Parcours en profondeur

Autres parcours

Applications aux graphes triangul´esBFS classiqueLexBFS

1Parcours G´en´erique

2Parcours en largeur

BFS classique

LexBFS

3Parcours en profondeur

DFS classique

DFS lexicographique

4Autres parcours

Parcours selon le voisinage maximal MNS

Maximal Cardinality Search

5Applications aux graphes triangul´es

Les parcours *

Michel HabibMPRI 2009Parcours de graphes

Parcours G´en´erique

Parcours en largeur

Parcours en profondeur

Autres parcours

Applications aux graphes triangul´esBFS classique

LexBFS

Parcours en largeur (BFS)

Donn´ees: Un grapheG= (V,E) et un sommet sources

R´esultat: Un ordre totalσdeV

Initialiser la fileS`as

pouri←1`anfaire

Extraire le sommetvde la tˆete de lafileS

σ(i)←v

pour chaquesommet non-num´erot´e w?N(v)faire siw n"est pas dans Salors

Ajouterwen fin de la fileS

Michel HabibMPRI 2009Parcours de graphes

Parcours G´en´erique

Parcours en largeur

Parcours en profondeur

Autres parcours

Applications aux graphes triangul´esBFS classique

LexBFS

Propri´et´e (B)

´Etant donn´e un ordreσsurV, siaTh´eor`eme Pour un grapheG= (V,E), un ordreσsurVest un parcours BFS deGssiσv´erifie la propri´et´e (B).

Michel HabibMPRI 2009Parcours de graphes

Parcours G´en´erique

Parcours en largeur

Parcours en profondeur

Autres parcours

Applications aux graphes triangul´esBFS classique

LexBFS

Applications

Distances `a la source

Soientσun BFS deG`a partir desetx,y2 sommets tels que d(s,x)Evaluation du diam`etre [CDK"03] SiGne contient pas de cycle sans corde de longueur sup´erieure ou ´egale `ak, alors BFS permet de trouver un sommetxtel que ecc(x)≥Diam(G)- ?k/2?.

Michel HabibMPRI 2009Parcours de graphes

Parcours G´en´erique

Parcours en largeur

Parcours en profondeur

Autres parcours

Applications aux graphes triangul´esBFS classique

LexBFS

Graphe triangul´e

Un graphe est triangul´e ssi tout cycle de longueur≥4 poss`ede une corde. 5

14386 7 2

Diam`etre [CDK"03]

Sivest le dernier sommet d"un ordre BFS sur un graphe triangul´e

G, alorsecc(v)≥Diam(G)-1.

Michel HabibMPRI 2009Parcours de graphes

Parcours G´en´erique

Parcours en largeur

Parcours en profondeur

Autres parcours

Applications aux graphes triangul´esBFS classique

LexBFS

Graphes d"intervalles

Un graphe est un graphe d"intervalles ssi c"est le graphe d"intersection d"une famille d"intervalles sur la droite r´eelle. 3 76

5423 811 7

8 5642

Diam`etre [Corneil, Dragan, Kho¨eler 2003]

Sivest le dernier sommet d"un ordre BFS sur un graphe d"intervallesG, alorsecc(v)≥Diam(G)-1. Il est possible de trouver dans la derni`ere couche, un sommet vtel queecc(v) =Diam(G)

Michel HabibMPRI 2009Parcours de graphes

Parcours G´en´erique

Parcours en largeur

Parcours en profondeur

Autres parcours

Applications aux graphes triangul´esBFS classique

LexBFS

Parcours en largeur lexicographique (LexBFS)

Donn´ees: Un grapheG= (V,E) et un sommet sources

R´esultat: Un ordre totalσdeV

Affecter l"´etiquette∅`a chaque sommet

label(s)← {n} pouri←n`a1faire Choisir un sommetvd"´etiquette lexicographique max.

σ(i)←v

pour chaquesommet non-num´erot´e w?N(v)faire label(w)←label(w).{i}

Michel HabibMPRI 2009Parcours de graphes

Parcours G´en´erique

Parcours en largeur

Parcours en profondeur

Autres parcours

Applications aux graphes triangul´esBFS classique

LexBFS

1 765
43
2

Michel HabibMPRI 2009Parcours de graphes

Parcours G´en´erique

Parcours en largeur

Parcours en profondeur

Autres parcours

Applications aux graphes triangul´esBFS classique

LexBFS

Propri´et´e (LexB)

´Etant donn´e un ordreσsurV, siaTh´eor`eme Pour un graphG= (V,E), un ordreσsurVest un parcours LexBFS deGssiσv´erifie la propri´et´e (LexB).

Michel HabibMPRI 2009Parcours de graphes

Parcours G´en´erique

Parcours en largeur

Parcours en profondeur

Autres parcours

Applications aux graphes triangul´esBFS classique

LexBFS

Orientation transitive

Graphe de comparabilit´e et orientation transitive Un graphe est de comparabilit´e ssi ses arˆetes peuvent ˆetre orient´ees transitivement.

LexBFS [Habib, McConnel, Paul, Viennot 1998

Le dernier sommet d"un LexBFS r´ealis´e sur le compl´ementaire d"un graphe de comparabilit´eGpeut-ˆetre pris comme une sourced"une orientation transitive deG.

Michel HabibMPRI 2009Parcours de graphes

Parcours G´en´erique

Parcours en largeur

Parcours en profondeur

Autres parcours

Applications aux graphes triangul´esBFS classique

LexBFS

Extension lin´eaire

Un grapheGest de comparabilit´e ssi il existe un ordre surVtel que pout tout tripletaTh´eor`eme : D.G. Corneil SiGest de comparabilit´e, alors il existe un ordre LexBFS qui est une extension lin´eaire.

Probl`eme

Comment calculer efficacement cet ordre LexBFS particulier?

Michel HabibMPRI 2009Parcours de graphes

Parcours G´en´erique

Parcours en largeur

Parcours en profondeur

Autres parcours

Applications aux graphes triangul´es

DFS classique

DFS lexicographique

Parcours en profondeur (DFS)

Donn´ees: Un grapheG= (V,E) et un sommet sources

R´esultat: Un ordre totalσdeV

Initialiser la pileS`as

pouri←1`anfaire

Extraire le sommetvdu haut de lapileS

σ(i)←v

pour chaquesommet non-num´erot´e w?N(v)faire siw n"est pas dans Salors

Ajouterwen haut de la pileS

Michel HabibMPRI 2009Parcours de graphes

Parcours G´en´erique

Parcours en largeur

Parcours en profondeur

Autres parcours

Applications aux graphes triangul´es

DFS classique

DFS lexicographique

Propri´et´e (D)

´Etant donn´e un ordreσsurV, siaTh´eor`eme Pour un grapheG= (V,E), un ordreσsurVest un parcours DFS deGssiσv´erifie la propri´et´e (D).

Michel HabibMPRI 2009Parcours de graphes

Parcours G´en´erique

Parcours en largeur

Parcours en profondeur

Autres parcours

Applications aux graphes triangul´es

DFS classique

DFS lexicographique

Quelques exemples d"application

Test de planarit´e (utilisation d"un DFS pour placer les arˆetes autour de l"arbre associ´e au parcours). Composantes 2-connexes (resp. composantes fortement connexes dans le cas des graphes orient´es). Tri topologique (extension lin´eaire) des graphes sans circuits, applications aux m´echanismes d"h´eritage. ...

LexDFS

Peut-on d´efinir un parcours en profondeur lexicographique?

Michel HabibMPRI 2009Parcours de graphes

Parcours G´en´erique

Parcours en largeur

Parcours en profondeur

Autres parcours

Applications aux graphes triangul´es

DFS classique

DFS lexicographique

1Parcours G´en´erique

2Parcours en largeur

BFS classique

LexBFS

3Parcours en profondeur

DFS classique

DFS lexicographique

4Autres parcours

Parcours selon le voisinage maximal MNS

Maximal Cardinality Search

5Applications aux graphes triangul´es

Les parcours *

Michel HabibMPRI 2009Parcours de graphes

Parcours G´en´erique

Parcours en largeur

Parcours en profondeur

Autres parcours

Applications aux graphes triangul´es

DFS classique

DFS lexicographique

BFS vs LexBFS

BFS dcba

LexBFS

dcba

DFS vs LexDFS

DFS dcba

LexDFS

dcba

Michel HabibMPRI 2009Parcours de graphes

Parcours G´en´erique

Parcours en largeur

Parcours en profondeur

Autres parcours

Applications aux graphes triangul´es

DFS classique

DFS lexicographique

Propri´et´e (LD)

´Etant donn´e un ordreσsurV, siaTh´eor`eme Pour un grapheG= (V,E), un ordreσsurVest un parcours LexDFS deGssiσv´erifie la propri´et´e (LD).

Michel HabibMPRI 2009Parcours de graphes

Parcours G´en´erique

Parcours en largeur

Parcours en profondeur

Autres parcours

Applications aux graphes triangul´es

DFS classique

DFS lexicographique

LexDFS

Parcours en profondeur lexicographique (LexDFS)

Donn´ees: Un grapheG= (V,E) et un sommet sources

R´esultat: Un ordre totalσdeV

Affecter l"´etiquette∅`a chaque sommet

label(s)← {1} pouri←1`anfaire Choisir un sommetvd"´etiquettelexicographique max.

σ(i)←v

pour chaquesommet non-num´erot´e w?N(v)faire label(w)← {i}.label(w)

Michel HabibMPRI 2009Parcours de graphes

Parcours G´en´erique

Parcours en largeur

Parcours en profondeur

Autres parcours

Applications aux graphes triangul´es

DFS classique

DFS lexicographique

LexDFS

Complexit´e

Peut-on impl´ementer LexDFS enO(n+m)?

Krueger et Spinrad 2008

Il est possible d"impl´ementer LexDFS enO(n+mloglogn) en utilisant des arbres de Van der Boas.

Applications D. Corneil, M.H. 2009

On peut calculer l"existence d"une chaˆıne hamiltonienne sur un graphe de cocomparabilit´e en utilisant LexDFS.

Michel HabibMPRI 2009Parcours de graphes

Parcours G´en´erique

Parcours en largeur

Parcours en profondeur

Autres parcours

Applications aux graphes triangul´es

DFS classique

DFS lexicographique

Pourquoi LexDFS n"est pas trivialement lin´eaire `A partir deP={X1,X2,...Xk}partition ordonn´ee en k parties et d"un ensemble pivotSet il faut obtenir enO(|S|) : la partition ordonn´eequotesdbs_dbs44.pdfusesText_44

[PDF] fiche revision decolonisation

[PDF] parcours en profondeur d'un graphe en c

[PDF] théorie des graphes python

[PDF] parcours en largeur graphe

[PDF] parcours en profondeur itératif

[PDF] algorithme parcours en profondeur python

[PDF] parcours en largeur graphe java

[PDF] conflit de puissance définition

[PDF] parcours lecture acces pas cher

[PDF] parcours lecture pdf

[PDF] parcours lecture le petit chaperon rouge

[PDF] parcours lecture acces avis

[PDF] parcours lecture occasion

[PDF] coexistence pacifique cours

[PDF] archives militaire en ligne