Matematické Fórum

Jak to říkáš, tak je to správně. Pokud jich je více vstupních uzlů můžeš vybrat kterýkoli. Žádně větší záludnost by být neměla.

Grundi: Bereš uzly v sestupném pořadí jejich acyklického číslování. Vždy se podíváš do všech uzlů, do kterých vede hrana a Grundiho funkce bude nejmenší nepoužité číslo.

Takže máš uzel který má 2 následníky. Jejich hodnoty jsou 1 a 2 -> uzel bude mít 0 (nejmenší nepoužité z 0, 1, 2...)
Pokud máš uzel, který má 3 následníky a jejich ohodnocení je 0, 1, 2 -> uzel bude mít hodnotu 3

P.S.: Ve skriptech, která používáš na straně 43 jsou to hodnoty uzlů číslo 4 a 2. :-)

Postupuješ odzadu a ten graf je orientovaný. Takže z uzlu 7 žádné hrany nevedou.

Uzel 7 má automaticky nulu. To je dané.
Jdeš po acyklickém číslování zpět - tedy uzel 6. Z uzlu 6 vede pouze hrana do uzlu 7. Ten má nulu... použiješ jedničku.
Znovu dolů po acyklickém číslování - uzel 5. Z uzlu 5 vedou hrany do 6 a 7, které mají hodnoty 0 a 1 > použiješ dvoujku
Uzel 4 - hrany vedou do uzlů 5 a 6, které mají hodnoty 2 a 1 -> můžeš tedy znovu použít nulu
Uzel 3 - jedna hrana do uzlu 4, který má hodnotu 0 -> použiješ jedničku
Uzel 2 - hrany do 3, 5, 7 s hodnotami 1, 2, 0 -> použiješ 3
Uzel 1 - hrany do 2, 3, 7 s hodnotami 3, 1, 0 -> použiješ 2

Uf... Takhle už dobrý?

↑ Shelber:
Kvazikomponenta je maximální silně souvislý podgraf. Takže musí existovat orientovaná cesta mezi všemi dvojicemi uzlů v kvazikomponentě. Prostě a jednoduše se dostaneš uvnitř kvazikomponenty odkudkoli kamkoli. To co jsi definoval ty není správně.

Podívej se na následující obrázek:


Na prvním obrázku jsou 3 cykly. To jsou jistě kvazikomponenty, protože se dostaneš z každého uzlu do všech ostatních.

Na kondenzaci je vidět, že prostřední uzel kondenzace je vstupní i výstupní.

V tom obrázku dole je zvýrazněna hrana, která zajišťuje, že se dostaneš mezi všemi uzly 1-6. Tudíž pak se ty 2 kk spojí.

Z toho plyne, že z kvazikomponenta může být vstupní i výstupní uzel kondenzace, pokud to není vůči jednomu uzlu kondenzace najedenou.

Doufám, že jsem ti v tom neudělal ještě větší bordel, než si v tom měl.

↑ Shelber:Ano, přesně tak.

↑ Shelber:
Algoritmus je důkazem věty: Každý orientovaný graf bez cyklů liché délky má jádro.

A důkaz říká: Vezmi výstupní komponentu a v ní sestroj množinu To jsi popsal správně jako takové uzly do nichž vede z náhodně vybraného uzlu sled sudé délky.

Pokud by byl silně souvislý, tak by algoritmus zkončil.

Pokud není silně souvislý (má více kvazikomponent), je dalším krokem algoritmu sestavit nový graf.
A ten se sestaví tak, že z původního grafu vyjmeš celou množinu a všechny uzly, ze kterých vede do hrana.

A celý postup znovu opakuješ od začátku.