Четверг, 24.09.2020, 06:56
Ш  К  О  Л  А     П  И  Ф  А  Г  О  Р  А
      Предмет математики настолько серьезен, что нужно
не упускать случая, сделать его немного занимательным".
                                                                           Блез Паскаль
Главная | Регистрация | Вход Приветствую Вас Гость | RSS
ПАМЯТКИ ПО МАТЕМАТИКЕ   ВЕЛИКИЕ МАТЕМАТИКИ   ТЕОРИЯ ЧИСЕЛ   МАТЕМАТИЧЕСКАЯ ЛОГИКА
УРОКИ МАТЕМАТИКИ В ШКОЛЕ


МАТЕМАТИЧЕСКАЯ КЛАДОВАЯ


В МИРЕ ЗАДАЧ
ЕГЭ ПО МАТЕМАТИКЕ
МАТЕМАТИКА В НАЧАЛЬНОЙ ШКОЛЕ
ВАРИ, КОТЕЛОК!
УДИВИТЕЛЬНАЯ МАТЕМАТИКА
ВЫСШАЯ МАТЕМАТИКА
В МИРЕ ИНТЕРЕСНОГО
Категории раздела
ПРОСТЫЕ ЧИСЛА. ДОЛГАЯ ДОРОГА К БЕСКОНЕЧНОСТИ [37]
КОГДА ПРЯМЫЕ ИСКРИВЛЯЮТСЯ. НЕЕВКЛИДОВЫ ГЕОМЕТРИИ [23]
МУЗЫКА СФЕР. АСТРОНОМИЯ И МАТЕМАТИКА [57]
МАГИЯ ЧИСЕЛ. МАТЕМАТИЧЕСКАЯ МЫСЛЬ ОТ ПИФАГОРА ДО НАШИХ ДНЕЙ [27]
ИНВЕРСИЯ [20]
ИСТИНА В ПРЕДЕЛЕ. АНАЛИЗ БЕСКОНЕЧНО МАЛЫХ [47]
БЕСКОНЕЧНОСТЬ В МАТЕМАТИКЕ [43]
МАТЕМАТИЧЕСКАЯ ЛОГИКА И ЕЕ ПАРАДОКСЫ [6]
ИЗМЕРЕНИЕ МИРА. КАЛЕНДАРИ, МЕРЫ ДЛИНЫ И МАТЕМАТИКА [33]
АБСОЛЮТНАЯ ТОЧНОСТЬ И ДРУГИЕ ИЛЛЮЗИИ. СЕКРЕТЫ СТАТИСТИКИ [31]
КОДИРОВАНИЕ И КРИПТОГРАФИЯ [47]
МАТЕМАТИКА В ЭКОНОМИКЕ [39]
ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ И МАТЕМАТИКА [35]
ЧЕТВЕРТОЕ ИЗМЕРЕНИЕ. ЯВЛЯЕТСЯ ЛИ НАШ МИР ТЕНЬЮ ДРУГОЙ ВСЕЛЕННОЙ? [9]
ТВОРЧЕСТВО В МАТЕМАТИКЕ [44]
ЗАГАДКА ФЕРМА. ТРЕХВЕКОВОЙ ВЫЗОВ МАТЕМАТИКЕ [30]
ТАЙНАЯ ЖИЗНЬ ЧИСЕЛ. ЛЮБОПЫТНЫЕ РАЗДЕЛЫ МАТЕМАТИКИ [95]
АЛГОРИТМЫ И ВЫЧИСЛЕНИЯ [17]
КАРТОГРАФИЯ И МАТЕМАТИКА [38]
ПОЭЗИЯ ЧИСЕЛ. ПРЕКРАСНОЕ И МАТЕМАТИКА [23]
ТЕОРИЯ ГРАФОВ [33]
НАУКА О ПЕРСПЕКТИВЕ [29]
ЧИСЛА - ОСНОВА ГАРМОНИИ. МУЗЫКА И МАТЕМАТИКА [15]
Статистика

Онлайн всего: 3
Гостей: 3
Пользователей: 0
Форма входа

Главная » Файлы » МИР МАТЕМАТИКИ » ТЕОРИЯ ГРАФОВ

Гамильтоновы циклы
20.01.2016, 19:19

Рассмотрим следующую задачу. Можно ли найти такой путь в связном графе, который бы проходил через все вершины графа только один раз, причем начальная и конечная вершины при этом совпадали? Такие пути называют гамильтоновыми циклами.



На рисунке выше изображен гамильтонов цикл DABCED. Не следует путать гамильтоновы и эйлеровы циклы: в эйлеровых циклах нужно пройти ровно один раз по всем ребрам графа (вспомним задачу о кёнигсбергских мостах), а в гамильтоновых циклах нужно пройти ровно один раз по всем вершинам. Некоторые графы не содержат гамильтоновых циклов, другие содержат сразу несколько. Например, граф, изображенный на предыдущем рисунке, содержит два гамильтоновых цикла: DABCED и DCEBAD. Разумеется, обойти каждый гамильтонов цикл можно двумя способами: в прямом и в обратном направлении.

Несмотря на сложность поиска гамильтоновых циклов в больших графах, эта задача представляет огромный интерес при организации путешествий, доставке товаров, распределении продуктов в сетях супермаркетов и так далее.

* * *

ИЗОБРЕТЕНИЕ ЦЕНОЙ В ДВЕ ГИНЕИ

Подобные циклы на графах открыл Томас Киркман (1806–1895). Исследованием этих циклов занимался ирландский математик Уильям Роуан Гамильтон (1805–1865), он же сделал их широко известными. В 1859 году Гамильтон придумал такую игру: 20 вершин додекаэдра (правильного 12-гранника) соответствуют 20 городам. Нужно обойти все города по одному разу и при этом вернуться в тот же город, с которого началось путешествие. Восторженный Гамильтон продал идею производителю игрушек за смехотворную сумму в две гинеи. Блестящие идеи не всегда ценятся по достоинству!



Математик Уильям Роуан Гамильтон и придуманная им игра.

* * *

МЕТОД ПОСТРОЕНИЯ ДЕРЕВА

На рисунках ниже показано, как можно сопоставить исходному графу ABCD дерево всех возможных маршрутов для поиска гамильтоновых циклов, которые начинаются и заканчиваются в вершине А, а вершины В, С и D обходятся ровно один раз. С увеличением числа вершин поиск гамильтоновых циклов усложняется: в каждом случае исходным является полный граф с n вершинами (им соответствует n городов). Из каждого города можно попасть в — 1 город, из каждого из них — в n — 2 города и так далее, пока мы не вернемся в начальную точку. Следовательно, число маршрутов будет равно (n — 1)·(n — 2)·(n — 3)·… ·3·2·1. Вспомним, что факториалом числа называется произведение всех натуральных чисел от 1 до этого числа включительно (например, 6! = 6·5·4·3·2·1), следовательно, общее число циклов будет равно (n — 1)!. Так как каждый цикл можно пройти в прямом и обратном направлении, то общее число различных циклов будет в два раза меньше: (n -1)1/2. Впрочем, и это число будет очень велико: для n — 6 оно составит (6–1)!/2 = 60 циклов.


Категория: ТЕОРИЯ ГРАФОВ | Добавил: admin | Теги: ИТК и мате, Мир Математики, искусственный интеллект, машинное обучение, популярная математик, математика и информатик, дидактический материал по матем
Просмотров: 510 | Загрузок: 0 | Рейтинг: 0.0/0
УЧИТЕЛЮ ИНФОРМАТИКИ
КОНСПЕКТЫ УРОКОВ
ВНЕКЛАССНЫЕ МЕРОПРИЯТИЯ ПО ИНФОРМАТИКЕ
ПОСОБИЯ И МЕТОДИЧКИ ДЛЯ УЧИТЕЛЯ ИНФОРМАТИКИ
ИЗ ОПЫТА РАБОТЫ УЧИТЕЛЯ ИНФОРМАТИКИ
ЗАДАНИЯ ШКОЛЬНОЙ ОЛИМПИАДЫ ПО ИНФОРМАТИКЕ


ИНФОРМАТИКА В ШКОЛЕ


ИНФОРМАТИКА В НАЧАЛЬНЫХ КЛАССАХ
ИНФОРМАТИКА В 3 КЛАССЕ
ИНФОРМАТИКА В 4 КЛАССЕ
КОНТРОЛЬНЫЕ РАБОТЫ ПО ИНФОРМАТИКЕ. 3 КЛАСС
КОНТРОЛЬНЫЕ РАБОТЫ ПО ИНФОРМАТИКЕ. 4 КЛАСС
ПРОГРАММИРОВАНИЕ ДЛЯ ДЕТЕЙ
СКАЗКА "ПРИКЛЮЧЕНИЯ ЭЛЕКТРОШИ"
ИГРОВЫЕ ТЕХНОЛОГИИ НА УРОКАХ ИНФОРМАТИКИ
ВИКТОРИНЫ ПО ИНФОРМАТИКЕ
КОМПЬЮТЕРНЫЕ ЧАСТУШКИ
ОБРАТНАЯ СВЯЗЬ
Поиск


Друзья сайта
  • Создать сайт
  • Все для веб-мастера
  • Программы для всех
  • Мир развлечений
  • Лучшие сайты Рунета
  • Кулинарные рецепты

  • Copyright MyCorp © 2020
    Яндекс.Метрика Рейтинг@Mail.ru