Граф Гамильтона

Граф Гамильтона
   граф, содержащий цикл (замкнутый путь), в который входят все вершины, причем по одному разу (гамильтонов цикл), т.е. который можно обойти; эффективный общий алгоритм выяснения, является ли данный граф гамильтоновым, не известен, и задача решается перебором (в отличие от эйлерова цикла, содержащего все ребра по одному разу):
    "Мне прислали из США ксерокопии статей, демонстрирующих потенциально содержащуюся в нуклеотидных цепочках вычислительную мощность, которая почти на десять порядков превышает вычислительную мощность самых современных компьютеров (используемых и создаваемых нами), работающих последовательно. Сделал это доброжелательный читатель, поскольку заметил, как он мне написал, какое-то родство моей интуиции, нашедшей отражение в книге "Мнимая величина" и касающейся именно действенных потенциалов наследственного кода, с первыми результатами работ, в которых фрагменты кода - олигонуклеотидные секвенции, состоящие из примерно 20 полимеров, - оказались способны практически преодолеть, то есть решить, такие задачи из области теории графов Гамильтона, которые для "нормального" компьютера оказываются очень трудоемкими". - Тайна китайской комнаты. Вычислительная мощность жизни

Мир Лема - словарь и путеводитель. . 2004.

Игры ⚽ Поможем написать курсовую

Смотреть что такое "Граф Гамильтона" в других словарях:

  • Граф Аррана — (англ. Earl of Arran) дворянский титул в Ирландии и Шотландии. Впервые был создан в 1467 г. для Томаса Бойда (позднее он был лишен титула в связи с обвинением в измене). В 1503 г. титул графа Аррана был восстановлен и передан Джеймсу… …   Википедия

  • Граф Линкольн — (англ. Earl of Lincoln)  один из дворянских титулов средневековой Англии, сохранившийся до настоящего времени. С XII века этот титул учреждался восемь или девять раз. Среди его наиболее известных носителей  Джон де ла Поль,… …   Википедия

  • Граф Арран — Клан Гамильтон Hamilton Девиз «Сквозь!» (гэльск. Troimh, англ. Through) Земли Арран, Ренфрушир Символ Листья лавра …   Википедия

  • Граф Оркни — Графами Оркни сначала были норвежские ярлы, правившие Оркнейскими и Шетландскими островами, а также частями Кейтнесса и Сутерленда. Графы периодически давали присягу королям Норвегии, а позже также и королям Шотландии, как правители части… …   Википедия

  • Граф Лаудон — Кэмпбелл, Джон, 1 й граф Лаудон Джон Кэмпбелл (англ. John Campbell; ум. 1662), 1 й граф Лаудон (с 1637 г.) крупный шотландский политический деятель, один из инициаторов ковенантского движения и канцлер Шотландии в 1641 1660 гг. Джон Кэмпбелл… …   Википедия

  • Цикл Гамильтона — Граф додекаэдра с выделенным циклом Гамильтона Гамильтонов граф в теории графов это граф, содержащий гамильтонову цепь или гамильтонов цикл. Гамильтонов путь (или гамильтонова цепь) путь (цепь), содержащий каждую вершину графа ровно один раз.… …   Википедия

  • Гамильтонов граф — Граф додекаэдра с выделенным циклом Гамильтона …   Википедия

  • Гамильтон, Джеймс, 3-й граф Арран — Джеймс Гамильтон James Hamilton …   Википедия

  • Гамильтон, Джеймс, 1-й граф Арран — Джеймс Гамильтон James Hamilton …   Википедия

  • Макензи, Джордж, 2-й граф Сифорт — Джордж Макензи (англ. George Mackenzie; 1608(1608)  1651), 2 й граф Сифорт c 1633 года  шотландский государственный деятель, ковенантер и полководец середины XVII века, лидер клана Макензи. Биография Джордж Макензи был братом… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»