Ścieżka w grafie
- mol_ksiazkowy
- Użytkownik
- Posty: 11367
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3153 razy
- Pomógł: 747 razy
Ścieżka w grafie
Dany jest graf który ma \(\displaystyle{ 100}\) wierzchołków i stopień każdego z nich jest nie mniejszy niż \(\displaystyle{ 10}\). Udowodnić, że w tym grafie istnieje ścieżka, która ma co najmniej \(\displaystyle{ 21}\) wierzchołków.
-
- Użytkownik
- Posty: 157
- Rejestracja: 23 sty 2020, o 16:16
- Płeć: Mężczyzna
- wiek: 30
- Podziękował: 14 razy
- Pomógł: 18 razy
Re: Ścieżka w grafie
Wydaje mi się, że należałoby doprecyzować, co rozumiemy przez ścieżkę i liczbę jej wierzchołków (a może są jakieś dodatkowe założenia dot. grafu? np. spójność). Według mojego rozumienia to stwierdzenie nie jest prawdziwe. Wystarczy rozpatrzeć graf będący "sumą" pięciu 20-wierzchołkowych grafów pełnych, które nie są ze sobą w żaden sposób połączone.
- kerajs
- Użytkownik
- Posty: 8581
- Rejestracja: 17 maja 2013, o 10:23
- Płeć: Mężczyzna
- Podziękował: 307 razy
- Pomógł: 3349 razy
Re: Ścieżka w grafie
Jeśli:
droga - to trasa po różnych wierzchołkach grafu
ścieżka - to trasa po różnych krawędziach grafu (ścieżka prosta - trasa po różnych krawędziach, w której wierzchołki się nie powtarzają )
to założenie o spójności grafu nie jest tu konieczne.
droga - to trasa po różnych wierzchołkach grafu
ścieżka - to trasa po różnych krawędziach grafu (ścieżka prosta - trasa po różnych krawędziach, w której wierzchołki się nie powtarzają )
to założenie o spójności grafu nie jest tu konieczne.
- arek1357
- Użytkownik
- Posty: 5740
- Rejestracja: 6 gru 2006, o 09:18
- Płeć: Mężczyzna
- Lokalizacja: blisko
- Podziękował: 130 razy
- Pomógł: 525 razy
Re: Ścieżka w grafie
Może czegoś nie widzę, ale jeżeli taki graf podzielimy na pięć spójnych składowych nie mających połączeń, każda składowa będzie zawierać 20 wierzchołków, oczywiście mogą to być pełne kliki nawet więc każdy wierzchołek będzie miał wagę minimum 10, ale każda ścieżka będzie więc
zawierać maksimum 20 punktów a nie 21...
zawierać maksimum 20 punktów a nie 21...
-
- Użytkownik
- Posty: 157
- Rejestracja: 23 sty 2020, o 16:16
- Płeć: Mężczyzna
- wiek: 30
- Podziękował: 14 razy
- Pomógł: 18 razy
Re: Ścieżka w grafie
Myślę, że tutaj przez liczbę wierzchołków ścieżki (bez powtarzających się krawędzi) rozumie się długość ścieżki (liczbę jej krawędzi) powiększoną o jeden. Jeśli nie zakładać, że krawędzie się nie powtarzają, to wystarczy dowolny graf z jedną krawędzią i można robić dowolnie "dużą" ścieżkę w tym znaczeniu. Czy ktoś mógłby dać jakąś wskazówkę? Problem mnie zaciekawił i próbowałem z kilkoma pomysłami, ale nic sensownego mi się nie udało...