Ile najwięcej krawędzi można dodać do grafu cyklicznego \(\displaystyle{ C _{n}}\), tak aby w powstałym grafie G, krawędzie \(\displaystyle{ C_{n}}\) pozostały jedynym cyklem hamiltonowskim?
Zadanie nie jest z żadnego zbioru, więc może się okazać bardzo trudne. Choć na oko nie wydaje się tragiczne, więc może ktoś to zrobi z łatwością.
Ja kombinowałem, że może musi pozostać ileś wierzchołków stopnia 2, ale nic nie wymyśliłem.
Cn - cykle hamiltonowskie
-
xiikzodz
- Użytkownik
- Posty: 1874
- Rejestracja: 4 paź 2008, o 02:13
- Płeć: Kobieta
- Lokalizacja: Lost Hope
- Podziękował: 28 razy
- Pomógł: 502 razy
Cn - cykle hamiltonowskie
(Ostrzegam, że nie znam standardowo stosowanych pojęć.)
Dla każdego n w zupełności wystarczają dwa wierzchołki stopnia 2.
Potrafię podać konstrukcję pozwalającą na dodanie do grafu \(\displaystyle{ C_n}\) tylu krawędzi, że łącznie jest \(\displaystyle{ \frac{7+(-1)^n+2n^2}{8}}\) krawędzi i graf zawiera dokładnie jeden cykl hamiltonowski.
Konstrukcja jest następująca:
numerujemy kolejne wierzchołki cyklu \(\displaystyle{ C_n}\) kolejnymi liczbami 1,2,3,.... Rozważając kolejno wierzchołki o parzystych numerach dodajemy krawędzie łączące te wierzchołki ze wszyskimi o większych numerach. To znaczy wierzchołek o numerze 2 łączymy z wierzchołkami 3,4,5,..., następnie wierzchołek o numerze 4 łączymy z wierzchołkami 5,6,... itd.
Dowód jedyności cyklu Hamiltona przez indukcję.
W ten sposob otrzymujemy dolne ograniczenie na liczbę dodanych krawędzi.
Co do górnego. Niech Niech \(\displaystyle{ C=(v_1,\ldots,v_n)}\) będzie cyklem Hamiltona w pewnym grafie \(\displaystyle{ G}\) o \(\displaystyle{ n}\) wierzchołkach.
Niech \(\displaystyle{ a,b,c,d}\) będą wierzchołkami tego cyklu tak, że po ewentualnym obrocie i/lub odwróceniu kolejności otrzymujemy \(\displaystyle{ C=(b,u_1,\ldots,u_i,c,d,w_1,\ldots,w_j,a)}\). Operacją elementarną nazwiemy zastąpienie cyklu \(\displaystyle{ C}\) cyklem \(\displaystyle{ C'=(c,u_i,\ldots,u_1,b,d,w_1,\ldots,w_j,a)}\), o ile w grafie są krawędzie łączące wierzchołek a z c oraz wierzchołek b z d.
Trzeba sobie narysować. W grafie pełnym o wierzchołkach a,b,c,d cykl (a,b,c,d) przechodzi przy jednek z możliwych operacji elementarnych na cykl (a,c,d,b).
Cykle nazwiemy teraz równoważnymi, jeśli można jeden otrzymać z drugiego stosując obroty, symetrie i opisane powyżej operacje elementarne.
Górne szacowanie na liczbę krawędzi otrzymujemy szacując liczbę krawędzi, które możemy dodać do \(\displaystyle{ C_n}\) tak, by w grafie nie było cyklu równoważnego z \(\displaystyle{ C_n}\). Będzie to jakaś liczba, nazwijmy ją \(\displaystyle{ H(n)}\) rzędu \(\displaystyle{ \mathcal{O}(n^2)}\), dająca się wyznaczyć, ale zabierać się za jej wyznaczanie warto dopiero po rozważeniu następującego problemu:
Czy w dowolnym grafie każde dwa cykle Hamiltona są równoważne?
Nie potrafię na to odpowiedzieć. Gdyby odpowiedź byla twierdząca, wówczas wyznaczając \(\displaystyle{ H(n)}\) otrzymujemy pełną odpowiedź na pytanie w zadaniu.
Dla każdego n w zupełności wystarczają dwa wierzchołki stopnia 2.
Potrafię podać konstrukcję pozwalającą na dodanie do grafu \(\displaystyle{ C_n}\) tylu krawędzi, że łącznie jest \(\displaystyle{ \frac{7+(-1)^n+2n^2}{8}}\) krawędzi i graf zawiera dokładnie jeden cykl hamiltonowski.
Konstrukcja jest następująca:
numerujemy kolejne wierzchołki cyklu \(\displaystyle{ C_n}\) kolejnymi liczbami 1,2,3,.... Rozważając kolejno wierzchołki o parzystych numerach dodajemy krawędzie łączące te wierzchołki ze wszyskimi o większych numerach. To znaczy wierzchołek o numerze 2 łączymy z wierzchołkami 3,4,5,..., następnie wierzchołek o numerze 4 łączymy z wierzchołkami 5,6,... itd.
Dowód jedyności cyklu Hamiltona przez indukcję.
W ten sposob otrzymujemy dolne ograniczenie na liczbę dodanych krawędzi.
Co do górnego. Niech Niech \(\displaystyle{ C=(v_1,\ldots,v_n)}\) będzie cyklem Hamiltona w pewnym grafie \(\displaystyle{ G}\) o \(\displaystyle{ n}\) wierzchołkach.
Niech \(\displaystyle{ a,b,c,d}\) będą wierzchołkami tego cyklu tak, że po ewentualnym obrocie i/lub odwróceniu kolejności otrzymujemy \(\displaystyle{ C=(b,u_1,\ldots,u_i,c,d,w_1,\ldots,w_j,a)}\). Operacją elementarną nazwiemy zastąpienie cyklu \(\displaystyle{ C}\) cyklem \(\displaystyle{ C'=(c,u_i,\ldots,u_1,b,d,w_1,\ldots,w_j,a)}\), o ile w grafie są krawędzie łączące wierzchołek a z c oraz wierzchołek b z d.
Trzeba sobie narysować. W grafie pełnym o wierzchołkach a,b,c,d cykl (a,b,c,d) przechodzi przy jednek z możliwych operacji elementarnych na cykl (a,c,d,b).
Cykle nazwiemy teraz równoważnymi, jeśli można jeden otrzymać z drugiego stosując obroty, symetrie i opisane powyżej operacje elementarne.
Górne szacowanie na liczbę krawędzi otrzymujemy szacując liczbę krawędzi, które możemy dodać do \(\displaystyle{ C_n}\) tak, by w grafie nie było cyklu równoważnego z \(\displaystyle{ C_n}\). Będzie to jakaś liczba, nazwijmy ją \(\displaystyle{ H(n)}\) rzędu \(\displaystyle{ \mathcal{O}(n^2)}\), dająca się wyznaczyć, ale zabierać się za jej wyznaczanie warto dopiero po rozważeniu następującego problemu:
Czy w dowolnym grafie każde dwa cykle Hamiltona są równoważne?
Nie potrafię na to odpowiedzieć. Gdyby odpowiedź byla twierdząca, wówczas wyznaczając \(\displaystyle{ H(n)}\) otrzymujemy pełną odpowiedź na pytanie w zadaniu.
Cn - cykle hamiltonowskie
Dziękuję za poświęcony czas.
Ja zrobiłem to tak, ale to chyba nie jest najlepszy sposób:
Zakładamy, że G(n) ma tylko jeden cykl hamiltonowski \(\displaystyle{ C_{n}=(1,2,3...n)}\)
Jeśli cykl ham. w G(n+1) zawiera krawędzie (1, n+1) oraz (n, n+1) to musi być cyklem \(\displaystyle{ C_{n+1}=(1,2,3...n+1)}\). Inaczej usuwając daną krawędź (k, k+1) graf wciąż miałby cykl ham., a więc i G(n) pozbawione tej krawędzi miałoby taki cykl, który oczywiście nie mógłby być cyklem \(\displaystyle{ C_{n}=(1,2,3...n)}\)
Jeśli usuniemy krawędź (1, n+1) to otrzymujemy wierzchołek o stopniu 1, a więc nie ma tu cyklu ham.
Załóżmy, że istnieje cykl hamiltonowski inny niż \(\displaystyle{ C_{n+1}}\). Musi on wtedy wyglądać tak \(\displaystyle{ (1,n+1,l...n,m...1)}\)
l i m muszą być wierzchołkami o numerach parzystych, gdyż tylko takie (inne niż n i n+1) są połączone z n i n+1. Ponieważ są parzyste, a jedno z nich musi być większe istnieje krawędź (l, m). Istnieją też krawędzie (l, n) i (m, n)
Wtedy możemy w grafie G(n) skonstruować cykl \(\displaystyle{ (1,n...l,m..1)}\), który przechodzi przez wszystkie wierzchołki grafu G(n), ale nie jest tożsamy z \(\displaystyle{ C_{n}}\), gdyż łączą się w nim ze sobą wierzchołki o numerach parzystych. A więc sprzeczność z założeniem indukcyjnym.
Ale strasznie skomplikowany wychodzi ten dowód, ty miałaś na myśli coś prostszego?
Co do cyklów równoważnych trochę nie łapię o co ci chodzi...
Jeśli chodzi o ich homeomorfizm to można podać grafy, gdzie cykle nie są homeomorficzne (że nie są można sprawdzić przyglądając się stopniom wierzchołków)
Jak przeprowadziłaś ten dowód?Dowód jedyności cyklu Hamiltona przez indukcję.
Ja zrobiłem to tak, ale to chyba nie jest najlepszy sposób:
Zakładamy, że G(n) ma tylko jeden cykl hamiltonowski \(\displaystyle{ C_{n}=(1,2,3...n)}\)
Jeśli cykl ham. w G(n+1) zawiera krawędzie (1, n+1) oraz (n, n+1) to musi być cyklem \(\displaystyle{ C_{n+1}=(1,2,3...n+1)}\). Inaczej usuwając daną krawędź (k, k+1) graf wciąż miałby cykl ham., a więc i G(n) pozbawione tej krawędzi miałoby taki cykl, który oczywiście nie mógłby być cyklem \(\displaystyle{ C_{n}=(1,2,3...n)}\)
Jeśli usuniemy krawędź (1, n+1) to otrzymujemy wierzchołek o stopniu 1, a więc nie ma tu cyklu ham.
Załóżmy, że istnieje cykl hamiltonowski inny niż \(\displaystyle{ C_{n+1}}\). Musi on wtedy wyglądać tak \(\displaystyle{ (1,n+1,l...n,m...1)}\)
l i m muszą być wierzchołkami o numerach parzystych, gdyż tylko takie (inne niż n i n+1) są połączone z n i n+1. Ponieważ są parzyste, a jedno z nich musi być większe istnieje krawędź (l, m). Istnieją też krawędzie (l, n) i (m, n)
Wtedy możemy w grafie G(n) skonstruować cykl \(\displaystyle{ (1,n...l,m..1)}\), który przechodzi przez wszystkie wierzchołki grafu G(n), ale nie jest tożsamy z \(\displaystyle{ C_{n}}\), gdyż łączą się w nim ze sobą wierzchołki o numerach parzystych. A więc sprzeczność z założeniem indukcyjnym.
Ale strasznie skomplikowany wychodzi ten dowód, ty miałaś na myśli coś prostszego?
Co do cyklów równoważnych trochę nie łapię o co ci chodzi...
Jeśli chodzi o ich homeomorfizm to można podać grafy, gdzie cykle nie są homeomorficzne (że nie są można sprawdzić przyglądając się stopniom wierzchołków)
Jeśli wziąć pod uwagę operację zmiany kolejności to nawet sam C(n) nie spełnia warunku, bo cykl \(\displaystyle{ (1,2,3...n)}\) jest równoważny z cyklem \(\displaystyle{ (n...3,2,1)}\), czy nie?Górne szacowanie na liczbę krawędzi otrzymujemy szacując liczbę krawędzi, które możemy dodać do C(n) tak, by w grafie nie było cyklu równoważnego z C(n).
-
xiikzodz
- Użytkownik
- Posty: 1874
- Rejestracja: 4 paź 2008, o 02:13
- Płeć: Kobieta
- Lokalizacja: Lost Hope
- Podziękował: 28 razy
- Pomógł: 502 razy
Cn - cykle hamiltonowskie
Dowód jedyności (w zapisie strasznie niewygodny, ale to norma w teorii grafów):
Rozważmy cykl Hamiltona w tak skonstruowanym grafie. Można założyć, że po obróceniu i ew. odbiciu cyklu odpowiednio zaczyna się on od wierzchołka 1 i rozważmy maksymalną część tego cyklu w której kolejne wierzchołki mają kolejne numery: 1,2,3,...,m. Pokażemy, że wówczas m=n. Przypuśćmy, że m<n. Zauważmy, że m+1-wszy wierzchołek ma numer k większy niż m. Jeśli m jest nieparzyste, to k=m+1 i sprzeczność z maksymalnością. Jeśli m jest parzyste wówczas m+1 jest nieparzyste. Rozważmy wierzchołki sąsiadujące w rozważanym cyklu z wierzchołkiem m+1<n (jeśli m+1=n, to dowód zakończony). Z założenia indukcyjnego nie mogą to być 2,3,...,m-1, więc na mocy konstrukcji jednym z sąsiadów musi być wierzchołek m i wobec nieparzystości m+1 droga 1,2,...,m,m+1 należy do cyklu co jest sprzeczne z maksymalnością m.
Intencją było zdanie:
Rozważmy cykl Hamiltona w tak skonstruowanym grafie. Można założyć, że po obróceniu i ew. odbiciu cyklu odpowiednio zaczyna się on od wierzchołka 1 i rozważmy maksymalną część tego cyklu w której kolejne wierzchołki mają kolejne numery: 1,2,3,...,m. Pokażemy, że wówczas m=n. Przypuśćmy, że m<n. Zauważmy, że m+1-wszy wierzchołek ma numer k większy niż m. Jeśli m jest nieparzyste, to k=m+1 i sprzeczność z maksymalnością. Jeśli m jest parzyste wówczas m+1 jest nieparzyste. Rozważmy wierzchołki sąsiadujące w rozważanym cyklu z wierzchołkiem m+1<n (jeśli m+1=n, to dowód zakończony). Z założenia indukcyjnego nie mogą to być 2,3,...,m-1, więc na mocy konstrukcji jednym z sąsiadów musi być wierzchołek m i wobec nieparzystości m+1 droga 1,2,...,m,m+1 należy do cyklu co jest sprzeczne z maksymalnością m.
Intencją było zdanie:
Możesz napisać, co masz na myśli pisząć o cyklach homeomorficznych?Górne szacowanie na liczbę krawędzi otrzymujemy szacując liczbę krawędzi, które możemy dodać do C(n) tak, by w grafie nie było cyklu nierównoważnego z C(n).
Cn - cykle hamiltonowskie
Ok, twój dowód dużo szybszy, choć napisany trochę zawile
Jeśli chodzi o cykle równoważne to trochę nie rozumiem co robi tam operacja elementarna.
Czy to nam nie dodaje cyklów innych niż C(n) jako równoważnych?
Jeśli to celowe to skąd pewność, że nie będzie przeszacowania?
Homeomorfizmy to już nieważne... nagle zacząłem lepiej rozumieć o co ci chodzi w tym pytaniu, na które nie podałaś odpowiedzi. Pomyślę nad tym.
Jeśli chodzi o cykle równoważne to trochę nie rozumiem co robi tam operacja elementarna.
Czy to nam nie dodaje cyklów innych niż C(n) jako równoważnych?
Jeśli to celowe to skąd pewność, że nie będzie przeszacowania?
Homeomorfizmy to już nieważne... nagle zacząłem lepiej rozumieć o co ci chodzi w tym pytaniu, na które nie podałaś odpowiedzi. Pomyślę nad tym.
-
xiikzodz
- Użytkownik
- Posty: 1874
- Rejestracja: 4 paź 2008, o 02:13
- Płeć: Kobieta
- Lokalizacja: Lost Hope
- Podziękował: 28 razy
- Pomógł: 502 razy
Cn - cykle hamiltonowskie
Na przykład w grafie pełnym każdy cykl hamiltona (po ew. odwróceniu i zmianie orientacji) można otrzymać z każdego innego z użyciem ciągu "operacji elementarnych".
Idea jest następująca:
\(\displaystyle{ C_n}\) realizujemy jako wielokąt foremny, który nazwiemy również \(\displaystyle{ C_n}\). Ustalamy jedną z dwóch możliwych orientacji \(\displaystyle{ C_n}\). Wybierzmy teraz dowolne dwa niesąsiednie boki w \(\displaystyle{ C_n}\). Niech to będą, z zachowaniem orientacji \(\displaystyle{ ab}\) oraz \(\displaystyle{ cd}\). Jeśli graf \(\displaystyle{ C_n}\) uzupełnimy o krawędzie \(\displaystyle{ ac}\) oraz \(\displaystyle{ bd}\), to w grafie będzie przynajmniej jeszcze jeden cykl Hamiltona zawierający krawędzie \(\displaystyle{ ac}\) oraz \(\displaystyle{ bd}\) lecz nie zawierający krawędzi \(\displaystyle{ ab}\) i \(\displaystyle{ cd}\). Hipoteza jest taka, że jeśli uzupełniony graf \(\displaystyle{ C_n}\) ma przynajmniej dwa cykle, to znajdziemy w nim takie wierzchołki \(\displaystyle{ a,b,c,d}\).
Idea jest następująca:
\(\displaystyle{ C_n}\) realizujemy jako wielokąt foremny, który nazwiemy również \(\displaystyle{ C_n}\). Ustalamy jedną z dwóch możliwych orientacji \(\displaystyle{ C_n}\). Wybierzmy teraz dowolne dwa niesąsiednie boki w \(\displaystyle{ C_n}\). Niech to będą, z zachowaniem orientacji \(\displaystyle{ ab}\) oraz \(\displaystyle{ cd}\). Jeśli graf \(\displaystyle{ C_n}\) uzupełnimy o krawędzie \(\displaystyle{ ac}\) oraz \(\displaystyle{ bd}\), to w grafie będzie przynajmniej jeszcze jeden cykl Hamiltona zawierający krawędzie \(\displaystyle{ ac}\) oraz \(\displaystyle{ bd}\) lecz nie zawierający krawędzi \(\displaystyle{ ab}\) i \(\displaystyle{ cd}\). Hipoteza jest taka, że jeśli uzupełniony graf \(\displaystyle{ C_n}\) ma przynajmniej dwa cykle, to znajdziemy w nim takie wierzchołki \(\displaystyle{ a,b,c,d}\).
Cn - cykle hamiltonowskie
Teraz się zorientowałem.
Przecież ta hipoteza jest banalna.
Rozważmy grafy o więcej niż 5 wierzchołkach. Graf ma 2 cykle hamiltonowskie. Więc ma jeden cykl hamiltonowski, nazywamy go (1, 2, 3...). Wierzchołkami a, b, c, d są 1, 2, 4, 5.
Coś pokręciłem, kolosalnie nie zrozumiałem?
A jeśli chodzi o to, czy każdy cykl ham. da się przekształcić operacjami elementarnymi, to czy taki, nie jest kontrprzykładem: C(8) + (1, 5) + (5, 8) + (4, 6)?
Przecież ta hipoteza jest banalna.
Rozważmy grafy o więcej niż 5 wierzchołkach. Graf ma 2 cykle hamiltonowskie. Więc ma jeden cykl hamiltonowski, nazywamy go (1, 2, 3...). Wierzchołkami a, b, c, d są 1, 2, 4, 5.
Coś pokręciłem, kolosalnie nie zrozumiałem?
A jeśli chodzi o to, czy każdy cykl ham. da się przekształcić operacjami elementarnymi, to czy taki, nie jest kontrprzykładem: C(8) + (1, 5) + (5, 8) + (4, 6)?
-
xiikzodz
- Użytkownik
- Posty: 1874
- Rejestracja: 4 paź 2008, o 02:13
- Płeć: Kobieta
- Lokalizacja: Lost Hope
- Podziękował: 28 razy
- Pomógł: 502 razy
Cn - cykle hamiltonowskie
Dobry kontrprzykład, ale jeszcze nie do końca zadowalający, bo homeomorficzny z grafem nie będącym kontrprzykładem (usuwamy 7). W rozważanych przeze mnie sytuacjach graf był zawsze zredukowany do minimalnego homeomorficznego (ze względów raczej oczywistych).A jeśli chodzi o to, czy każdy cykl ham. da się przekształcić operacjami elementarnymi, to czy taki, nie jest kontrprzykładem: C(8) + (1, 5) + (5, 8) + (4, 6)?
Nie potrafię tego połączyć z moją ideą, więc pewnie nie udało mi się jej dobrze sformułować. Mniejsza z tym. Sugeruję poczekać na inne wpisy. U mnie zainteresowanie trwało tyle, ile jazda autobusem na basen i z powrotem. A dodatkowo mam bardzo małą wiedzę z teorii grafów. Na pewno znajdzie się ktoś odpowiedniejszy do udzielania tu wskazówek.Przecież ta hipoteza jest banalna.
Rozważmy grafy o więcej niż 5 wierzchołkach. Graf ma 2 cykle hamiltonowskie. Więc ma jeden cykl hamiltonowski, nazywamy go (1, 2, 3...). Wierzchołkami a, b, c, d są 1, 2, 4, 5.
Coś pokręciłem, kolosalnie nie zrozumiałem?