Router les circulations planaires

De
Publié par

Router les circulations planaires Guyslain Naves 5–6 novembre 2009 G-SCOP, Universite Joseph Fourier, Grenoble

  • guyslain naves

  • loi de conservation

  • circulations planaires

  • multiflot entier


Publié le : mardi 19 juin 2012
Lecture(s) : 11
Source : lirmm.fr
Nombre de pages : 26
Voir plus Voir moins
Router
les
circulations
Guyslain Naves
5–6 novembre 2009
G-SCOP,Universite´JosephFourier,Grenoble
planaires
lFtoesMtultiotsrPbo`lme(euMtlfigxuedH,GV,sehparienttelontieSor)e´icND.eixedlrV(G)(H)G+H)c:E(ecCdleycseenlembumnu-itlnetsdecunefois,actementtcnaHtxeistnrees)((ec}|P)E(eP|P{|=)e(f:euqlet(h)(}|=cE(P)P|e{|Ph(=))Gf)e(EH))hE(
(e
E(P)}| ≤c(e)
e
|
Probl`eme(Flotice´nois))d(
Soient G un graphe, s,tV(G), c:E(G)NiderD´ec. l’existence d’un multi-ensemblePde(s,t)-chemins tel que
:
E(G))
P
|P |=k
|{P
E(Hh)(h|=c((P)}
∈ C
|{P
e
|
|
e
|{P
∈ C
E(G)h)
Proble`me(Flotd(ice´onsi))
E(P)}|=c(h)
(e
))
Soient G un graphe, hE(G), c:E(G)N´D.redice l’existence d’un multi-ensembleCde cycles tel que :
E(P)}| ≤c(e)
is,telquentunefoP{Pe|E:e(f)e|=(ee)(GE)}(Pc(|PP{Ee|(f))|=)hlFtootssetMultiPorlbN.D´+H):E(G(G)c)HV,s(Vpaehxurgde,HtGenoi)SertinetolfitluM(eme`HexactemrsectantlcsenietlbCeedyc-etiemnsuedulnmsixecnetdicelre
FlotsteuM
Probl`eme(Flotecd´())noisi
tlitos
Soient G un graphe, hE(G), c:E(G)Nedre´icD. l’existence d’un multi-ensembleCde cycles tel que :
|{P∈ C |eE(P)}| ≤c(e) (eE(G)h) |{P∈ C |eE(P)}|=c(h)
Probl`eme(Multiflot entier)
Soient G, graphes, VH deux(H)V(G)c:E(G+H)N. D´eciderlexistencedunmulti-ensembleCde cycles intersectant H exactement une fois, tel que :
f(e) =|{P |∈ PeE(P)}| ≤c(e) (eE(G)) f(h) =|{P∈ P |eE(P)}|=c(h) (hE(H))
L
Pour un cycleC:
oideconserv
χC(δ+(v))χC(δ(v)) = 0
Pour un flot :
f(δ+(v))f(δ(v)) = 0
taoin
(vV(G))
(vV(G))
De´nition f:E(G)Nunecestesecierv´fisGednoitalucri ´equations.
Th´eor`eme(Fulkerson) Il existe un(s,t)-flot de valeur k dans G ssi il existe une circulation f de G avec f(h) =k .
rPobl`emedujour
Proble`me(Multiflot dans les circulations) Multiotdanslecasou`lacapacit´ecestunecirculationde G+H .
Remarque : Si|E(H)|ep,cblroatuln)ioenuscrico(1nadttesme`e= constant, il existe toujours un flot. Si|E(H)|= 2, il est polynomial (Nash-Williams, Frank). Si|E(H)| ≥,cestNP-completm,eˆemvace3Gacyclique (Vygen).
CasGplanai
Th´eor`eme(Pfeier,Marx)
recacyiluqe
Si G est planaire acyclique,multiflot dans les circulationsest NP-complet
The´ore`me(IbarakietNagamochi)
Si G est planaire acyclique, que toutes les origines des arcs de demandesontsurleborddunemˆemefacedeGetquilexiste unbonordred´eliminationdessommets,multiflot dans les circulationsest polynomial.
R´seutlta
The´ore`me Si G est planaire acyclique, et|H|x´e,etsmultiflot dans les circulationsest pseudopolynomial.
Preuve : D´ecroiserleschemins, ´ Etudierlastructuredeschemins(ind´ependantdeG), Router localement en chaque sommet.
D
Croise´s. D´ecroisement:deux
ce´ro
chemins
si
se
ement
Pas
croisent
au
croises. ´
plus
une
fois.
D
Crois´es. D´ecroisement:deux
ce´ro
chemins
si
se
ement
Pas
croisent
au
croise´s.
plus
une
fois.
Plus exactement :
D´ceriosement
Proposition S’il existe une solution, il existe une solution telle que, si deux cheminssontcrois´es,ilssecroisentuniquementenleur premier sommet commun, et leurs terminaux sont distincts.
Preuve :arroecD´tsenemissdeschemuccessifniiaospnni,setmr d´ecroissancelexicographiquedesnombresdecroisementen chaque sommet.
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.