graf - rysunek

[madnessadness]

Proszę o pomoc z narysowaniem grafu o 9 wierzchołkach i 15 krawędziach, który będzie: planarny (płaski), jednokreslny, dwudzielny i półhamiltonowski jednocześnie.Nie mam pomysłu jak taki graf narysować.. Jak podzielę go na dwa zbiory wierzchołków i łącze je tak, żeby się nie przecinały krawędzie to mam tylko 8 krawędzi i ni jak dodać kolejną żeby został planarny.Czy taki graf jest możliwy do narysowania?-- 11 sty 2017, o 17:05 --Wróciłam do zadania i po czasie udało mi się narysować graf, który chyba spełnia podane wyżej warunki. Bardzo proszę o sprawdzenie czy jest poprawny i czy spełnia jeszcze dodatkowe własności, które wypiszę niżej. Rysunek



1. Planarny - ze wzoru Eulera \(\displaystyle{ E\le 3 \cdot V - 6, 15\le 3 \cdot 9 - 6, 15\le 21}\)
2. półhamiltonowski - ma ścieżkę Hamiltona, ale nie Hamiltona, bo nie posiada cyklu?

3. Jednokreślny - B-E--A-E-C-I-D-G-A-I-B-H-D-E-C-G
4. Dwudzielny - dwa zbiory wierzchołków \(\displaystyle{ V_{1} = \left\{A,B,C,D \right\} V _{2}=\left\{ E,F,G,H,I\right\}}\)

Czy jest/istnieje:

A. Droga jednobieżna czyli droga Eulera? taka sama jak w punkcie 3?
B. Graf płaski - niestety, ale nie potrafię go narysować
C. Zbiory wierzchołków dla dwóch rozłącznych antyklik: czyli takie jak w punkcie 4?
D. Drzewo rozpinające :

AU

29w07bk.jpg (15.25 KiB) Przejrzano 50 razy

E. Liczba chromatyczna = 7
F. Graf Eulera nie, bo nie ma cyklu Eulera (jest tylko ścieżka)
G.Regularny - nie, bo wierzchołki mają różne stopnie: \(\displaystyle{ degA _{4} \neq degB_{3}}\)