graf hamiltonowski i jego skojarzenie

danielek12201220 · Post autor: **danielek12201220** » 24 mar 2017, o 20:02

zakladamy ze \(\displaystyle{ G}\) jest grafem dwudzielnym \(\displaystyle{ G=(X,Y,E)}\) oraz \(\displaystyle{ 1 \le |X| \le |Y|}\)

wykaz ze jesli \(\displaystyle{ G}\) jest hamiltonowski to ma pelne skojarzenie

Mruczek · Post autor: **Mruczek** » 25 mar 2017, o 13:29

No to jak jest hamiltonowski to znaczy, że ma cykl Hamiltona (cykl przechodzący przez każdy wierzchołek grafu). Graf jest dwudzielny, więc każdy jego cykl ma parzystą długość. Bierzemy co drugą krawędź z tego cyklu Hamiltona i dostajemy pełne skojarzenie (widać, że każdy wierzchołek jest w tym skojarzeniu).

danielek12201220 · Post autor: **danielek12201220** » 25 mar 2017, o 22:58

hmm wiem wiem, ale jak to zapisac tak poprawnie ? zeby na kolokwium bylo tak przejrzyscie ? bo ja tak samo uwazam , tylko kwestia zapisu ?