Spacery w grafie

[mol_ksiazkowy]

Udowodnić, że można poetykietować wszystkie krawędzie grafu \(\displaystyle{ K_n}\) , gdy \(\displaystyle{ n}\) jest parzyste, liczbami \(\displaystyle{ 1,..., {n \choose 2}}\) tak ,że nie ma ścieżki "etykietowo rosnącej" o więcej niż \(\displaystyle{ n-1}\) krawędziach.

[kerajs]

Wybieram dowolny z wierzchołków i wszystkie wychodzące z niego (i jeszcze nieponumerowane) krawędzie oznaczam najmniejszymi z dostępnych liczb etykiet. Kolejnym etykietowanym wierzchołkiem będzie ten do którego prowadzi krawędź o największej etykiecie. I tu także wszystkie wychodzące z niego (i jeszcze nieponumerowane) krawędzie oznaczam najmniejszymi z dostępnych liczb etykiet. Procedurę powtarzam aż do poetykietowania kliki.

Przy takiej numeracji krawędzi najdłuższa ścieżka powiela wybór wierzchołków do eltykietowania i składa się z n-1 odcinków.

[arek1357]

Kolejnym etykietowanym wierzchołkiem będzie ten do którego prowadzi krawędź o największej etykiecie.

Wydaje mi się, że to nie będzie działać sprawdzałem dla \(\displaystyle{ n=4}\), ale jakby słowo największy zamienił na najmniejszy to pewnie by zadziałało..

[mol_ksiazkowy]

Przy takiej numeracji krawędzi najdłuższa ścieżka powiela wybór wierzchołków do eltykietowania i składa się z n-1 odcinków.

Gdzie wykorzystano parzystość ...?

[arek1357]

no nigdzie

Dodano po 1 dniu 23 godzinach 33 minutach 11 sekundach:
Próbowałem konstruować ścieżki rosnące w grafach pełnych o ilości wierzchołków:

\(\displaystyle{ n=4,5,6,7}\)

W każdym raczej udało mi się skonstruować ścieżkę rosnącą nie dłuższą niż \(\displaystyle{ n-1}\) krawędzi

Robię to mniej więcej tak:

Wybieram krawędź nr. \(\displaystyle{ 1}\) raczej dowolnie. Potem wybieram dowolny z dwóch wierzchołków sąsiadujących z tą krawędzią i numeruję krawędzie wychodzące z tego wierzchołka ale dla np. \(\displaystyle{ n=5}\) mamy wszystkich krawędzi: \(\displaystyle{ 1,2,3,4,5,6,7,8,9,10}\)

Wybieram: \(\displaystyle{ 4,7,10}\),(dla \(\displaystyle{ n=6}\) biorę nie co trzeci tylko co czwarty, itd...) potem wybieram największą etykietę \(\displaystyle{ (10)}\) i wszystkie sąsiadujące z nią jeszcze nieponumerowane krawędzie numeruję najmniejszymi numerami, które zostały, czyli: \(\displaystyle{ 2,3}\), potem biorę najmniejszą etykietę czyli dwójkę i dopasowuję do niej największe jakie zostały czyli: \(\displaystyle{ 8,9}\) i patrzę jeszcze bo pierwszeństwo ma np. wolna krawędź sąsiadująca z jedynką, potem jeszcze do trójki wtłaczam \(\displaystyle{ 5,6 }\) bo te zostały i już nie mam wyboru.

Analogicznie robiłem dla \(\displaystyle{ n=4,6}\)


Nie zauważyłem potrzeby dzielenia na parzyste i nieparzyste dla \(\displaystyle{ n>3}\) , dla \(\displaystyle{ n=3}\) owszem jest bo dla \(\displaystyle{ n=3}\) jak wiadomo nie wyjdzie ścieżka rosnąca o długości dwa.