Fórum studentů MFF UK

Skoro až zahanbujúce ... thnks

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

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