Matematické Fórum

Začal bych tím, co je vlastně hranová/uzlová souvislost? Respektive hranový/uzlový řez.

Hranový řez (mezi dvěma uzly třeba a ) je množina hran taková, že každá cesta z do má alespoň jednu hranu v .  A navíc, žádná vlastní podmnožina tuto vlastnost nesplňuje.

Zjednodušeně lidsky řečeno, je to množina hran, které musíš odstranit, aby se graf rozpadl a zároveň uzly x a y byly v různých komponentách. Navíc s touhle vlastností minimální.

V matici je na pozici i,j nejmenší počet těch hran, které musíš odstranit, aby se graf rozpadl a i a j byly v jiných komponentách (tzv. hranový stupeň souvislosti mezi dvěma uzly).

Takže v tom tvém případě, mezi uzly 4 a 5 je to jednoduché -> odstraníš jednu hranu a máš rozpadnuto.

Když bys chtěl "odříznout" 2 od 4, musíš uříznout 3 hrany.

atd...

Uzlová souvislost je analogií. Jen je "problém" v případě sousedních prvků. V případě, že jsou uzly sousední je uzlový stupeň roven

↑ Shelber:
Chápeš to správně.

Pokud máš dva uzly, které jsou sousední tak nikdy nemůžeš odstraněním nějakých uzlů dosáhnout toho aby byly v různých komponentách - kvůli té hraně která je spojuje. Proto se definuje tenhle případ "speciálně".

A ještě slovíčkaření na konec: a jsou dvě rozdílný věci. Vzhledem k tomu, že moje vyjádření bylo taky trochu vágní je to samozřejmě jedno, ale jestli je váš profesor puntíčkář, jak jsem četl v nějakém Tvém příspěvku, tak jenom doplňuji.

↑ Shelber:
Stupeň uzlu je počet hran, které ten uzel obsahuje. Minimální stupeň grafu je potom nejmenší ze všech stupňů uzlů. V tomhle případě mají všechny uzly stupeň 4 nebo 5 (snad jsem se nepřekoukl). Tudíž minimální stupeň grafu je 4.

co se týče hranového/uzlového stupně souvislosti grafu tak jak říkáš, můžeš si vytvořit matice a vybrat nejmenší prvky.

Nicméně, celá matice je zbytečně "velká věc". Lidsky řečeno, musíš najít nejmenší řez (hranový/uzlový) který ti rozdělí ten graf na komponenty. Nepotřebuješ to zjišťovat mezi všemi dvojicemi. Ty grafy většinou bývají konstruovány tak, aby to bylo snadné.

V tomhle případě když bys to "rozřízl" uprostřed (odstranil ty hrany, které tvoří jakési Z) tak dostaneš dvě komponenty. Takže si uděláš takovýhle "odhad" a pak už se jenom zamyslíš, jestli to může být i menší? Tedy jestli by ti stačilo odstranit 2 hrany aby se ten graf rozpadl. Jelikož ty dvě "půlky" grafu jsou "skoro" úplné grafy, tak nejspíš ne.

Uzlový řez je podobný. Zvolíš si uzlový řez velikosti 2, ten snad vidíš. A zeptáš se sám sebe "je možné mít menší řez?" tedy řez velikosti 1?  No, evidentně ne.

Pokud to v tom grafu nevidíš, můžeš udělat i matice, ale v tomhle případě je to matice o 10x10 a to není málo. Ikdyž jsou ty matice symetrické a diagonálu neřešíš i tak ti zbývá 45 prvků. Takže ani polynom nemusí být pro člověka dostatečně rychlý.

Mimochodem, daleko "zajímavější" je ten druhý graf z těch skript.

↑ Shelber:
Hranově disjunktní cesty jsou takové, které prostě nevedou přes stejné hrany. Představ si graf na obrázku...

mezi u a v existuje několik cest, jak vidíš (např.: u,2,...5,8,v). Ale nejsou hranově disjunktní, protože nakonec vždycky použiješ hranu (8,v). Tudíž je zde jenom jedna hranově disjunktní cesta. A je zde krásně vidět, že mezi uzly u a v je graf 1 souvislý, protože stačí odebrat jednu hranu a stane se nesouvislým.

Význam těchto vět je především v jejich důkazu. Důkazy obou vět totiž ukazují algoritmy, jakým převést problém k-souvislosti na problém toků. V tom je velká síla především v otázce příslušnosti k třídám složitosti. Z toho všeho nakonec totiž plyne, že k-souvislost náleží P. Díky převodu na toky, které jsou polynomiální. Na to se Ryjáček ptá ;)

EDIT: Teď na to tak koukám, nevysvětlil jsem to úplně ideálně. Takže doplním trošku lepší definici těch disjunktních cest: Dvě cesty p1 a p2 jsou hranově disjunktní, pokud žádná hrana není ZÁROVEŇ v p1 i p2. Takhle se mě to líbí víc ;) Ale pořád je to snad user-friendly.

↑ Shelber:
Ano.

Jestli jdeš v úterý tak se tam potkáme :-) Na co se zaměřit, to je těžký no, hlavně vědět co je P, NP a NPC. Jinak samozřejmě FF můžeš využít jako argument pro ten původní příklad.

↑ Shelber:
Na pochopení nejlepší ty skripta. Pěkný shrnutí jsou ty materiály z Dropboxu, jestli máš. Jeslti ne, napiš a pošlu.

↑ Shelber:
Tak o ničem takovým nevím. Ale napiš, když nebudeš něco vědět a já se pokusím. Nebo někdo jiný tady.

Jop. Asi bych raději než FF napsal Edmonds-Karpův, ale to už je asi jedno. Důležité je to, že si to převedl na tok.