szukanie zaawansowane
 [ Posty: 1 ] 
Autor Wiadomość
Kobieta Offline
 Tytuł: graf - rysunek
PostNapisane: 7 sty 2017, o 17:44 
Użytkownik

Posty: 4
Lokalizacja: Kraków, Polska
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

Obrazek

1. Planarny - ze wzoru Eulera 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?
Obrazek
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 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 : Obrazek
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: degA _{4}  \neq   degB_{3}
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 1 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Problem Casanovy Graf Znajomości  Avicularia  4
 Graf i liczba jego ścian  michalalex132  4
 Graf doskonaly.  RobiMethod  1
 Graf nieskierowany - zadanie 3  kasia00  1
 Zbadań czy graf jest grafem doskonałym  Oleszko12  0
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl