Министерство образования и науки РФ

Красноярский государственный педагогический университет

им. В.П. Астафьева

Филиал КГПУ им. В.П.Астафьева в г. Канске

Тема:

«Гамильтоновы графы и циклы»

Реферат

ВЫПОЛНИЛА:

Вахрина Татьяна Юрьевна

Студентка 3 курса

ПРОВЕРИЛ: Кондрашов А.М.

преподаватель математики

Канск, 2012

Содержание

ВВЕДЕНИЕ…………………………………………………………………….. 3

1. Основные понятия и определения……………………………………....4

2. Условия существования гамильтонова цикла………………………….6

3. Задачи, связанные с поиском гамильтоновых циклов…………………8

4. Методы построения гамильтоновых циклов………………………….11

5. Алгебраический метод построения гамильтоновых циклов………....12

6. Примеры решения задач………………………………………………..14

ЗАКЛЮЧЕНИЕ………………………………………………………………..15

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ………………………….16

ПРИЛОЖЕНИЕ 1 : ИСТОРИЧЕСКАЯ СПРАВКА…………………….........17

Введение

Название «гамильтонов цикл» произошло от задачи «Кругосветное путешествие» предложенной ирландским математиком Вильямом Гамильтоном в 1859 году. Нужно было, выйдя из исходной вершины графа, обойти все его вершины и вернуться в исходную точку. Граф представлял собой укладку додекаэдра (додекаэдр - это многогранник, гранями которого служат 12 правильных пятиугольников; у него 20 вершин и 30 ребер; вершины и ребра додекаэдра составляют некоторый плоский граф), каждой из 20 вершин графа было приписано название крупного города мира.

1. Основные определения

Напомним основные определения из теории графов. Пусть V непустое конечное множество. Через V⁽²⁾ обозначим множество всех двухэлементных подмножеств из V. Графом G называется пара множеств (V, E), где E — произвольное подмножество из V⁽²⁾. Элементы множеств V и E называют соответственно вершинами и ребрами графа G. Граф G(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)-маршрут называется замкнутым.

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

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

Гамильтонов цикл не обязательно содержит все ребра графа. Ясно, что гамильтоновым может быть только связный граф и, что всякий гамильтонов граф является полугамильтоновым. Заметим, что гамильтонов цикл существует далеко не в каждом графе.

Замечание.

Любой граф G можно превратить в гамильтонов граф, добавив достаточное количество вершин. Для этого, например, достаточно к вершинам v₁,…,v_p графа G добавить вершины u₁,…,u_p и множество ребер {(v_i,u_i)}{(u_i,v_i+1)}.

Степенью вершины v называется число ребер d(v), инцидентных ей, при этом петля учитывается дважды. В случае ориентированного графа различают степень d_o(v) по выходящим дугам и d_i(v) — по входящим.