Дискретная математика. Ерош И.Л - 99 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

99
Пусть, например, бывшие пролетарии, а ныне демократы первой
волны решили построить город и увековечить свои красивые фамилии.
Пусть также принято условие, что каждый получает по улице и по пло
щади, причем, улица Ельцина должна заканчиваться площадью Ель
цина, улица Чубайса должна заканчиваться площадью Чубайса и т. д.
План города демократов будет иметь такой вид (рис. 5.5).
Поскольку в этом городе число улиц (ребер) равно числу площадей
(вершин), то цикломатическое число графа, соответствующего плану
города демократов первой волны, равно g = 1.
5.11. «Задача коммивояжера»
и «Задача о минимальной сети дорог»
Во все времена математики пытались заработать на своих уникаль
ных знаниях. Однако, похоже, что это удалось только венгерскому ма
тематику Рубику.
В 1859 году ирландский математик сэр Уильям Роуэн Гамильтон
изготовил и пытался продавать новую головоломку. Он взял один из
правильных многогранников (додекаэдр), в каждую вершину вбил ма
ленькие гвоздики, а к одному гвоздю привязал веревку. Задача состо
яла в том, чтобы, наматывая веревку на гвоздики, образовать цикл та
кой, чтобы веревка (путь) прошла бы через все вершины в точности по
одному разу. К сожалению, обыватели не заинтересовались головолом
кой сэра Гамильтона, зато ее запомнили математики. Со временем, пос
ле некоторого изменения условий, эта головоломка превратилась в
классическую теперь «Задачу коммивояжера», которая формулирует
ся так. Имеется n городов и задана таблица попарных расстояний меж
ду ними. Найти циклический путь обхода по одному разу всех горо
дов, при этом путь должен иметь минимально возможную длину. В бо
лее общих постановках на паре вершин задается значение некоторой
функции и требуется найти цикл, при котором общее значение функ
ции минимизируется или максимизируется.
В принципе, «Задача коммивояжера» была известна и российским
коробейникам. Они обходили деревни и, как правило (если верить Не
красову), никогда не заходили в одну и ту же деревню дважды. А ми
нимизировали они либо время обхода всех деревень, либо путь, либо
количество стоптанных лаптей.
«Задача коммивояжера» очень похожа по постановке на задачу Эй
лера о цикле в графе. Однако задача Эйлера была поставлена и блестя
ще решена Эйлером в его первой работе. Аналитическое решение «За
дачи коммивояжера» до сих пор не найдено, хотя имеются достаточно
хорошие решения, основанные на упорядоченном переборе (например,

Страницы