Graf półhamiltonowski

uczen23 · Post autor: **uczen23** » 25 cze 2018, o 19:54

Dla jakich \(\displaystyle{ m}\) i \(\displaystyle{ n}\) graf dwudzielny \(\displaystyle{ K_{m,n}}\) jest półhamiltonowski?

leg14 · Post autor: **leg14** » 25 cze 2018, o 19:59

Wskazówka: każda krawędź jest równoważna parze \(\displaystyle{ (v,u)}\) gdzie \(\displaystyle{ u \in U;v \in V}\)
i \(\displaystyle{ |U| = m;|V|=n}\)

uczen23 · Post autor: **uczen23** » 26 cze 2018, o 09:36

Czyli krawędzi jest \(\displaystyle{ |E|= \frac{m \cdot n}{2}}\)

i co to daje?

leg14 · Post autor: **leg14** » 26 cze 2018, o 09:43

Spróbuj stworzyć ścieżkę Hamiltonowską w \(\displaystyle{ K_{2,10}}\)

uczen23 · Post autor: **uczen23** » 26 cze 2018, o 09:53

nie można. jak coś to chodzi o grafy proste, bez pętelek i podwójnych krawędzi.

Graf:

Ukryta treść:

leg14 · Post autor: **leg14** » 26 cze 2018, o 10:10

No jasne , ze nie mozna. A rzucilo Ci sie w oczy dlaczego tak jest w tym konkretnym przypadku?

uczen23 · Post autor: **uczen23** » 26 cze 2018, o 10:14

tak, gdyż trzeba będzie przechodzić kilka razy przez wierzchołki 10 stopnia.

Tak na logikę (zauważyłem przy rysowaniu)to moim zdaniem chyba to będzie spełnione jeśli \(\displaystyle{ m=n}\) przynajmniej dla pierwszych \(\displaystyle{ m,n=1,2,3,4}\)

leg14 · Post autor: **leg14** » 26 cze 2018, o 10:17

Tak na logikę (zauważyłem przy rysowaniu)to moim zdaniem chyba to będzie spełnione jeśli

No prawie prawie (ale jeszcze jest jedna możliwość) - popatrz jeszcze na \(\displaystyle{ K_{1,2}}\) .
jak popatrzysz i poprawisz minimalnie to co napisałeś, to zajmij się udowodnieniem, że w pozostałych przypadkach graf nie jest półHamiltonowski.

Całe rozumowanie zasadza się na takiej obserwacji:
bierzemy taką ścieżkę Hamiltona i ją orientujemy (czyli zamieniamy krawędzie na strzałki), czyli jeśli miałeś krawędź:
\(\displaystyle{ 1-----2 ------3}\) to teraz robisz z niej \(\displaystyle{ 1---->2---->3----->}\) (tak by strzałki szły w "zgodną" stronę).
Skoro \(\displaystyle{ K_{m,n}}\) jest dwudzielny to zawsze koniec strzałki będzie w \(\displaystyle{ V}\), a początek w \(\displaystyle{ U}\) i każdy wierzchołek jest początkiem lub końcem strzałki.

Matematyka.pl