Введение в теорию графов. Задача о кёнигсберских мостах. Матрицы, векторы, множества. Представление задачи Эйлера в современных обозначениях

Тема: «Введение в теорию графов»

На основе анализа задачи выбрана следующая последовательность изложения:

1.  Введение в теорию графов.

1.1.  Задача о кёнигсберских мостах.

1.2.  Виды графов

1.3.  Матрицы, векторы, множества.

1.4.  Представление графов в ЭВМ:

1.4.1.  матрицы смежности,

1.4.2.  матрицы инциденций,

1.4.3.  списки смежности,

1.4.4.  массивы дуг.

1.5.  Представление задачи Эйлера в современных обозначениях.

2.  Дополнительные понятия.

2.1.  Подграфы.

2.2.  Локальные характеристики вершин.

2.3.  Маршруты.

2.4.   Цепи.

2.5.   Циклы.

2.6.   Связность.

3.  Поиск минимального маршрута.

3.1.  Волновой алгоритм.

3.2.  Алгоритм Флойда.

3.3.  Алгоритм Дейкстры.

4.  Остовные деревья.

4.1.  Алгоритм построения остовного дерева.

4.2.  Алгоритм Краскала.

5.  Циклы в графах

5.1.   Цикломатическое число.

5.2.  Эйлеровы циклы.

5.2.1.  Эйлеровы графы.

5.2.2.  Теорема о количестве эйлеровых графов.

5.3.   Циклы Гамильтона.

5.3.1.  Графы Гамильтона.

5.3.2.  Теорема о количестве гамильтоновых графов.

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

5.5.  Поиск циклов в графе.

5.6.  Методы поиска циклов Эйлера.

6.  Раскраска графов.

6.1.  Хроматическое число.

6.2.  Планарность графов.

6.3.  Теорема о пяти красках.

6.4.  Алгоритмы раскрашивания

6.5.  Точный алгоритм  раскрашивания.

6.6.  Приближённый алгоритм раскрашивания №1.

6.6.1.  Анализ алгоритма №1.

6.7.  Приближённый алгоритм раскрашивания №2.

7.  Изоморфизм графов.

7.1.  Поиск изоморфизма на основе обобщения локальных характеристик вершин.

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

Список иллюстративного материала (с указанием анимированного):

Номер раздела	Иллюстрация	Анимация
1	Задача о кёнигсберских мостах	‑
	Орграф, псевдограф, мультиграф, гиперграф, взвешенный граф	‑
	Матрицы: смежности, инциденций	‑
	Списки смежности	‑
	Массивы дуг	‑
	Задача Эйлера	‑
2	Подграф	‑
	Пример цепи	‑
	Пример цикла	‑
3	Волновой алгоритм	+
	Алгоритм Флойда	+
	Алгоритм Дейкстры	+
4	Остовное дерево	‑
	Алгоритм Краскала	+
5	Эйлеров граф
	Граф Гамильтона
	Задача коммивояжера	+
	Поиск цикла Эйлера	+
6	К теореме о пяти красках	‑
	Точный алгоритм раскрашивания	+
	Приближённый алгоритм раскрашивания №1	+
	Приближённый алгоритм раскрашивания №2	+
7	Изоморфизм графов	‑

Анимации могут быть выполнены как в формате GIF, так и при помощи Flash или интерактивными Java-апплетами, где обучаемый может влиять на ход процесса.

Дополнительно могут быть использована система проверки знаний по пройденному материалу.

Список ссылок на ресурсы: