Grafy eulerowskie i hamiltonowskie
: 28 sie 2013, o 20:23
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ć?
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ć?