Hamiltonian graph
http://dbpedia.org/resource/Hamiltonian_graph
Hamiltonovský graf je graf, který lze projít takovou cestou, že každý jeho uzel je navštíven právě jednou s výjimkou uzlu výchozího, který je zároveň uzlem cílovým. Neboli - graf je hamiltonovský, právě když obsahuje kružnici, která prochází všemi jeho uzly (tzv. hamiltonovská kružnice). Název připomíná irského matematika a fyzika W. R. Hamiltona (1805-1865), od kterého pocházel hlavolam, v němž bylo za úkol obejít po hranách vrcholy pravidelného dvanáctistěnu.
rdf:langString
En Hamiltongraf är inom matematik en graf som har en Hamiltoncykel. En Hamiltonväg är en väg i en graf som innehåller varje nod exakt en gång. En Hamiltoncykel är en Hamiltonväg som börjar och slutar i samma nod. Hamiltongrafer har många tillämpningar, bl.a. handelsresandeproblemet och springareproblemet.
rdf:langString
哈密顿图（台湾作漢米頓圖）又稱漢密頓圖，是指存在哈密頓環的無向圖，由哈密顿爵士提出。
rdf:langString
En mathématiques, dans le cadre de la théorie des graphes, un chemin hamiltonien d'un graphe orienté ou non orienté est un chemin qui passe par tous les sommets une fois et une seule. Un cycle hamiltonien est un chemin hamiltonien qui est un cycle. Un graphe hamiltonien est un graphe qui possède un cycle hamiltonien. Un graphe hamiltonien peut contenir plusieurs cycles hamiltoniens : ainsi, le graphe de Chvátal a 12 sommets, 24 arêtes et 370 cycles hamiltoniens distincts.
rdf:langString
Graf hamiltonowski – rodzaj grafu rozważany w teorii grafów i definiowany dwojako, w dwóch nieco innych znaczeniach:
* szerszym: dowolny graf zawierający ścieżkę (drogę) przechodzącą przez każdy wierzchołek dokładnie jeden raz zwaną ścieżką Hamiltona;
* węższym: 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.
rdf:langString
Гамильтонов граф — граф, содержащий гамильтонов цикл. При этом гамильтоновым циклом является такой цикл (замкнутый путь), который проходит через каждую вершину данного графа ровно по одному разу;то есть простой цикл, в который входят все вершины графа. Также с гамильтоновым графом тесно связано понятие гамильтонова пути, который является простым путём (путём без петель), проходящим через каждую вершину графа ровно один раз. Гамильтонов путь отличается от цикла тем, что у пути начальные и конечные точки могут не совпадать, в отличие от цикла. Гамильтонов цикл является гамильтоновым путём.
rdf:langString
Га́мільтонів гра́ф — в математиці це граф, що містить гамільтонів цикл. Га́мільтонів шля́х — шлях, що містить кожну вершину графу рівно один раз. Гамільтонів шлях, початкова і кінцева вершини якого збігаються, називається гамільтоновим циклом. Гамільтонові шлях, цикл і граф названі на честь ірландського математика Вільяма Гамільтона, який вперше визначив ці класи, дослідивши задачу «навколосвітньої подорожі» по додекаедру, вузлові вершини якого символізували найбільші міста Землі, а ребра — дороги, що їх з'єднують.
rdf:langString
rdf:langString
Hamiltonovský graf
rdf:langString
Hamiltonscher Graph
rdf:langString
Hamiltonian graph
rdf:langString
Graphe hamiltonien
rdf:langString
Graf hamiltonowski
rdf:langString
Гамильтонов граф
rdf:langString
Hamiltongraf
rdf:langString
哈密顿图
rdf:langString
Гамільтонів граф
xsd:integer
450651
xsd:integer
784076901
rdf:langString
Hamiltonovský graf je graf, který lze projít takovou cestou, že každý jeho uzel je navštíven právě jednou s výjimkou uzlu výchozího, který je zároveň uzlem cílovým. Neboli - graf je hamiltonovský, právě když obsahuje kružnici, která prochází všemi jeho uzly (tzv. hamiltonovská kružnice). Název připomíná irského matematika a fyzika W. R. Hamiltona (1805-1865), od kterého pocházel hlavolam, v němž bylo za úkol obejít po hranách vrcholy pravidelného dvanáctistěnu.
rdf:langString
En mathématiques, dans le cadre de la théorie des graphes, un chemin hamiltonien d'un graphe orienté ou non orienté est un chemin qui passe par tous les sommets une fois et une seule. Un cycle hamiltonien est un chemin hamiltonien qui est un cycle. Un graphe hamiltonien est un graphe qui possède un cycle hamiltonien. Un graphe hamiltonien ne doit pas être confondu avec un graphe eulérien, où l'on passe par toutes les arêtes une fois et une seule : dans un cycle hamiltonien, on peut très bien négliger de passer par certaines arêtes. Un graphe peut être eulérien, hamiltonien, les deux à la fois, ou aucun des deux : le graphe papillon est un exemple de graphe eulérien mais pas hamiltonien. Un graphe hamiltonien peut contenir plusieurs cycles hamiltoniens : ainsi, le graphe de Chvátal a 12 sommets, 24 arêtes et 370 cycles hamiltoniens distincts. On a démontré un certain nombre de conditions mathématiques, qui, si elles sont vérifiées, permettent d'assurer qu'un graphe est hamiltonien, ainsi que des conditions qui, si elles ne sont pas vérifiées, assurent qu'il ne l'est pas. On peut par ailleurs confier à des ordinateurs le soin de chercher des cycles hamiltoniens au moyen d'algorithmes que l'on a optimisés petit à petit. Dans les deux cas, le problème algorithmique du chemin hamiltonien est NP-complet, i.e. difficile à résoudre dans un temps raisonnable dans le cas général. Les graphes hamiltoniens sont un domaine de recherche actif à la fois en mathématiques et en informatique.
rdf:langString
Graf hamiltonowski – rodzaj grafu rozważany w teorii grafów i definiowany dwojako, w dwóch nieco innych znaczeniach:
* szerszym: dowolny graf zawierający ścieżkę (drogę) przechodzącą przez każdy wierzchołek dokładnie jeden raz zwaną ścieżką Hamiltona;
* węższym: 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. Aby lepiej zrozumieć właściwości grafu hamiltonowskiego można się posłużyć przykładem komiwojażera, który chce odwiedzić wszystkich swoich klientów, ale tylko raz (problem komiwojażera). Klienci to wierzchołki grafu, a drogi między nimi są jego krawędziami. Jeżeli graf jest hamiltonowski, to znaczy, że komiwojażer może obejść wszystkich klientów bez mijania drugi raz żadnego z nich i wrócić do punktu wyjścia.
rdf:langString
En Hamiltongraf är inom matematik en graf som har en Hamiltoncykel. En Hamiltonväg är en väg i en graf som innehåller varje nod exakt en gång. En Hamiltoncykel är en Hamiltonväg som börjar och slutar i samma nod. Hamiltongrafer har många tillämpningar, bl.a. handelsresandeproblemet och springareproblemet.
rdf:langString
Гамильтонов граф — граф, содержащий гамильтонов цикл. При этом гамильтоновым циклом является такой цикл (замкнутый путь), который проходит через каждую вершину данного графа ровно по одному разу;то есть простой цикл, в который входят все вершины графа. Также с гамильтоновым графом тесно связано понятие гамильтонова пути, который является простым путём (путём без петель), проходящим через каждую вершину графа ровно один раз. Гамильтонов путь отличается от цикла тем, что у пути начальные и конечные точки могут не совпадать, в отличие от цикла. Гамильтонов цикл является гамильтоновым путём. Гамильтоновы путь, цикл и граф названы в честь ирландского математика У. Гамильтона, который впервые определил эти классы, исследовав задачу «кругосветного путешествия» по додекаэдру. В этой задаче вершины додекаэдра символизировали известные города, такие как Брюссель, Амстердам, Эдинбург, Пекин, Прага, Дели, Франкфурт и др., а рёбра — соединяющие их дороги. Путешествующий должен пройти «вокруг света», найдя путь, который проходит через все вершины ровно один раз. Чтобы сделать задачу более интересной, порядок прохождения городов устанавливался заранее. А чтобы было легче запомнить, какие города уже соединены, в каждую вершину додекаэдра был вбит гвоздь, и проложенный путь отмечался небольшой верёвкой, которая могла обматываться вокруг гвоздя. Однако такая конструкция оказалась слишком громоздкой, и Гамильтон предложил новый вариант игры, заменив додекаэдр плоским графом, изоморфным графу, построенному на рёбрах додекаэдра.
rdf:langString
哈密顿图（台湾作漢米頓圖）又稱漢密頓圖，是指存在哈密頓環的無向圖，由哈密顿爵士提出。
rdf:langString
Га́мільтонів гра́ф — в математиці це граф, що містить гамільтонів цикл. Га́мільтонів шля́х — шлях, що містить кожну вершину графу рівно один раз. Гамільтонів шлях, початкова і кінцева вершини якого збігаються, називається гамільтоновим циклом. Гамільтонові шлях, цикл і граф названі на честь ірландського математика Вільяма Гамільтона, який вперше визначив ці класи, дослідивши задачу «навколосвітньої подорожі» по додекаедру, вузлові вершини якого символізували найбільші міста Землі, а ребра — дороги, що їх з'єднують. Хоч вони й названі на честь Гамільтона, гамільтонові цикли в многогранниках раніше вивчав , який, зокрема, навів приклад многогранника без гамільтонових циклів. Ще раніше гамільтонові цикли і шляхи в графі ходів коня на шахівниці, маршрути коня, вивчав індійський математик IX століття , і приблизно в той самий час арабський математик . У XVIII столітті в Європі маршрут коня публікували Абрахам де Муавр і Леонард Ейлер. Задачу знаходження гамільтонового циклу можна використати як основу для доведення з нульовим пізнанням.
xsd:nonNegativeInteger
110