Matematické Fórum

A nemas nahodou potuchu, jak se ten algoritmus jmenuje? Ja jsem se ted kdysi ucil algoritms na nalezeni maximalniho parovani, no, neni to zadna legrace....

Nestačilo by rozšířit definici vylepšující střídavé cesty tak, že buď se pomocí ní zvětší počet hran v párování nebo se sníží jeho cena? (jen nápad, ale takhle z hlavy nevidím protipříklad :) ). To by asi šlo ukázat, že když máme dvě maximální párování který se liší v nějakých hranách, tak jde z jednoho ke druhýmu přejít pomocí nějakých střídavých cest a každou má cenu použít, jen když to zlevní ...

↑ Lukee:

Zdravím :-)

Zde kniha v rustine http://books.prometey.org/read.php/djvu=14696 od str. 114 (dvoustrana) nebo 215 originálu pojednává o činskem pošťákovi.

Autorem knihy je N. Christophides nebo Christofides? (snad jsem to moz nezkomolila) - třeba pohledat v jine reci http://en.wikipedia.org/wiki/Christofides_algorithm

http://www.itl.nist.gov/div897/sqg/dads … stman.html - zde se mi to zda čitelné.

zde můj horor - překlad popisu algoritmu (pořadné označení je v original textu),

vaha je asi "ohodnocení", řetězec asi "cesta" a ještě jsou odkazy na jine kapitoly:

čast 5.2.1

Krok 1. Necht matice c_ij vah hran grafu G. S použitím algoritmu nejkratšeho řetezce (viz kapitola 8) vytvoříme |X| x |X| matici D = d_ij, kde d_ij váha řetezce minimalní vahy, jdoucí z některého vrcholu x_i na další vrchol x_j

Krok 2. Najdeme takove řetezové parování M pro množinu X, které dává minimální vahu (v souladu s matici vah D). Efektivně toto jde udělát dle algoritmu minimálního parování dle kapitoly 12.

Krok 3. Pokud vrchol x_a se kombinuje (shoduje??) s dalším vrcholem x_b, pak určeny řetez je minimální vahy, odpovídající váze v kroku 1. Doplnimě uměle hranu v G odpovídající hrany z a provedeme to pro každý další řetez z množiny M, vysledkem je s-graf G (M)

Krok 4. Součet vah všech hran grafu G nalezeny pomoci matice M (za vahu umělé hrany se povazuje vaha ji rovnoběžné reální hrany) se rovna minimalni vaze cyklu, který prochází po G. Zároveň počet obchodu cyklu po hraně se rovna celkovému poctu rovnoběžných hran mezi x_i, x_j v G M.

Po tomto výkonu prohlásit, že mám složenou zkoušku z "Úvodu do teorie grafu" - to mohu rovnou podat prihlasku o titul ing. Kacanovou.

Ale pokud budu nejak napomocna (jen z prekladem) - staci dat vedet.

Ať se daří :-)

↑ Lukee:

v Kapitole 12 ruské knihy je toho velmi moc - to se nevyznám, to by muselo být řečeno, od kterého řádku se to má překládat: - myslím, že to je odstavec 3.1 v kapitole 12 na str. 391 originalu

Zde v kapitole 13 na zaver str. 80. http://www.uai.fme.vutbr.cz/~mseda/TG03_MS.pdf vypráví, jak se dá změnit maximální na minimální.

http://www.cs.vsb.cz/ochodkova/courses/gra/gal5.pdf - také mluví o maďarských cestách, jako v ruske variante.

Asi víc nebudu nápomocna, maximálně s nějakým překladem, pokud bude konkrétně řečeno - ale dnes už ne.

Zdravím :-)

↑ jelena:
Teď nevím, jestli tobě došel ten email ode mě :-). Doufám, že ano. Kdyby ne, tak tvůj email mi přišel (Díky!), ale koukal jsem se na něj až dnes -- měl jsem na plánu programování až dneska. Nakonec jsem se na to vykašlal a použil jsem obyčejné maximální párování, stejně jsem asi jediný člověk, co to alespoň nějak má :-). Ty ostatní algoritmy byly příliš složité :-(.