|
|
|
Polski Serwis Naukowy - OnLine od 1999 roku
 RSS
Dodaj do:
Warto przeczytać: Cykl prelekcji, poświęconych najważniejszym odkryciom archeologicznym w Polsce w ostatnich dziesięcioleciach, rozpocznie się 2 lutego w Muzeum Starożytnego Hutnictwa Mazowieckiego w Pruszkowie. Zainauguruje go odczyt na temat rezydencji pierwszych Piastów na ... 18 lutego rozpocznie sie cykl otwartych wykładów popularnonaukowych, dotyczące zagadnień medycznych, przygotowany przez naukowców z Wydziału Nauk Medycznych Uniwersytetu Warmińsko-Mazurskiego w Olsztynie. Uczestnicy spotkań będą mogli zdobyć wiele ciekaw... Właśnie zakończył się duży, czteroletni projekt unijny poświęcony światowym zasobom wody, z którego opublikowano raport zawierający końcowe wnioski.
Projekt WATCH (Woda a zmiany globalne), realizowany od lutego 2007 r. do lipca 2011 r.,... W piątek, 22 stycznia, w Obserwatorium Astronomicznym Uniwersytetu im. Adama Mickiewicza w Poznaniu odbył się wykład dr Wojciecha Borczyka "Obserwacje astronomiczne wczoraj i dziś". Była to pierwsza odsłona tegorocznego cyklu popularnonaukowych wykładów w... Mimo swojej wszechobecności i zróżnicowanych ról, okrzemki morskie - główny komponent fitoplanktonu występującego obficie w oceanie, tworzący tym samym podstawę morskiego łańcucha pokarmowego - pozostają owiane tajemnicą. Niedawno finansowane ze środków ...
Ostatnio na Forum:
Dyskusje
8
odp.
4
odp. Reklama:
 Cykl HamiltonaCzy wiesz że...? Graf to – w uproszczeniu – zbiór wierzchołków, które mogą być połączone krawędziami, w taki sposób, że każda krawędź kończy się i zaczyna w którymś z wierzchołków (ilustracja po prawej stronie). Grafy to podstawowy obiekt rozważań teorii grafów. Za pierwszego teoretyka i badacza grafów uważa się Leonarda Eulera, który rozstrzygnął zagadnienie mostów królewieckich. Twierdzenie Ore pozwalające stwierdzić, czy graf ma cykl Hamiltona. Zostało ono sformułowane w roku 1961 przez norweskiego matematyka Øystein Ore. Spełnienie przez graf warunku twierdzenia jest wystarczające, aby był on grafem hamiltonowskim. Cykl Hamiltona to taki cykl w grafie, w którym każdy wierzchołek grafu przechodzony jest tylko jeden raz (oprócz pierwszego wierzchołka) . Znalezienie cyklu Hamiltona o minimalnej sumie wag krawędzi jest równoważne rozwiązaniu problemu komiwojażera. Grafy zawierające cykl Hamiltona nazywamy hamiltonowskimi. Algorytm najbliższego sąsiada - naiwny algorytm rozwiązywania problemu komiwojażera polegający na odwiedzaniu, począwszy od wybranego wierzchołka, wierzchołka znajdującego się najbliżej wierzchołka ostatnio odwiedzonego. Bardzo prosty do zaprogramowania, szybki, ale daje słabe wyniki.
Cykl to droga (inaczej: ścieżka prosta) zamknięta, czyli taka, której koniec (ostatni wierzchołek) jest identyczny z początkiem (pierwszym wierzchołkiem). Zobacz teżProblem komiwojażera (TSP - ang. traveling salesman problem) jest to zagadnienie z teorii grafów, polegające na znalezieniu minimalnego cyklu Hamiltona w pełnym grafie ważonym.
Cykl Eulera to taki cykl w grafie, który przechodzi przez każdą jego krawędź dokładnie raz. Jeżeli w danym grafie możliwe jest utworzenie takiego cyklu, to jest on nazywany grafem eulerowskim.
Czy wiesz że...? beta Graf hamiltonowski to graf rozważany w teorii grafów zawierający ścieżkę (drogę) przechodzącą przez każdy wierzchołek dokładnie jeden raz zwaną ścieżką Hamiltona. W szczególności grafem hamiltonowskim jest graf zawierający cykl Hamiltona, tj. zamkniętą ścieżkę Hamiltona. W niektórych źródłach graf zawierający tylko ścieżkę Hamiltona nazywany jest grafem półhamiltonowskim. Powyższa treść oraz zamieszczone w niej powiązane definicje/pojęcia - udostępniane są na licencji Creative Commons: uznanie autorstwa, na tych samych warunkach, z możliwością obowiązywania dodatkowych ograniczeń.
Zobacz szczegółowe informacje o warunkach korzystania
Wszystkie hasła znajdujące się w naszym mirrorze Wikipedii mają znaczenie informacyjne i edukacyjne. Nie mogą być traktowane jako porady. |
