Dyskusja:Graf hamiltonowski
Z Wikipedii
hamiltonowski jest przymiotnikiem, dlatego hasło powinno się nazywać
Graf hamiltonowski, a nie Graf Hamiltonowski
[edytuj] Nieopisane zależności
W rozdziałach Graf hamiltonowski#Warunek konieczy oraz Graf hamiltonowski#Twierdzenie Oystein Ore (1961) przedstawiono zależności i twierdzenia, które moim zdaniem opisane są w sposób niejasny i niepełny. Umieszczanie informacji, które mogą wprowadzać w błąd ze względu na swoją nieczytelności jest gorsze niż ich brak. Co więcej w angielskiej wersji artykułu twierdzenie Oystein Ore nie jest opisane, bo w roku 1972 sformułowano jego bardziej ogólną wersję – twierdzenie Bondy-Chvátala. Moim zdaniem sporą część polskiego tekstu należy usunąć, a potem artykuł uzupełnić tłumaczeniem. Superborsuk Ω 20:48, 17 kwi 2006 (CEST)
nie no jasne, Twierdzenie Stone'a jest uogólnieniem twierdzenia Weierstrassa - więc po co o tym drugim pisać? przecież to żaden argument!
Rnm 21:13, 17 kwi 2006 (CEST)
Zastanów się czy nie lepiej jest rozbić cały tekst na kilka artykułów. Powiedzmy Twierdzenie Oystein Ore, Twierdzenie Paula Diraca, Twierdzenie o ilości krawędzi, Twierdzenie Bondy-Chvátal. Moim zarzutem w stosunku tekstów, które wprowadzasz, jest ich straszne oderwanie od programistycznego konkretu. Czy możesz się pokusić o jakieś odniesienia do praktyki? A jak to się wszystko ma do Algorytmu A*? Superborsuk Ω 21:55, 17 kwi 2006 (CEST)
a co ma programistyczny konkret do hamiltonowskich grafów? w każdej księdze dot. teorii grafów znajdą się te twierdzenia - i tyle. Odniesienie do praktyki? No ,jeżeli jakiś graf spełnia założenia owych twierdzeń, to nie ma sensu sprawdzać czy jest hamiltonowski (określenie jego drogi to inna sprawa) - tyle. Jezusie, przecież to tekst o grafach hamiltona, teksty które wprowadzam to twierdzenia dot. grafów hamiltona i ich dowody - co do cholery mają te twierdzenia do "programistycznego konkretu"? Praktyka? Znaczy się mam wkleić kod który będzie sprawdzał, czy dany graf nie spełnia tych założeń? Rnm 22:17, 17 kwi 2006 (CEST)
Właśnie w tym tkwi problem. Encyklomedia nie jest wykładem z jakiejś wąskiej dziedziny. To synteza wiedzy. Chcę podkreślić, że doceniam materiały, które umieściłeś w Wikipedii. Tematyka jest trudna i wymaga wiedzy, która jest nieczęsto spotykana. Jednak nie podjąłeś próby wyjaśnienia całego zagadnienia od podstaw, np. nie ma hasła rząd grafu. Superborsuk Ω 22:47, 17 kwi 2006 (CEST)
akurat ten rząd grafu nie jest mój (ja wolę określenie max stopień), to jest problem jak z marszrutami (kwestia nazewnictwa). Synteza wiedzy..... to trzeba odpowiedzieć sobie na pytanie - piszemy dla wszystkich (czy de facto dla nikogo), nie wchodząc w absolutnie żaden temat głębiej (no bo to synteza, nie wąska działka ma być), o ii wojnie światowej też chyba nie ma co pisać, bo trzeba by we wstępie historie ludzkości od starożytnej grecji opisać (bo i tam pewnie znajdą się jakieś wpływy an owe wydarzenia) 83.21.1.223 08:19, 18 kwi 2006 (CEST)
Rnm na Wikipedii, należy założyć, że wszyscy mają dobre chęci. Domyślam się, że kieruje Tobą pragnienie umieszczenia konkretnej wiedzy dla bardzo wąskiej grupy specjalistów. To wielce chwalebna działalność, tym bardziej, że wbijanie zależności matematycznych jest pracochłonne i trzeba znać LaTeX. Jednak, aby Twój wkład został doceniony przez innych, musisz przynajmniej próbować wyjaśnić w bardziej przystępny sposób ideę, która stoi za tymi zależnościami. Prawie każda matematyczna formuła daje się przełożyć na zdanie w języku polskim. Złożone zagadnienia trzeba rozbijać na mniejsze artykuły, żeby czytelnika z miejsca nie wystraszyć. Po co w artykule o grafie hamiltonowskim dowód twierdzenia Twierdzenie Oystein Ore? Jeżeli kogoś to będzie interesować, może kliknąć na link. W tekście głównym wystarczy umieścić wyłącznie samo twierdzenie, a nawet tylko o nim wspomnieć.
Mam też jedno zasadnicze pytanie: Gdybym chciał sprawdzić, czy graf ma ścieżkę Hamiltona, to które z tych twierdzeń powinienem użyć? Ja tej fundamentalnej odpowiedzi w Twoim tekście nie widzę. Brakuje też przykładów. Kod w języku programowania jest niezbędny do analizy, kiedy graf ma setki krawędzi. Jednak najprostsze sytuacje, z grafem 2d składającym się z kilku krawędzi można rozwiązać na kartce. Dzisiejszy tekst robi wrażenie kawałka teorii, którą wykłada ktoś kto nigdy w życiu grafa na oczy nie widział. Chcę podkreślić, że krytykuję twoje edycje na bazie osobistego doświadczenia. Pracowałem nad praktycznymi aplikacjami teorii grafów przez jakiś czas. Czy kiedykolwiek napisałeś jakikolwiek program analizujący graf? Czy możesz rozwiać moje wątpliwości w tym względzie?
Superborsuk Ω 00:10, 19 kwi 2006 (CEST)
rozbicie na drobniejsze arty:
jeżeli ktoś chce "mniej więcej" wiedzieć o co chodzi, wystarczy, że przeczyta hasła scieżka Hamiltona i cykl Hamiltona, zawarte twierdzenia dotyczą stricte grafów hamiltonowskich, poza tym "twierdzeń Diraca" jest trochę więcej i takie podziały szybko stałyby się nienaturalne
"Kod w języku programowania jest niezbędny do analizy, kiedy graf ma setki krawędzi. "- przecież to zupełnie bezsensu, no chyba, że w pseudokodzie lub jakimś wysokopoziomowym (i zapewne wybitnie obiektowym) języku. Czytelnik się wystarszy? No, niezły argument przeciw wszystkim dłuższym tekstom... że już o (niezbędnych) szczegółach implementacji jako wspomaganiu analizy istoty algorytmu nie wspomne
"Prawie każda matematyczna formuła daje się przełożyć na zdanie w języku polskim." - a ja myślałem, że formuła==zdanie, które jest de facto niezależne od języka który ją tylko opisuje ;) - poza tym pytam jeszcze raz - czy w ramach "ogólnodostępności" wiedzy mamy przeprowadzać dowody przez machanie rękami?
Mam też jedno zasadnicze pytanie: Gdybym chciał sprawdzić, czy graf ma ścieżkę Hamiltona, to które z tych twierdzeń powinienem użyć? - nie wiem i mnie to nie obchodzi - ja dostarczam metody (twierdzenia+dowody) i zostawiam klientowi wybór metody
Po co w artykule o grafie hamiltonowskim dowód twierdzenia Twierdzenie Oystein Ore? - (!?) no bo
- dotyczy ono grafów hamiltonowskich
- nie jest to dowód który każdy student/uczeń/itp, nawet stricte matematyczny przeprowadzi z marszu - oczywiście dla nielaików to banał, ale ja pamiętam jak kiedyś spędziłem długie chwile nad tym dowodem - dopóki nie wrzuciłem go do netu, śmiem twierdzić, że go nigdzie indziej nie ma - więc ja, warto?
Czy kiedykolwiek napisałeś jakikolwiek program analizujący graf? >> Dzisiejszy tekst robi wrażenie kawałka teorii, którą wykłada ktoś kto nigdy w życiu grafa na oczy nie widział. - tak, głównie w technice OOP chociaż prawdę mówiąc nie wiem o co Ci chodzi - znaczy się, bzdury tam są czy co? Przejrzyj "Matematykę dyskretną" Wrighta i Rossa - czy oni też piszą jak ludzie którzy w życiu grafu na oczy nie widzieli? Rnm 08:54, 19 kwi 2006 (CEST)
Odwołanie się do literatury z pewnością jest mocnym argumentem. Nie twierdzę, że twierdzenia i dowody należy wyrzucić z Wikipedii. Jednak w tym artykule nie wnoszą one zbyt wiele. Czy teraz nie jest lepiej? Cieszę się, że pracujesz nad grafami, ale musisz zrozumieć, że mogą być różne spojrzenia na ten sam temat. Dla mnie najważniejsze jest zawsze pytanie o aplikacje. Dla teoretyka wystarczy samo piękno twierdzeń i równań, które tworzy. Superborsuk Ω 19:19, 19 kwi 2006 (CEST)
Sekcja "Indeksowanie wierzchołków" budzi wątpliwości - z treści nie wynika za bardzo o co wogóle chodzi, no i skąd tam czas stały? Akapit o powiązaniu z problemem obnośnego sprzedawcy proponowałbym gdzieś niżej. Kuszi 23:34, 28 kwi 2006 (CEST).
- Indeksowanie powinno moim zdaniem trafić do artykułu graf (matematyka) albo droga (teoria grafów). Co do komiwojażera, to były uwagi, że brakuje tej informacji. Graf Hamiltona (87 odp.) i komiwojażer (600 odp.) bardzo się wiążą, a ten drugi jest w Internecie bardziej popularny. Postarałem się, aby sam problem stał się intuicyjnym przykładem przemawiającym do czytelnika szczególnie takiego który Superborsuk Ω 03:24, 29 kwi 2006 (CEST) PS. Ależ wysokie pozycjonowanie ma Wikipedia w Google - artykuł graf hamiltonowski jest pierwszy, a problem komiwojażera trzeci.
Komentarz do usuniętych zdań: Rozważania na temat poruszania się specjalisty od handlu bezpośredniego po takim grafie zawarto w problemie komiwojażera. - rozważań nie zawieramy w problemie, zwrot niepoprawny, nie wiem jak to poprawić żeby było z sensem.
Wzrost złożoności obliczeń jest tak gwałtowny, że dla rzeczywistych przypadków, nawet najszybsze komputery, mogą znaleźć tylko przybliżoną drogę dla komiwojażera. - podobne zdanie mogloby się pojawić, ale sugeruje ono że cykl hamoltona rozwiązuje problem komiwojażera, co nie jest prawdą (Bez straty ogólności prob. kom. dotyczy grafów pełnych). Poza tym, co prawda złożoność to funkcja, ale jakoś razi mnie zwrot:"wzrost złożoności" - wydaje mi się że coś takiego nie funkcjonuje. Problem z sekcją indeksowanie wierzchołków pozostaje Kuszi 11:09, 29 kwi 2006 (CEST)
[edytuj] Graf hamiltonowski
jeszcze może nie jest na medal, ale IMO niewiele brakuje - trochę grafiki z przykładowymi grafami, może o tej gierce którą Hamilton sprzedał na podstawie pomysłu grafowego, dowód twierdzenia Bondano - i tyle, więcej chyba ciężko będzie wymyślić... Rnm 17:33, 17 kwi 2006 (CEST)
Za
- Marek9 11:10, 18 kwi 2006 (CEST)
Przeciw
- Superborsuk Ω 20:57, 17 kwi 2006 (CEST) – jest gorzej. Ten tekst po prostu nie jest poprawny merytorycznie i wymaga jeszcze dużo pracy. Na dodatek oprócz ścisłego opisu, brakuje wersji dla laików. Proszę zerknąć na wersję angielską.
Dyskusja Z puntu widzenia laika, przede wszystkimi to jest napisane tak, że trudno pojąć o co tu chodzi. Najpierw jest mowa o cyklu Hamiltona (która jest przynajmniej zalinkowany), potem o ścieżce Hamiltona (czy to to samo co cykl, nie wiadomo bo nie ma nawet linku do tego pojęcia?), potem jakichś indeksowaniach (ale nie wiadomo co jest indeksowane...), potem o czasie stałym (co to jest u licha "czas stały" ? czas przecież zawsze płynie...) Dalej, dla dalszego pognębienia czytelnika mowa jest o czasie wielomianowym. Potem można przeczytać, że "Owo twierdzenie pozwalało w czasie liniowym znaleźć odpowiedź na pytanie, czy graf jest eulerowski." - to co się z tym twierdzeniem stało? okazało się fałszywe, zapomniano je? i jeszcze cała masa niejasności i niezręczności. Potrzebny jest gruntowna praca nad tym artykułem. Przydałby się choć krótki rozdzialik bardziej intuicyjnie wyjaśniający o co tu chodzi. Polimerek 19:19, 17 kwi 2006 (CEST)
wprowadziłem poprawki.
"Z puntu widzenia laika" - coś za coś, albo piszemy kokretnie, zakładając, że user ma minimalne wyobrażenie o kontekście w jakim dane zagadnienie się pojawia, albo... no właśnie, co?
"co to jest u licha "czas stały" ? " - niezależny od tego, czy np. szukasz krawędzi w grafie o 10 czy 1000000 wierzchołkach :)
"Dalej, dla dalszego pognębienia czytelnika mowa jest o czasie wielomianowym" - jest już link do złożoności obliczeniowej
""Owo twierdzenie pozwalało w czasie liniowym znaleźć odpowiedź na pytanie, czy graf jest eulerowski." - to co się z tym twierdzeniem stało? okazało się fałszywe, zapomniano je?" - niemój tekst, już jest bardziej fortunnie napisane.
"i jeszcze cała masa niejasności i niezręczności." - wymieniaj chopie, to zaraz ich nie będzie !
"Przydałby się choć krótki rozdzialik bardziej intuicyjnie wyjaśniający o co tu chodzi. " - no ale wstęp dokładnie mówi o co chodzi, dalsze "uczłowieczanie" mogłoby prowadzić do definicji przez rysowanie i dowodów przez machanie rękami, a tego chyba nie chcemy? ;) Rnm 20:49, 17 kwi 2006 (CEST)
Superborsuk - a w którym miejscu jest on merytorycznie niepoprawny (chyba, że znowu podważasz merytoryczne uwagi wybitnych znawców informatyki - vide algorytm, co do którego (definicji) wśród owych autorytetów jest zgoda...)? Rnm 21:04, 17 kwi 2006 (CEST)
qrde, dla jakich laików? mój kuzyn (ma 9 lat) ją zrozumiał! przecież nie będziemy za wszystkim schodzić do poziomu przedszkola! w wersji angielskiej nie wiem czy jest tak o niebo lepiej wytłumaczone - ścieżka przechodząca dokładnie raz przez każdy vertex jest ścieżką przechodząca dokładnie raz.. JAK TO PROŚCIEJ NAPISAĆ???? Rnm 21:07, 17 kwi 2006 (CEST)
Poprawność merytoryczna musi być równoznaczna z pełnym określeniem zestawu symboli, którego używasz. Nie możesz wyjąć z książki o algorytmice kilku linijek i wstawić ich do Wikipedii. Po pierwsze to spowoduje NPA, a po drugie brakuje kontekstu. Powiedzmy, że autor wprowadził jakieś swoje oznaczenie w poprzednim fragmencie tekstu, a ty użyłeś go w formule wstawionej do Wikipedii. Bez tej dodatkowej informacji zależność jest błędna ponieważ nie da się jasno i jednoznacznie zinterpretować.
W opisie, który dziś znajduje się w haśle, jest bardzo wiele fragmentów, gdzie przyjęto założenie zgodnie, z którym czytelnik zna wcześniejsze fragmenty używanej przez Ciebie książki. Na koniec podstawowa sprawa: każda matematyczna zależności musi być dokładnie opisana, a na Wikipedii nawet dokładniej. Superborsuk Ω 21:41, 17 kwi 2006 (CEST)
o które oznaczenia dokładnie Ci chodzi? o deg(v) jako stopień wierzchołka? Czy o Kn,m a może o symbol newtona??? Bo więcej "nietypowych" nie znalazłem. A może moc zbioru? Na Boga, jakiegoś minimul trzeba wymagać, bo nigdy z pojęcia zbioru nie wyjdziemy!!! Zresztą, akurat z książkowej wersji korzystałem tylko w przypadku dowodów - reszta jest z głowy lub netu, i z tego co obserwuję, to o ile droga może być ścieżką/marszrutą czy szlakiem, o tyle deg(v) jest częste i chyba jednoznaczne. Zresztą, przecież jest opcja edytuj - jeżeli uważasz , że coś trzeba dopisać, to proszę - dopisz, a nie pisz o niemerytorycznym artykule, bo niemerytoryczność to nie przesadny formalizm czy też zakładanie, że czytelnik, czytający o grafach Hamiltona wie mniej więcej co to jest graf, ale jakieś totalne bzdury. Ale jeszcze raz - które kokretnie oznaczenia Ci nie leżą ? Piszesz długie uwagi z których nic konstruktywnego nie wynika, gdyż są one ogólnikowe i nieprecyzyjne, zamiast dodać co IYO brakuje, postulujesz usunięcie tekstów - sorki, ale nie każdy potrafi sobie udowodnić te twierdzenia, a w internecie znalezienie czegoś ponad sam im tekst jest bardzo trudne - postępujesz dokładnie tak jak w przypadku algorytmu - coś nie do końca pasi, to na śmietnik z tym - uwziełeś się, czy co? A może uważasz siebie za wyrocznię w sprawie informatyki? (sorki za wycieczki osobiste, ale piszę jeszcze raz - wybitni pracownicy II uni wroc uznali "moją" definicję algorytmu, jak i zależność przepiskulinarny-algorytm za poprawną - a Ty w ramach "przeredagowania" artykułu wywaliłeś tą definicję (co Ty, z jakiejś politechniki jesteś? oni tam mają ciekawe podejście (np. nazywają funkcją niejednoznaczne relacje, wymyślają takie buły jak "algorytm/program działający w sposób losowy"))- IMO próbujesz tu przeprowadzić podobną akcję, tj. z jednej strony robić się na formalistę, a z drugiej zachowywać się jak humanisty który za bardzo do serca wziął sobie metody logiki, jak by nie patrzeć, ścisłej) Rnm 22:27, 17 kwi 2006 (CEST)
Nie widzę nic o NP-zupelości problemu znajdowania ścieżki, ani o statusie podproblemów - przydałoby się. Ponadto pokrewny problem komiwojażera nie jest nawet wspomniany w treści. Kuszi 12:12, 28 kwi 2006 (CEST).
