Teoretická otázka - popsat algoritmus na nalezení největšího párování v grafu.
Příklad - Najděte uzavřený tvar exponenciální vytvořující funkce
, kde
je počet perfektních párování v úplném grafu
na
vrcholech.
Protože jsem příklad nevyřešila, dal mi druhý příklad: Nechť
jsou rovnoběžné přímky v rovině. Množina V jsou úsečky spojující body mezi přímkami
(koncové body různých úseček jsou různé). Množina hran je taková, že mezi dvěma úsečkami vede hrana, právě když se protínají. Dokažte, že graf s množinou vrcholů V a s popsanou množinou hran je perfektní graf.
Náznak řešení: Buď jde využít Dilworthovu větu, nebo lze nalézt rozlehlou nezávislou množinu ( v každém podgrafu G). Postup pro nalezení rozlehlé nezávislé množiny je například: v pořadí v jakém jsou koncové body úseček na jedné přímce vždy přidám první vrchol do množiny a smažu všechny úsečky incidentní s touto úsečkou. A to opakuji.
Teoretická otázka - popsat algoritmus na nalezení největšího párování v grafu.
Příklad - Najděte uzavřený tvar exponenciální vytvořující funkce [latex]\Sigma_{n \geq 0} p_n {x^n \over n!}[/latex], kde [latex]p_n[/latex] je počet perfektních párování v úplném grafu [latex]K_n[/latex] na [latex]n[/latex] vrcholech.
Protože jsem příklad nevyřešila, dal mi druhý příklad: Nechť [latex]p_1, p_2[/latex] jsou rovnoběžné přímky v rovině. Množina V jsou úsečky spojující body mezi přímkami [latex]p_1, p_2[/latex] (koncové body různých úseček jsou různé). Množina hran je taková, že mezi dvěma úsečkami vede hrana, právě když se protínají. Dokažte, že graf s množinou vrcholů V a s popsanou množinou hran je perfektní graf.
Náznak řešení: Buď jde využít Dilworthovu větu, nebo lze nalézt rozlehlou nezávislou množinu ( v každém podgrafu G). Postup pro nalezení rozlehlé nezávislé množiny je například: v pořadí v jakém jsou koncové body úseček na jedné přímce vždy přidám první vrchol do množiny a smažu všechny úsečky incidentní s touto úsečkou. A to opakuji.