Konstrukce lineárního nakreslení grafu v O(n)

[hippies]

Na slajdu 29 je, ze to umime v linearnim case, ale ja vubec netusim jak, muze me nekdo nakopnout, nebo to je neco co mam brat jako fakt?

[twoflower]

Ja bych to bral jako fakt. To je ta vec, o ktere Cepek rikal, ze jeji dukaz trva Koubkovi na nejake prednasce pul semestru

[hippies]

doufal jsem v to, ale na te prednasce (ani jedne) jsem bohuzel nebyl:) .. kazdopadne diky

[Lukas Mach]

Ja bych to bral jako fakt. To je ta vec, o ktere Cepek rikal, ze jeji dukaz trva Koubkovi na nejake prednasce pul semestru

Mimochodem, Martin Mares ma relativne kratky O(n) algoritmus v posledni kapitole skripticek na prednasku grafovych algoritmu: http://mj.ucw.cz/vyuka/ga/

[twoflower]

Ja bych to bral jako fakt. To je ta vec, o ktere Cepek rikal, ze jeji dukaz trva Koubkovi na nejake prednasce pul semestru

Mimochodem, Martin Mares ma relativne kratky O(n) algoritmus v posledni kapitole skripticek na prednasku grafovych algoritmu: http://mj.ucw.cz/vyuka/ga/

Aha, to bude asi to zjednoduseni, ktere nejaky clovek na prednasce zminoval. Ted jsem jen pro zajimavost kouknul do Mehlhorna a tam je ten dukaz na 9 stranek a to jeste zda se vyuziva nektera fakta z testovani rovinnosti, ktere je tam taky tak na 10 stranek (resp. dukaz toho, ze lze v O(n)).