Dyskusja:Graf hamiltonowski

Po głosowaniu zakończonym 17 maja 2006 artykułowi Graf hamiltonowski nie przyznano statusu Artykułu na Medal.
Zobacz dyskusję

hamiltonowski jest przymiotnikiem, dlatego hasło powinno się nazywać

Graf hamiltonowski, a nie Graf Hamiltonowski

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)[odpowiedz]

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)[odpowiedz]

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)[odpowiedz]

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)[odpowiedz]

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)[odpowiedz]

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)[odpowiedz]

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)[odpowiedz]

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)[odpowiedz]

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)[odpowiedz]

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).[odpowiedz]

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.[odpowiedz]

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)[odpowiedz]

Informacja o tym, że dowolny nadgraf grafu hamiltonowskiego jest też hamiltonowski jest nieprawdziwa... łatwo skonstruować nadgraf np. grafu pełnego który hamiltonowski nie będzie...

Nieprawdziwa informacja z artykułu została usunięta. Dowód nieprawdziwości twierdzenia: Bierzemy dowolny graf hamiltonowski o liczbie wierzchołków większej od 1. Wybieramy z niego dowolny wierzchołek (nazwijmy go A) Tworzymy nadgraf tego grafu dołączając do niego dwa nowe wierzchołki w taki sposób, że oba są stopnia jeden i oba mają bezpośrednie połączenie krawędzią z A. Stworzony w ten sposób graf nigdy nie będzie grafem hamiltonowskim - stąd nieprawdą jest że każdy nadgraf grafu hamiltonowskiego jest grafem hamiltonowskim, ponieważ istnieje taki zbiór nadgrafów grafów hamiltonowskich, które nie są grafami hamiltonowskimi i jest on zbiorem liczności conajmniej alef zero