Úloha na tento týden

Tento semestr budeme společně řešit problémy z knihy pana Lovásze: Combinatorial problems and exercises. Na konci jednoho semináře si řekneme zadání, na začátku příštího někdo, kdo problém vyřešil, řekne řešení. Tady na webu se kromě zadání dočtete i malou nápovědu.

1) Když je S nějaká množina vrcholů grafu G, tak každé dobré k-obarvení G vytvoří nějaký rozklad S na třídy ekvivalence. Pro dané k a S vyrobte graf, aby možné rozklady byly právě (a) rozklad na jednobodové množiny (to je jednoduché) (b) všechny rozklady, kromě toho v (a).

(c) triviální rozklad {S} (d) všechny rozklady, kromě toho v (c).

2) Rovinný graf má stejný počet koster jako jeho duál. Nápověda