Udowodnić, że jeśli w grafie dowolny wierzchołek ma stopień \(\displaystyle{ r}\), to w tym grafie jest cykl \(\displaystyle{ r+1}\) elementowySpecjalny cykl
-
mol_ksiazkowy
- Użytkownik
- Posty: 11415
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3155 razy
- Pomógł: 748 razy
Specjalny cykl
Udowodnić, że jeśli w grafie dowolny wierzchołek ma stopień \(\displaystyle{ r}\), to w tym grafie jest cykl \(\displaystyle{ r+1}\) elementowy-
arek1357
- Użytkownik
- Posty: 5749
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Specjalny cykl
Kwadrat bez przekątnych każdy wierzchołek ma stopień \(\displaystyle{ 2}\) a cykl jest tylko jeden o długości cztery...(więc nie trzy)
-
mol_ksiazkowy
- Użytkownik
- Posty: 11415
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3155 razy
- Pomógł: 748 razy
-
arek1357
- Użytkownik
- Posty: 5749
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 131 razy
- Pomógł: 526 razy
Re: Specjalny cykl
teraz ok
Dodano po 41 minutach 47 sekundach:
Więc na pewno istnieje ścieżka o długości co najmniej \(\displaystyle{ r}\):
\(\displaystyle{ v_{1}-v_{2}-v_{3}-...-v_{r}}\)
Bo jeżeliby taka nie istniała to oznaczałoby , że ostatni wierzchołek ma mniej niż \(\displaystyle{ r}\) sąsiadów...
Skoro istnieje ścieżka zawierająca \(\displaystyle{ r}\) wierzchołków , więc musi istnieć ścieżka zawierająca wszystkich sąsiadów jakiegoś wierzchołka \(\displaystyle{ v}\), odwiedza \(\displaystyle{ r}\) sąsiadów wierzchołka \(\displaystyle{ v}\) więc razem z wierzchołkiem \(\displaystyle{ v}\) ścieżka ta staje się cyklem o długości \(\displaystyle{ r+1}\)...cnd...
Dodano po 41 minutach 47 sekundach:
Więc na pewno istnieje ścieżka o długości co najmniej \(\displaystyle{ r}\):
\(\displaystyle{ v_{1}-v_{2}-v_{3}-...-v_{r}}\)
Bo jeżeliby taka nie istniała to oznaczałoby , że ostatni wierzchołek ma mniej niż \(\displaystyle{ r}\) sąsiadów...
Skoro istnieje ścieżka zawierająca \(\displaystyle{ r}\) wierzchołków , więc musi istnieć ścieżka zawierająca wszystkich sąsiadów jakiegoś wierzchołka \(\displaystyle{ v}\), odwiedza \(\displaystyle{ r}\) sąsiadów wierzchołka \(\displaystyle{ v}\) więc razem z wierzchołkiem \(\displaystyle{ v}\) ścieżka ta staje się cyklem o długości \(\displaystyle{ r+1}\)...cnd...
-
janusz47
- Użytkownik
- Posty: 7918
- Rejestracja: 18 mar 2009, o 16:24
- Płeć: Mężczyzna
- Podziękował: 30 razy
- Pomógł: 1671 razy
Re: Specjalny cykl
Kod: Zaznacz cały
https://wazniak.mimuw.edu.pl/index.php?title=Matematyka_dyskretna_1/%C4%86wiczenia_12:_Grafy