Теория графов. Лекция. 2017

↑

Вводная лекция

1. Графы. Определение

2. Пути и маршруты

2.1. Весаи длина пути

3. Петли, ориентированные циклы и циклы

4. Степени вершины

5. Подграфы

6. Типы графов

7. Сильно связные графы и компоненты графа

8. Матричные представления

8.1. Матрица смежности

8.2. Матрица инциденций

Лекция № 2 Достижимость и связность в графах

1. Компоненты графа

2. Матрицы достижимостей и контрдостижимостей

3. Нахождение сильных компонент и построение конденсации

4. Базы и антибазы

5. Применение к исследованию структуры организаций

Лекция № 3 Знаковые графы и теория структурного баланса

1. Знаковые графы

2. Баланс в малых группах.

3. Теорема о структуре.

4. Использование знаковых орграфов в качестве средства моделирования сложных систем.

Лекция № 4 Раскраски

1. Введение

2. Некоторые теоремы и оценки, относящиеся к хроматическим числам

2.1. Нижние оценки для .

2.2. Верхние оценки для .

2.3. Гипотеза четырех красок.

3. Приближенные алгоритмы раскрашивания.

4. Обобщения и приложения.

4.1. Простая задача размещения (загрузки).

4.2. Составление графиков осмотра(проверки).

4.3. Распределение ресурсов.

Лекция № 5 КРАТЧАЙШИЕ ПУТИ В ГРАФАХ

Постановка задачи

Алгоритм Дейкстры (случай неотрицательной матрицы весов)

Алгоритм Форда (случай общей матрицы весов)

Алгоритм Флойда (кратчайшие пути между всеми парами вершин)

Применение к сетевому планированию и управлению

Лекция № 6 РАЗМЕЩЕНИЕ ЦЕНТРОВ И МЕДИАН В ГРАФАХ

Разделения графа

Центр и радиус графа

Абсолютный центр графа

Кратные центры (р-центры) графа

Практическое применение задачи размещения центров

Медиана графа

Кратные медианы (р-медианы) графа

Приближенный алгоритм нахождения кратных медиан графа

Практическое применение задачи размещения медиан

Лекция № 7 ДЕРЕВЬЯ

Основные понятия

Построение всех остовных деревьев графа

Элементарные преобразования деревьев

Процедура порождения всех деревьев неориентированного графа

Кратчайший остов графа

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

Алгоритм Прима

Книги и учебники по дисциплине Теория графов:

- Аналитическая геометрия - Вариационное исчисление - Векторный и тензорный анализ - Высшая геометрия - Высшая математика - Вычислительная математика - Дискретная математика - Дифференциальное и интегральное исчисление - Дифференциальные уравнения - Исследование операций - История математики - Комплексное исчисление - Линейная алгебра - Линейное программирование - Математическая логика - Математическая физика - Математический анализ - Пределы - Ряды - Статистика - Теория вероятностей - Теория графов - Теория игр - Теория принятия решений - Теория случайных процессов - Теория чисел - Финансовая математика - Функциональный анализ -

- Антропология - Астрономия - Безопасность жизнедеятельности - Библиотечное дело - Биология - Военное дело - География - Зоология - История - Конфликтология - Культурология - Литература - Математика - Медицина - Педагогика - Политология - Право России - Право України - Психология - Религоведение - СМИ и журналистика - Социология - Технические науки - Транспорт - Физика - Философия - Финансы - Экология - Экономика - Этнография и демография - Юриспруденция - Языкознание -