X1 X4 X5

Задание 10.

Определить, является ли граф гамильтоновым (направление связей не учитывать). Если – да, то указать гамильтонов маршрут, если – нет, то, применяя минимальное количество известных операций на графах, преобразовать данный граф в гамильтонов граф.

Решение:

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

Данный граф является гамильтоновым. Действительно:

Х2 Х3

X1 X4 X5

Условия задач и варианты заданий для семестровой работы №2.

1. Задать граф следующими способами: перечислением, матрицами смежности и инцидентности.

2. Определить следующие основные характеристики графа:

число ребер и дуг; число вершин;коэффициент связности графа;степени всех вершин;цикломатическое число графа.

3. Определить, является ли данный граф:

- планарным или плоским графом (обосновать ответ и выполнить обратное преобразование);

- двудольным графом (обосновать ответ и, если необходимо, то достроить до двудольного графа);

- деревом (обосновать ответ и, в случае циклического графа, привести один из вариантов основного дерева);

- псевдографом или мультиграфом, или простым графом (обосновать ответ и выполнить необходимые преобразования).

4.Привести пример подграфа, частичного графа и частичного подграфа.

5.Произвести реберную и вершинную раскраски графа с определением вершинного и реберного хроматического числа.

6.Упорядочить граф матричным способом и построить порядковую функцию, функцию Гранди.

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

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

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

10.Определить, является ли граф гамильтоновым(направление связей не учитывать). Если – да, то указать гамильтонов путь, если – нет, то, применяя минимальное количество известных операций на графах, преобразовать данный граф в гамильтоновый граф.

Варианты заданий для семестровой работы № 2

Вариант 1	Вариант 2	Вариант 3	Вариант 4
Вариант 5	Вариант 6	Вариант 7	Вариант 8
Вариант 9	Вариант 10	Вариант 11	Вариант 12
Вариант 13	Вариант 14	Вариант 15	Вариант 16
Вариант 17	Вариант 18	Вариант 19	Вариант 20
Вариант 21	Вариант 22	Вариант 23	Вариант 24
Вариант 25	Вариант 26	Вариант 27	Вариант 28
Вариант 29	Вариант 30	Вариант31

СПИСОК ЛИТЕРАТУРЫ

1. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике.– М.: Наука,1977.

2. Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика. – М.: Наука. Физматлит, 2000.

3. Информатика: Энциклопедический словарь для начинающих /Сост. Д.А. Поспелов. – М.: Педагогика – Пресс, 1994.

4. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат,1988.

5. Лихтарникова Л.М.,Сукачева Т.Г. Математическая логика / Курс лекций. – СПб. : Издательство «Лань», 1998.

6. Логинов Б.М. Лекции и упражнения по курсу «Введение в дискретную математику». – Калуга: МГТУ им.Н.Э. Баумана, 1998.

7. Нефедов В.Н., Осипова В.А. Курс дискретной математики: Учеб. пособие.–М.: Изд-во МАИ,1992.

8. Савельев А.П. Прикладная теория цифровых автоматов. М.: Наука,1985.

9. Фудзисава Т., Касами Т. Математика для радиоинженеров: Теория дискретных структур: Пер. с япон. – М.: Радио и связь,1984.

10. Муха Ю.П., Авдеюк О.А., Скворцов М.Г. Дискретная математика. Конспект лекций: учеб. пособие/ ВолгГТУ.– Волгоград, 2005.

11. Муха Ю.П., Авдеюк О.А. Математическая логика и теория алгоритмов. Конспект лекций : Учеб. пособие/ ВолгГТУ.– Волгоград, 2005.