Ścieżka w grafie

[mol_ksiazkowy]

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.

[FasolkaBernoulliego]

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]

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.

[arek1357]

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...

[FasolkaBernoulliego]

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...

[arek1357]

Właśnie więc każdy może rozumieć inaczej...