Гамильтоновы циклы, Основные понятия и определения - Гамильтоновы циклы
Название "гамильтонов цикл" произошло от задачи "Кругосветное путешествие" предложенной ирландским математиком Вильямом Гамильтоном в 1859 году. Нужно было, выйдя из исходной вершины графа, обойти все его вершины и вернуться в исходную точку. Граф представлял собой укладку додекаэдра, каждой из 20 вершин графа было приписано название крупного города мира.
Основные понятия и определения
Если граф имеет простой цикл, содержащий все вершины графа по одному разу, то такой цикл называется Гамильтоновым циклом, а граф называется Гамильтоновым графом. Граф, который содержит простой путь, проходящий через каждую его вершину, называется Полугамильтоновым. Это определение можно распространить на ориентированные графы, если путь считать ориентированным.
Гамильтонов цикл не обязательно содержит все ребра графа. Ясно, что гамильтоновым может быть только связный граф и, что всякий гамильтонов граф является полугамильтоновым. Заметим, что гамильтонов цикл существует далеко не в каждом графе.
Замечание.
Любой граф G можно превратить в гамильтонов граф, добавив достаточное количество вершин. Для этого, например, достаточно к вершинам v1,..., vP графа G добавить вершины u1,..., uP и множество ребер {(vI, uI)}{(uI, vI+1)}.
Степенью вершины v называется число ребер d(v), инцидентных ей, при этом петля учитывается дважды. В случае ориентированного графа различают степень dO(v) по выходящим дугам и dI(v) - по входящим.
Похожие статьи
-
Условия существования гамильтонова цикла - Гамильтоновы циклы
В отличие от эйлеровых графов, где имеется критерий для графа быть эйлеровым, для гамильтоновых графов такого критерия нет. Более того, задача проверки...
-
Задачи, связанные с поиском гамильтоновых циклов - Гамильтоновы циклы
В ряде отраслей промышленности возникает следующая задача планирования. Нужно произвести n продуктов, используя единственный тип аппаратуры. Аппарат...
-
Пока неизвестно никакого простого критерия или алгебраического метода, позволяющего ответить на вопрос, существует или нет в произвольном графе G...
-
ФУНКЦИИ, Основные понятия - Свойства функций
Основные понятия При изучении различного рода явлений приходится иметь дело с совокупностью переменных величин, которые связаны между собой таким...
-
Основные понятия сетевых и графовых моделей Объектом исследования является сеть, состоящая из узлов и линий связи. Предполагается, что в сети имеется два...
-
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ: ОСНОВНАЯ СХЕМА - Задача коммивояжера
Пусть - конечное множество и - вещественно-значная функция на нем; требуется найти минимум этой функции и элемент множества, на котором этот минимум...
-
Основные понятия и определения планирования и организации эксперимента Планирование эксперимента - это процедура выбора числа и условий проведения...
-
ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ СКАЛЯРНЫХ И ВЕКТОРНЫХ ВЕЛИЧИН Величины называют Скалярными (скалярами), Если они после выбора единиц измерения полностью...
-
Описание процессов, происходящих на поверхности, изобилует специальными терминами, и при рассмотрении адсорбционных явлений приходится говорить на языке,...
-
Модели линейного программирования. Основные определения Еще одним классом задач экономико-математического моделирования являются задачи линейного...
-
Основные понятия и обозначения Динамическое программирование как самостоятельная дисциплина сформировалась в пятидесятых годах двадцатого века. Большой...
-
В данной главе мы обсуждаем известные модели НС: модель Маккалоха и Питтса; модель Розенблата; модели Хопфилда и Больцмана; модель на основе обратного...
-
Основные понятия и определения проблемы прогнозирования - Прогнозирующие системы
Необходимо отметить, что мы рассматриваем прогнозирование в целях планирования производства или управления запасами. Таким образом, наш интерес лежит в...
-
Модели теории игр. Основные определения и термины В разных областях целенаправленной деятельности, например при разработке и эксплуатации АСУ, часто...
-
ПОНЯТИЕ ОБ АВТОКОРРЕЛЯЦИИ. ОПРЕДЕЛЕНИЕ СИЛЫ АВТОКОРРЕЛЯЦИИ Парные регрессионные модели отражают специфику взаимодействия некоторого функционального...
-
Свойство 1. Вероятность достоверного события равна единице. Действительно, если событие достоверно, то каждый элементарный исход испытания...
-
Основные понятия информационного моделирования - Понятие об информационном моделировании
Остановимся на информационных моделях, отражающих процессы возникновения, передачи, преобразования и использования информации в системах различной...
-
Основные понятия - О новой парадигме математических методов исследования
Целесообразно начать с определений используемых понятий. Термин "парадигма" происходит от греческого "paradeigma" -- пример, образец и означает...
-
Введение - Основные понятия теории вероятностей
Каждая наука, развивающая общую теорию какого-либо круга явлений, содержит ряд основных понятий, на которых она базируется. Таковы, например, в геометрии...
-
Цель и задачи исследования операций Исследование операций - научная дисциплина, занимающаяся разработкой и практическим применением методов наиболее...
-
Пусть { , , ..., } - множество возможных состояний некоторой физической системы. В любой момент времени система может находиться только в одном...
-
Составление химических уравнений, Расчеты по химическим уравнениям - Основные понятия и законы химии
Включает три этапа: 1. Запись формул веществ, вступивших в реакцию (слева) и продуктов реакции (справа), соединив их по смыслу знаками "+" и "®" : HgO ®...
-
Введение, Основные положения - Эволюционные процедуры решения комбинаторных задач на графах
Среди набора комбинаторно-логических задач на графах важное место занимает проблема определения паросочетаний, раскраски графа, выделения в графе...
-
К основным понятиям и категориям статистической науки относятся следующие: - совокупность, - признак, - показатель, - система показателей и др....
-
Опис-ся правиломВант-Гоффа: С увелич-ем темп. на каждые 10 градусов. Скор. больш-ва хим. р-ций увелич-ся в 2-4 раза. Где г-темп. коэф-т скорости хим....
-
Атомно-молекулярное учение. Основные понятия химии - Основные понятия неорганической химии
Все вещества сост. из атомов. В химию понятие атома ввел Ломоносов: ат. разные, ат. каждого вида один. М/у собой, но отлич. от атомов др. вида., ат....
-
Заключение - Основные понятия теории вероятностей
Эмпирическое "определение" вероятности связано с частотой наступления события исходя из того, что при достаточно большом числе испытаний частота должна...
-
Основные понятия линейного программирования - Оптимальное программирование
Математические исследования отдельных экономических проблем, математическая формализация числового материала проводилась еще в XIX веке. При...
-
Основные понятия корреляционно-регрессионного анализа Теория и методы корреляционного анализа используются для выявления связи между случайными...
-
Определение понятия "имитационное моделирование" - Имитационное моделирование в экономике
В современной литературе не существует единой точки зрения по вопросу о том, что понимать под имитационным моделированием. Так существуют различные...
-
Конкретные модели процессов управления в социальных и экономических системах исходят из общей методологии, которую и формулируем в настоящей статье....
-
Ответ: Функция y=arctgx, ее график, свойства Ответ: Функция y=arcctgx, ее график, свойства Ответ: Решение уравнений sinx=a, частные случаи Ответ:...
-
Понятие о рядах динамики - Методы анализа основной тендеции развития в рядах динамики
Одной из важнейших задач статистики является изучение изменений анализируемых показателей во времени, т. е. их динамика. Эта задача решается при помощи...
-
Св-ва хим. эл-тов, а так же формы и св-ва соединений эл-тов нах-ся в периодической зависимости от заряда ядер их атомов. Возрастание + зарядов атомных...
-
Пусть функция определена в промежутке Х (рис.1). Исходя из некоторого значения независимой переменной, придадим ему приращение, не выводящее его из...
-
Закон Авогадро ди Кваренья (1811 г.) - Основные понятия и законы химии
В равных объемах различных газов при одинаковых условиях (температура, давление и т. д.) содержится одинаковое число молекул. Закон справедлив только для...
-
Электролиз - р-ция превращения ве-ва под действ. эл. тока. если к р-ру или расплаву эл-та поднести эл. ток, то ионы в нем начнут направленно перемещаться...
-
Гидролиз - р-ция обменного взаимод-я ионов связи, с ионами, входящими в состав Н2О (Н+ и ОН-). Г-з протекает в том случае, если хотя бы один из ионов...
-
Если на равновесную с-му не оказ-ся вноешнего воздействия (не изм. темп, давл.), то равновесие м/существовать неизменным долго. Любое внешнее возд-ие...
-
Масса всех веществ, вступивших в химическую реакцию, равна массе всех продуктов реакции. Атомно-молекулярное учение этот закон объясняет следующим...
Гамильтоновы циклы, Основные понятия и определения - Гамильтоновы циклы