Graf, cykl, pelny czy regularny, V(G), E(G)

Revoltbent · Post autor: **Revoltbent** » 14 mar 2015, o 13:05

: AU; ggiDCWFA7Rc.jpg (13.43 KiB) Przejrzano 93 razy

Czy graf zadany rysunkiem jest :
a) hamiltonowski ? znajdż cykl
b) jest grafem pełnym / regularnym ?
c) określ V(G), E(G) i \(\displaystyle{ \varphi}\)
d) sprawdż tw. \(\displaystyle{ \sum_{V \in V(G)}^{} deg(v)=2 E(G)}\)
e) Znajdż \(\displaystyle{ \left\{ D_{k}\left( G\right)\right\}^{ \infty }_{k=0}}\)

miodzio1988 · Post autor: **miodzio1988** » 14 mar 2015, o 13:06

Ok, jakies proby /propozycje?

Revoltbent · Post autor: **Revoltbent** » 14 mar 2015, o 13:41

E(G) krawędzi - tutaj ich 12, V(G) wierzchołki -ich 7 nie widzę tego cyklu żeby wracal w te same miejsce, graf jest nie pełny tyłko regularny, może to i łatwo, ale muszę to zrozumieć

miodzio1988 · Post autor: **miodzio1988** » 14 mar 2015, o 13:48

Nie jest pełny i nie jest regularny.

Dlaczego nie ma cyklu Hamiltona? Udowodnij to

Revoltbent · Post autor: **Revoltbent** » 14 mar 2015, o 14:25

bo nie spelnia warunek deg(u) + deg(v) > n dla każdej pary wierzcholkóow u, v które nie są polączone krawędzią

miodzio1988 · Post autor: **miodzio1988** » 14 mar 2015, o 14:56

ok, dzialaj dalej

bakala12 · Post autor: **bakala12** » 14 mar 2015, o 22:54

bo nie spelnia warunek deg(u) + deg(v) > n dla każdej pary wierzcholkóow u, v które nie są polączone krawędzią

To żaden dowód, to tylko warunek dostateczny. Jeżeli nie jest spełniony warunek dostateczny to cykl Hamiltona może istnieć.

L1ke · Post autor: **L1ke** » 19 mar 2015, o 17:57

musi byc przejscie przynajmniej 1 raz przez każdy wierzcholek