Grafy eulerowskie i hamiltonowskie

[Darkwing Duck]

Cześć.


Mam kilka zadań i chciałbym się zapytać o tok mojego rozumowania.

1. Podaj warunek konieczny i wystarczający, aby graf trójdzielny pełny \(\displaystyle{ K_{p,q,r}}\) był:

a) eulerowski

Wystarczy, aby miał wszystkie stopnie wierzchołków parzyste.

b) hamiltonowski

Tutaj nie jestem pewny, ale wydaje mi się, że musi być spełniona nierówność \(\displaystyle{ p+q \ge r}\) , gdzie \(\displaystyle{ r \ge p \wedge r \ge q}\) Czy może ktoś to potwierdzić?

2. Dany jest graf \(\displaystyle{ G = (V,E), gdzie V = \left\{\left\{ i,j \right\} : i, j \in \left\{1,2,3,4,5\right\}\right\}}\),

przy czym

\(\displaystyle{ uv \in E \Leftrightarrow u \cap v =}\) zbiór pusty.


Udownodnij, że jest izomorficzny z grafem Petersena.

Nie potrafię narysować tego grafu, tzn. wychodzi mi graf pełny na 5 wierzchołkach, który nijak nie jest izomorficzny z grafem Petersena. (A może jest?)

3. Niech \(\displaystyle{ G}\) będzie grafem rzędu \(\displaystyle{ \ge 3}\). Udowodnij indukcyjnie, że jeśli \(\displaystyle{ \left| G \right| \ge}\) podłoga( \(\displaystyle{ \frac{n^{2}}{4} + 1}\)) to w grafie istnieje podgraf \(\displaystyle{ K_{3}}\) .

Podaj przykład grafu rzędu \(\displaystyle{ n \ge 3}\) mającego podłoga \(\displaystyle{ \frac{ n^{2} }{4}}\) krawędzi, który nie zawiera \(\displaystyle{ K_{3}}\)


Udało mi się dojść, że graf K3 to cykl C3. I że sąsiednie wierchołki nie moga na pewno się łączyć z tymi samym wierzchołkami. Wiem też, że czym więcej wierzchołków, tym krawędzie rosną z kwadratem i że " coraz trudniej" jest znaleźć takie przykłady krawędzi, które by nie łączyła jednego wierzchołka z sąsiednimi do siebie wierzchołkami. Ktoś moze to potwierdzić?

[kolegasafeta]

Jeżeli chodzi o ten warunek na to, żeby był eulerowski, to musi być jeszcze spójny na dodatek
Jeżeli chodzi o hamiltonowskie, to nie ma warunku "wtedy i tylko wtedy". Polecam książkę Wilsona o grafach, tam wszystko jest. Książka jest dostępna w wielu popularnych miejscach internetu.

[Darkwing Duck]

Ale treść zadania to Ty czytaj - chodzi o graf pełny trójdzielny (szczególny przypadek grafu).

[kolegasafeta]

Sorry