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}$ ??

Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2019

Góra

Medea 2 Offline

Tytuł: Cykl hamiltona w grafie

Napisane: 7 sie 2015, o 19:27

Posty: 2491

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
Turniej a ścieżka Hamiltona	Rudis	4
Dowód na istnienie grafu Hamiltona.	karpiuch	7
Cykl hamiltona w grafie o 6 wierzchołkach	Anonymous	4
Cykl Hamiltona gdy go byc nie powinno	filip.wroc	4
cykle w grafie 2-spójnym	forever17	0

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