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 Offline

Tytuł: Cykl hamiltona w grafie

Napisane: 7 sie 2015, o 15:29

Posty: 394
Lokalizacja: Warszawa

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 2018

Góra

Medea 2 Offline

Tytuł: Cykl hamiltona w grafie

Napisane: 7 sie 2015, o 20:27

Posty: 2505

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

Góra

gardner Offline

Tytuł: Cykl hamiltona w grafie

Napisane: 8 sie 2015, o 11:08

Posty: 394
Lokalizacja: Warszawa

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
Skojarzenia w grafie, minimalizacja sumy długości karawędzi.	e715489	0
[Teoria grafów] Ilość krawędzi w grafie planarnym	matinf	4
Droga prosta a spójność w grafie	silvaran	0
graf k-refularny a istnienie cyklu hamiltona	karl153	2
Cykl Hamiltona i obwód Eulera	Student_matmy	2

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