planárny separátor preprocessing pls help

Základní přednáška o teorii složitosti algoritmů. Zhruba první polovina přednášky je věnována studiu složitosti konkrétních algoritmů různých typů (grafové, rozděl a panuj, hladové na matroidech) pracujících v polynomiálním čase. Složitost je zkoumána jak "klasicky" (složitost v nejhorším případě), tak amortizovaně. Druhá polovina přednášky je pak věnována studiu třídy NP, polynomiální převoditelnosti problémů a důkazům NP-úplnosti problémů. Závěr přednášky je věnován tématům souvisejícím se studiem NP-úplnosti: pseudopolynomiálním algoritmům a silné NP-úplnosti, početním úlohám a třídě #P.
kaktus64
Matfyz(ák|ačka) level I
Příspěvky: 22
Registrován: 3. 6. 2008 10:42
Typ studia: Informatika Mgr.

planárny separátor preprocessing pls help

Příspěvek od kaktus64 »

V záverečnej časti preprocessingu pri tvorbe separátora rozdelíme vrcholy grafu na množiny C, D, E plus dve vrstvy z BFS, ktoré ich separujú. Vieme, že:

|C| < n/2 (dané voľbou n/2-ého vrcholu do "prostrednej" vrstvy)
|E| < n/2 (dtto)

potom je tam, že ak |D| <= 2/3n sme hotový, ak nie, riešime ináč...
Ja akosi nevidím prečo sme hotový. Píše sa tam, že v tomto prípade do jednej množiny (A) zvolíme najväčšiu množinu z C,D,E. Do druhej množiny (B) zvyšné dve a ako separátor (S) oné dve vrstvy. |S| <= 2*sqrt(n) to je ok. A teraz použitím odhadov, ktoré máme:

buď
jedna množina |A| = |D| <= 2/3n
druhá množina |B| = |C| + |E| <= n/2 + n/2 = n

alebo
jedna množina |A| = |C| <= n/2
druhá množina |B| = |D| + |E| <= 2/3n + n/2 = viac ako n

tretí prípad je symetrický. Pri všetkých prerozdeleniach teda získam aspoň jednu množinu "väčšiu" ako 2/3n. Je mi jasné, že toľko vrcholov tam nie je, takže nech si to medzi sebou rozdelia akokoľvek, bude to sedieť, ale nevidím v tom to zdôvodnenie, prečo v prípade |D| <= 2/3n budú tie množiny fakt obe menšie ako 2/3n

ak tomu niekto rozumiete pls help :?
OT

Re: planárny separátor preprocessing pls help

Příspěvek od OT »

Prečo sme v prípade, že |D| <= 2/3n hotoví?

Ako A si zvolíme najväčšiu množinu z C, D, E...
a ako B si zvolíme zvyšok. Separátor budú pritom tvoriť vrstvy L_v a L_w.

Otázka prečo sa nikdy nemôže stať, že |A| > 2/3n alebo |B| > 2/3n je na mieste, ale odpoveď na ňu je jednoduchá:
Ak máme tri množiny (C, D, E), z ktorých si vezmeme najväčšiu, tak tá najväčšia z nich musí mať veľkosť aspoň 1/3 z celku (|C| + |D| + |E|), inak by nebola najväčšia. Teda zvyšné dve dokopy musia mať veľkosť nanajvýš 2/3 celku...

A to je celé, ako by povedal pán Čepek :)
kaktus64
Matfyz(ák|ačka) level I
Příspěvky: 22
Registrován: 3. 6. 2008 10:42
Typ studia: Informatika Mgr.

Re: planárny separátor preprocessing pls help

Příspěvek od kaktus64 »

Skoro až zahanbujúce ... :shock: :D thnks
Odpovědět

Zpět na „TIN062 Složitost I“