[MIX] Zestaw zadań na sezon ogórkowy II
: 17 lip 2011, o 17:29
autor: Inkwizytor
Odp. na pyt. do 12
Albo bardziej trywialnie i mniej wysublimowanie:
Ukryta treść:
W łamanej wierzchołków stopnia nieparzystego może być tylko dwa lub zero. Mamy 12 wierzchołków stopnia 3 w kratownicy. Mamy 5 łamanych. W NAJLEPSZYM PRZYPADKU każda łamana pokryje DWA wierzchołki stopnia 3. Czyli W NAJLEPSZYM PRZYPADKU dla 5 łamanych uda się pokryć 10 wierzchołków stopnia 3. Oczywiście może być ich łacznie mniej. No to jeśli nie wszystkie wierzchołki zostają pokryte w kwadratowej kratownicy za pomocą 5 łamanych, to znaczy że nie istnieje takie pokrycie. Szczerze pisząc nie do końca rozumiem gdzie tu wątpliwość?mol_ksiazkowy pisze:ad 12 cdWydaje mi sie ze mamy tu warunek na to iz graf jest eulerowski lub połeulerowski (semieulerowski).Przez łamaną rozumiem ścieżkę "typu eulerowskiego", która może być zamknięta, posiadać nawet dwa cykle (w łamanej o długości 8) i jako podgraf może mieć ona albo 0 albo 2 wierzchołki stopnia nieparzystego. Krótko mówiać daną łamaną da się narysować przechodząc przez każdą krawędź dokładnie raz
ale jak z tego wynika teza ... ?
np łamana ponizej obłsuguje tylko jeden wierzcholek stopnia 3,
Ukryta treść:
Każda łamana ma 2 lub 0 wierzchołków stopnia nieparzystego (0 wierzchołków w przypadku pętli). 5 łamanych jest w stanie pokryć graf mający co najwyżej 10 wierzchołków stopnia nieparzystego (co najwyżej, gdyz mogą się zdarzyć sytuacje, w których przykładowo jedna łamana kończy w wierzchołku stopnia 2, a druga łamana się w nim zaczyna). Kratownica kwadratowa ma 12 wierzchołków stopnia nieparzystego (wszystkie stopnia 3). Zatem nie da się przy użyciu 5 łamanych pokryć całej kratownicy