Размещено на http://www.allbest.ru/

• План
• Введение
• 1. Понятие Гамильтонова графа
• 1.1 Основные понятия теории графов
• 1.2 Свойства маршрутов, цепей и циклов
• 1.3 Понятие гамильтонова графа. Теорема Дирака
• 2. Задача о коммивояжере
• 2.1 Историческая справка
• 2.2 Постановка задачи о коммивояжере
• 2.3 Методы решения задачи о Коммивояжере
• 2.4 Метод ветвей и границ
• Заключение
• Список использованной литературы

Введение

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

Переборные алгоритмы не эффективны (в расчете на худшую задачу), поэтому успех в решении каждой конкретной задачи существенным образом зависит от способа организации перебора.

Знаменитая задача коммивояжера, поставленная еще в 1934 г., является одной из самых важнейших задач в теории графов. В своей области (оптимизации дискретных задач) задача коммивояжера служит своеобразным полигоном, на котором испытываются все новые методы.

Целью исследования является нахождение наиболее точного алгоритма поиска оптимального пути.

Задачи исследования:

1. Изучить основополагающие понятия: граф, маршрут, цепь, контур, цикл.

2. Рассмотреть известные способы решения задачи о коммивояжере.

3. Обобщить полученные результаты.

Прaктичeскaя знaчимoсть рaбoты зaключaeтся в тoм, чтo рeзyльтaты исслeдoвaния мoгyт быть испoльзoвaны во многих практических задачах.

Стрyктyрa рaбoты: рaбoтa сoстoит из ввeдeния, двyх глaв, зaключeния и спискa литeрaтyры.

1. Понятие Гамильтонова графа

1.1 Основные понятия теории графов

Пусть V - непустое множество, V⁽²⁾ - множество всех его двухэлементных подмножеств. Пара (V,E), где E - произвольное подмножество множества V⁽²⁾, называется простым графом (неориентированным графом). Элементы множества V называются вершинами графа, а элементы множества E - ребрами. Итак, граф - это конечное множество V вершин и множество E ребер, EV⁽²⁾.

Например:

V = {a,b,c,d}; V⁽²⁾ = {{a,b},{a,c},{a,d},{b,c},{b,d},{c,d}}

G₁ = V⁽²⁾

G₂= {{a,d},{b,d},{c,d}}

Рис. 1 Граф G₁ и Граф G₂

Термин «граф» впервые появился в книге выдающегося венгерского математика Д. Кёнига в 1936 г., хотя начальные задачи теории графов восходят еще к Эйлеру (XVIII в.). Множества вершин и ребер графа G обозначается соответственно V(G) и E(G). Вершины и ребра графа называются его элементами. Число |V(G)| вершин графа G называется его порядком и обозначается |G|. Если |G|=n, |EG|=m, то граф называют (n, m)-графом. Говорят, что две вершины u и v графа смежны, если множество {u, v} является ребром, и не смежны в противном случае. Если e={u, v} - ребро, то вершины u и v называют его концами. В этой ситуации говорят также, что ребро e соединяет вершины u и v. Два ребра называются смежными, если они имеют общий конец. Вершина v и ребро e называются инцидентными, если v является одним из концов ребра e, и не инцидентными в противном случае. Заметим, что смежность есть отношение между однородными элементами графа, тогда как инцидентность является отношением между разнородными элементами.

Маршрутом (или путем) в графе G называется чередующаяся последовательность вершин и ребер v₀, e₁, v₁, …, v_t?1, e_t, v_t+1, в которой e_i = v_i?1v_i (1 ? i ? t). Такой маршрут кратко называют (v₀, v_t)-маршрутом и говорят, что он соединяет v₀ c v_t; в свою очередь вершины v₀, v_t -- это концевые вершины указанного маршрута. Длиной маршрута называют количество содержащихся в нем ребер. Заметим, что в обыкновенном графе маршрут полностью определяется последовательностью v₀, v₁, …, v_t своих вершин. Если v₀=v_t, то (v₀, v_t)-маршрут называется замкнутым.

Цепь -- это маршрут без повторяющихся ребер. Цепь называется простой цепью, если в ней нет повторяющихся вершин, кроме, совпадающих концевых вершин. Замкнутая простая цепь называется циклом (или контуром).

1.2 Свойства маршрутов, цепей и циклов

1) Всякий незамкнутый (u, v)- маршрут, содержит в себе простую (u, v)- цепь. Вчастности, любая (u, v)- цепь, содержит в себе простую (u, v)- цепь. Причем, если (u, v)- маршрут содержит в себе вершину w (w?u и w?v), то в общем случае, простая (u, v)- цепь может не содержать в себе вершину w.

2) Всякий непростой цикл можно разбить на два или более простых. Причем для замкнутого маршрута такое утверждение не верно.

3) Всякая непростая (u, v)- цепь, может быть разбита на простую (u, v)- цепь и один или более простых циклов. Причем для незамкнутого маршрута такое утверждение не верно.

4) Для любых трех вершин u, w, v из существования (u, w)- цепи их и (w, v)- цепи,следует существование (u, v)- цепи. Причем может не существовать (u,v)- цепи, содержащей вершину w.

5) Объединение двух несовпадающих простых (u, v)- цепей содержит простой цикл.

6) Если граф содержит 2 несовпадающих цикла с общим ребром e, то после удаления этого ребра граф по-прежнему содержит цикл.

1.3 Понятие гамильтонова графа. Теорема Дирака

Граф называется гамильтоновым, если в нем имеется простой цикл, содержащий каждую вершину этого графа. Сам этот цикл также называется гамильтоновым. Гамильтоновой называют и простую цепь, содержащую каждую вершину графа. Слово «гамильтонов» в этих определениях связано с именем известного ирландского математика У. Гамильтона, которым в 1859 году предложена следующая игра «Кругосветное путешествие». Каждой из 20 вершин додекаэдра (рис. 1) приписано название одного из крупных городов мира.

рис. 2

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

Теорема Оре (О.Оре, 1960). Если для любой пары u и v несмежных вершин графа G порядка n?3 выполняется неравенство deg u+deg v?n, то G - гамильтонов граф.

Теорема Дирака (следствие теоремы Оре) (Г.Дирак,1952 г.). Если |G|=n?3 и для любой вершины v графа G выполняется неравенство deg v?n/2, то G - гамильтонов граф.

Лемма (о длине цикла)

Пусть - произвольный неориентированный граф и - минимальная степень его вершин. Если , то в графе существует цикл длиной .

Доказательство:

Рассмотрим путь максимальной длины . Все смежные с вершины лежат на . Обозначим . Тогда . Цикл имеет длину

Доказательство теоремы Дирака

Пусть - цикл наибольшей длины в графе . По лемме его длина . Если - гамильтонов, то теорема доказана. Предположим обратное, т. е. . Рассмотрим путь наибольшей длины . Заметим, что по условию , а значит и каждая вершина из смежна с некоторыми вершинами из . Заметим, что вершина не может быть смежна:

· с вершинами из , расстояние от которых до (по ) не превышает m. Действительно, пусть вершина и расстояние от до по циклу меньше либо равно . Тогда этот участок цикла можно заменить на , длина которого . Таким образом образуется цикл большей длины, что противоречит предположению о максимальности цикл .

· двум смежным вершинам на . Пусть и . Тогда заменив ребро на , увеличим длину цикла на .

· вершинам из , поскольку максимальный.

Получаем .

Противоречие.

граф теорема коммивояжер

2. Задача о коммивояжере

2.1 Историческая справка

Точно неизвестно, когда проблему коммивояжера исследовали впервые. Однако, известна изданная в 1832 году книга с названием «Коммивояжер -- как он должен вести себя и что должен делать для того, чтобы доставлять товар и иметь успех в своих делах -- советы старого курьера» в которой описана проблема, но математический аппарат для её решения не применяется. Зато в ней предложены примеры маршрутов для некоторых регионов Германии и Швейцарии.

Ранним вариантом задачи может рассматриваться игра Уильяма Гамильтона 19 века, которая заключалась в том, чтобы найти маршруты на графе с 20 узлами. Первые упоминания в качестве математической задачи на оптимизацию принадлежат Карлу Менгеру, который сформулировал её на математическом коллоквиуме в 1930 году так: «Мы называем проблемой посыльного (поскольку этот вопрос возникает у каждого почтальона, в частности, ее решают многие путешественники) задачу найти кратчайший путь между конечным множеством мест, расстояние между которыми известно.»

Вскоре появилось известное сейчас название задача странствующего торговца, которую предложил Гаслер Уитни из Принстонского университета.

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

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

В 1950-е и 1960-е годы задача коммивояжера привлекла внимание ученых в США и Европе. Важный вклад в исследование задачи принадлежит Джорджу Данцигу, Делберту Рею Фалкерсону и Селмеру Джонсону, которые в 1954 году в институте RAND Corporation сформулировали задачу в виде задачи дискретной оптимизации и применили для ее решения метод отсечений. Используя этот метод, они построили путь коммивояжера для одной частной постановки задачи с 49 городами и обосновали его оптимальность. В 1960-е и 1970-е годы задача изучалась многими учеными как теоретически, так и с точки зрения ее приложений в информатике, экономике, химии и биологии.

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

Больших успехов удалось достичь в конце 1970-х и 1980-х годах, когда Мартин Грётчел, Манфред Падберг и Джованни Ринальди и другие, с применением новых методов деления плоскостью, ветвей и границ вычислили решение для отдельного случая задачи с 2393 городами.

В 1990-е годы Дэвид Аплгейт, Роберт Биксби, Вашека Шватал и Уильям Кук установили рекорды по программе Конкорд. Герхард Райнельт создал TSPLIB -- набор стандартизованных экземпляров задачи коммивояжера различной степени сложности для сравнения результатов работы различных групп исследователей. В марте 2005 года задача с 33 810 узлами была решена программой Конкорд: был вычислен путь длиной в 66 048 945 и доказано отсутствие более коротких путей. В апреле 2006 было найдено решение для экземпляра с 85 900 узлами. Используя методы декомпозиции, можно вычислить решения для случаев задачи с миллионами узлов, длина которых менее чем на 1 % больше оптимальной.

2.2 Постановка задачи о коммивояжере

Классическая постановка задачи о коммивояжере выглядит следующим образом:

Имеется N городов, которые должен обойти коммивояжер по кратчайшему пути. При этом на его маршрут накладывается два ограничения:

· маршрут должен быть замкнутым, то есть коммивояжер должен вернуться в тот город, из которого он начал движение;

· в каждом из городов коммивояжер должен побывать точно один раз, то есть надо обязательно обойти все города, при этом, не побывав ни в одном городе дважды.

Целью решения является нахождения самого короткого маршрута, удовлетворяющего всем условиям

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

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

1. Доставка продуктов в магазины с оптового склада производителя (в этом случае может быть более уместна постановка транспортной задачи -- доставка в несколько магазинов с нескольских складов).

2. Доставка бутилированной воды

3. Мониторинг объектов (базовые станции сотовых операторов, нефтянные вышки)

4. Пополнение банкоматов наличными деньгами

5.Сбор сотрудников для доставки вахтовым методом

6.Расклейка афиш

7. И т.д.

2.3 Методы решения задачи о Коммивояжере

Задачи коммивояжера решаются посредством различных методов, выведенных в результате теоретических исследований. Все эффективные методы (сокращающие полный перебор) -- методы эвристические. В большинстве эвристических методов находится не самый эффективный маршрут, а приближённое решение. Зачастую востребованы алгоритмы постепенно улучшающие некоторое текущее приближенное решение. Выделяют следующие группы методов решения задач коммивояжера, которые относят к простейшим:

· Полный перебор;

Полный перебор (или метод «грубой силы») -- метод решения задачи путем перебора всех возможных вариантов. Сложность полного перебора зависит от количества всех возможных решений задачи. Если пространство решений очень велико, то полный перебор может не дать результатов в течение нескольких лет или даже столетий.

· Случайный перебор;

Обычно выбор решения можно представить последовательностью выборов. Если делать эти выборы с помощью какого-либо случайного механизма, то решение находится очень быстро, так что можно находить решение многократно и запоминать «рекорд», т. е. наилучшее из встретившихся решений. Этот наивный подход существенно улучшается, когда удается учесть в случайном механизме перспективность тех или иных выборов, т. е. комбинировать случайный поиск с эвристическим методом и методом локального поиска. Такие методы применяются, например, при составлении расписаний для Аэрофлота.

· Жадные алгоритмы (метод ближайшего соседа, метод включения ближайшего города, метод самого дешевого включения);

Жадный алгоритм - алгоритм нахождения наикратчайшего расстояния путём выбора самого короткого, ещё не выбранного ребра, при условии, что оно не образует цикла с уже выбранными рёбрами. «Жадным» этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность. При решении задачи коммивояжера жадный алгоритм превратится в стратегию «иди в ближайший (в который еще не входил) город». Жадный алгоритм, очевидно, бессилен в этой задаче. Рассмотрим для примера сеть (рис. 2), представляющую узкий ромб. Коммивояжер стартует из города 1. Алгоритм «иди в ближайший город» выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной диагонали ромба. В результате получится не кратчайший, а длиннейший тур.

Рис. 3

· Метод минимального остовного дерева (деревянный алгоритм);

В основе алгоритма лежит утверждение: «Если справедливо неравенство треугольника, то для каждой цепи верно, что расстояние от начала до конца цепи меньше (или равно) суммарной длины всех ребер цепи». Это обобщение расхожего убеждения, что прямая короче кривой. Деревянный алгоритм для решения задачи коммивояжера будет следующим: строится на входной сети задачи коммивояжера кратчайшее остовное дерево и удваиваются все его ребра. В результате получаем граф -- связный с вершинами, имеющими только четные степени. Затем строится эйлеров цикл, начиная с вершины 1, цикл задается перечнем вершин. Просматривается перечень вершин, начиная с 1, и зачеркивается каждая вершина, которая повторяет уже встреченную в последовательности. Останется тур, который и является результатом алгоритма.

Доказано, что деревянный алгоритм ошибается менее чем в два раза, поэтому такие алгоритмы называют приблизительными, а не просто эвристическими.

· Метод имитации отжига.

Экзотическое название данного алгоритма связано с методами имитационного моделирования в статистической физике, основанными на технике Монте-Карло. Исследование кристаллической решетки и поведения атомов при медленном остывании тела привело к появлению на свет вероятностных алгоритмов, которые оказались чрезвычайно эффективными в комбинаторной оптимизации. Впервые это было замечено в 1983 году. Сегодня этот алгоритм является популярным как среди практиков благодаря своей простоте, гибкости и эффективности, так и среди теоретиков, поскольку для данного алгоритма удается аналитически исследовать его свойства и доказать асимптотическую сходимость. Алгоритм имитации отжига относится к классу пороговых алгоритмов локального поиска. На каждом шаге этого алгоритма для текущего решения i_k в его окрестности N(i_k) выбирается некоторое решение j и, если разность по целевой функции между новым и текущим решением не превосходит заданного порога t_k, то новое решение j заменяет текущее. В противном случае выбирается новое соседнее решение. На практике применяются различные модификации более эффективных методов:

· Метод ветвей и границ;

Метод ветвей и границ предложен в 1963 году группой авторов Дж. Литлом, К. Мурти, Д. Суини, К. Кэролом. Широко используемый вариант поиска с возвращением, фактически является лишь специальным частным случаем метода поиска с ограничениями⁴. Ограничения в данном случае основываются на предположении, что на множестве возможных и частичных решений задана некоторая функция цены и что нужно найти оптимальное решение, т.е. решение с наименьшей ценой. Для применения метода ветвей и границ функция цены должна обладать тем свойством, что цена любого частичного решения не превышает цены любого расширения этого частичного решения (Заметим, что в большинстве случаев функция цены неотрицательна и даже удовлетворяет более сильному требованию). Столь большой успех применения данного метода объясняется тем, что авторы первыми обратили внимание на широту возможностей метода, отметили важность использования специфики задачи и сами воспользовались спецификой задачи коммивояжера.

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

· Метод генетических алгоритмов;

«Отцом-основателем» генетических алгоритмов считается Джон Холланд, книга которого «Адаптация в естественных и искусственных системах» (1975) является основополагающим трудом в этой области исследований. Генетический алгоритм -- это эвристический алгоритм поиска, используемый для решения задач оптимизации и моделирования путём случайного подбора, комбинирования и вариации искомых параметров с использованием механизмов, напоминающих биологическую эволюцию. Является разновидностью эволюционных вычислений. Отличительной особенностью генетического алгоритма является акцент на использование оператора «скрещивания», который производит операцию рекомбинации решений-кандидатов, роль которой аналогична роли скрещивания в живой природе. Генетические алгоритмы служат, главным образом, для поиска решений в многомерных пространствах поиска.

· алгоритм муравьиной колонии.

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

2.4 Метод ветвей и границ

Для решения задачи коммивояжера методом ветвей и границ необходимо выполнить следующую последовательность действий:

(1) Построение матрицы с исходными данными.

(2) Нахождение минимума по строкам.

(3) Редукция строк.

(4) Нахождение минимума по столбцам.

(5) Редукция столбцов.

(6) Вычисление оценок нулевых клеток.

(7) Редукция матрицы.

(8) Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9.

(9) Вычисление итоговой длины пути и построение маршрута.

Подробная методика решения

В целях лучшего понимания задачи будем оперировать не понятиями графа, его вершин и т.д., а понятиями простыми и максимально приближенными к реальности: вершины графа будут называться «города», ребра их соединяющие - «дороги».

Итак, методика решения задачи коммивояжера:

1. Построение матрицы с исходными данными

Сначала необходимо длины дорог соединяющих города представить в виде следующей таблицы:

Таблица 1

В нашем примере у нас 4 города и в таблице указано расстояние от каждого города к 3-м другим, в зависимости от направления движения (т.к. некоторые ж/д пути могут быть с односторонним движением и т.д.).

Расстояние от города к этому же городу обозначено буквой M. Также используется знак бесконечности. Это сделано для того, чтобы данный отрезок путь был условно принят за бесконечно длинный. Тогда не будет смысла выбрать движение от 1-ого города к 1-му, от 2-ого ко 2-му, и т.п. в качестве отрезка маршрута.

2. Нахождение минимума по строкам

Находим минимальное значение в каждой строке (di) и выписываем его в отдельный столбец.

Таблица 2

3. редукция строк

Производим редукцию строк - из каждого элемента в строке вычитаем соответствующее значение найденного минимума (di).

Таблица 3

В итоге в каждой строке будет хотя бы одна нулевая клетка.

4. Нахождение минимума по столбцам

Таблица 4

Далее находим минимальные значения в каждом столбце (dj). Эти минимумы выписываем в отдельную строку.

5. редукция столбцов

Вычитаем из каждого элемента матрицы соответствующее ему dj.

Таблица 5

В итоге в каждом столбце будет хотя бы одна нулевая клетка.

6. Вычисление оценок нулевых клеток

Для каждой нулевой клетки получившейся преобразованной матрицы находим «оценку». Ею будет сумма минимального элемента по строке и минимального элемента по столбцу, в которых размещена данная нулевая клетка. Сама она при этом не учитывается. Найденные ранее di и dj не учитываются. Полученную оценку записываем рядом с нулем, в скобках.

Таблица 6

И так по всем нулевым клеткам:

Таблица 7

7. редукция матрицы

Выбираем нулевую клетку с наибольшей оценкой. Заменяем ее на «М». Мы нашли один из отрезков пути. Выписываем его (от какого города к какому движемся, в нашем примере от 4-ого к 2-му).

Таблица 8

Ту строку и тот столбец, где образовалось две «М» полностью вычеркиваем. В клетку соответствующую обратному пути ставим еще одну букву «М» (т.к. мы уже не будем возвращаться обратно).

Таблица 9

8. если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9

Если мы еще не нашли все отрезки пути, то возвращаемся ко 2-му пункту и вновь ищем минимумы по строкам и столбцам, проводим их редукцию, считаем оценки нулевых клеток и т.д.

Если все отрезки пути найдены (или найдены еще не все отрезков, но оставшаяся часть пути очевидна) - переходим к пункту 9.

9. вычисление итоговой длины пути и построение маршрута

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

В нашем примере маршрут получился следующий: 4 > 2 > 3 > 1 > 4.

Общая длина пути: L = 30.

Заключение

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

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

Список использованной литературы

1. Кирсанов М.Н. «Графы в Maple», М. Физматлит, 2007.

2. Зыков А.А. «Основы теории графов» , М. «Вузовская книга», 2004

3. Уилсон Р. «Введение в теорию графов» , М. «Мир», 1977

4. Берж К. "Теория графов и ее применение", М., ИЛ, 1962;

5. Гарднер М. "Математические досуги", М. "Мир", 1972(глава 35);

6. "В помощь учителю математики", Йошкар-Ола, 1972 (ст. "Изучение элементов теории графов");

7. Олехник С.Н., Нестеренко Ю.В., Потапов М.К. "Старинные занимательные задачи", М. "Наука", 1988;

8. Гарднер М. "Математические головоломки и развлечения", М. "Мир",1971;

9. Оре О. "Графы и их применения", М. "Мир", 1965;

10. Зыков А.А. "Теория конечных графов", Новосибирск, "Наука", 1969;

11. Реньи А., "Трилогия о математике", М., "Мир", 1980.

Размещено на Allbest.ru

...