Мещанинов Д. Г. Лекции по теории графов и комбинаторике.

Краткая выдержка из текста работы (Аннотация)

ГАМИЛЬТОНОВЫ ЦИКЛЫ.

Определение 2.

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

Утверждение 1.

Если в графе имеется точка сочленения, то Гамильтонова цикла не существует.

Замечание.

Существование Эйлерова и Гамильтонова циклов не связаны.

Замечание.

Почти все графы не имеют Эйлерова или Гамильтонова цикла.

Содержание работы

Лекция № 1.

ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ.

Лекция № 2.ЭЙЛЕРОВЫ ЦИКЛЫ.

ГАМИЛЬТОНОВЫ ЦИКЛЫ.

ДЕРЕВЬЯ И ОСТОВЫ

Лекция № 3. ОСТОВЫ.

Лекция № 4. ЗАДАЧА О МИНИМАЛЬНОМ ОСТОВЕ.

ФУНДАМЕНТАЛЬНЫЕ ЦИКЛЫ И РАЗРЕЗЫ.

Лекция № 5. НЕЗАВИСИМЫЕ И ДОМИНИРУЮЩИЕ

МНОЖЕСТВА ВЕРШИН.

Лекция № 6.ИЗОМОРФНЫЕ, ПЛОСКИЕ И ПЛАНАРНЫЕ ГРАФЫ.

Лекция № 7.РАСКРАСКА ГРАФА.

Лекция № 8.ПРАВИЛЬНЫЙ ГРАФ.

ПАРОСОЧЕТАНИЯ В ДВУДОЛЬНЫХ ГРАФАХ.

Лекция № 9.СПОСОБЫ ПОСТРОЕНИЯ СОВЕРШЕННОГО ПАРОСОЧЕТАНИЯ.

Лекция № 10.ЗАДАЧА О КРАТЧАЙШЕМ ПУТИ.

Лекция № 11.ПОТОКИ В СЕТЯХ.

Лекция № 12.КОМБИНАТОРНЫЙ АНАЛИЗ.

Лекция № 13.ПРОИЗВОДЯЩИЕ ФУНКЦИИ.

Лекция № 14.ЭКСПОНЕНЦИАЛЬНЫЕ ПРОИЗВОДЯЩИЕ ФУНКЦИИ.

Лекция № 15.ЛИНЕЙНЫЕ РЕКУРРЕНТНЫЕ УРАВНЕНИЯ.

Лекция № 16.МЕТОД ВКЛЮЧЕНИЙ-ИСКЛЮЧЕНИЙ.

Использованная литература

1. Отсутствует

Другие похожие работы

• Контрольная - Контрольная работа по теме «Интегралы»
• Контрольная - Методы решения нелинейных уравнений
• Контрольная - Контрольная работа №1
• Контрольная - Применение экономико-математического моделирования для оптимизации программы выпуска, МАИ
• Шпаргалка - Уравнения фигур
• Реферат - ТЕОРИЯ УСТОЙЧИВОСТИ
• Контрольная - Высшая математика
• Контрольная - Дана система линейных уравнений х1 + 2х2 + 4х3 = 31, 5х1 + х2 + 2х3 = 20, 3х1 – х2 + х3 = 10. Доказать ее совместность и решить двумя
• Контрольная - 4 задачи по исследованию операций в экономике (АТИСО). Используя графический метод, найти решение следующей задачи линейного программирования
• Контрольная - Контрольная работа - 2