Strona główna Matematyka.pl » Matematyka - królowa nauk » Probabilistyka » Kombinatoryka i matematyka dyskretna

Cykl hamiltona w grafie

Strona 1 z 1

[ Posty: 3 ]

Autor

Wiadomość

gardner

Tytuł: Cykl hamiltona w grafie

Napisane: 7 sie 2015, o 14:29

Mam takie zadanie:
Dla każdej liczby naturalnej $k$ istnieje graf o spójności $k$ , bez cyklu Hamiltona.

Trzeba wychodzić od tego,że dla każdej takiej liczby istnieje graf zawierający podgraf będący podpodziałem grafu $K_{5}$ i $K_{3,3}$ ??

Góra

Medea 2 Offline

Tytuł: Cykl hamiltona w grafie

Napisane: 7 sie 2015, o 19:27

Posty: 2505

Te dwa grafy mają wiele wspólnego z planarnością, a nie spójnością. Mylę się?

Góra

gardner

Tytuł: Cykl hamiltona w grafie

Napisane: 8 sie 2015, o 10:08

Jasne,robiłem dopiero co zadanie z planarnością i z rozpędu wpisałem.

Znalazłem warunek konieczny na obecność cyklu hamiltona:
Jeżeli graf $G$ jest hamiltonowski to dla każdego niepustego podzbioru $V^{'}$ zbioru wierzchołków $V(G)$ zachodzi
$\omega (V(G)\ -\ V')\le |V'|$
gdzie $\omega (G)$ oznacza liczbę spójnych składowych grafu $G$ .

Góra

Poprzedni | Następny

	Strona 1 z 1	[ Posty: 3 ]

Strona główna Matematyka.pl » Matematyka - królowa nauk » Probabilistyka » Kombinatoryka i matematyka dyskretna

Zobacz podobne tematy
Tytuł tematu	Autor	Odpowiedzi
Liczba krawędzi w grafie dwudzielnym	PabloG	1
liczba cykli długości 4 w grafie G	JakubCh	0
Najkrótsza droga w grafie	wojciech007	1
Ilość krawędzi w grafie	mCichy13	4
Liczba dróg w grafie.	Albatross201	13

[Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]