ТЕМА 4. Элементы теории графов
Основные разделы:
Применение
4.1 Основные определения и понятия
Основные определения и понятия
Определения
Смежность и инцидентность
Путь, цепь, контур
Путь, цепь, контур
Связность
Степень вершины графа
Число ребер графа
Следствия
Примеры
Однородным графом является и полный двудольный граф Km,m = G(V1,V2,E), |V1|=|V2 |= m, подграфы которого G1(V1,∅) и G2(V2,∅) –
Определение двудольного графа Km,n = G(V1,V2,E),
Эйлеровы и гамильтоновы цепи и циклы
Эйлеров цикл
Эйлерова церь
Алгоритм построения эйлерова цикла
Гамильтонов цикл
Изоморфизм графов
Свойства изоморфных графов
Планарность. Плоские графы
Гомеоморфизм графов
Теорема Понтрягина-Куратовского
Числа, характеризующие граф
Хроматическое число графа
Задача о раскраске географической карты
4.2. Способы задания графа
Матрица смежности
Для орграфа:
Для неорграфа:
Матрица смежности
Матрица инцидентности
Матрица инцидентности ориентированного графа "G"  ⃗("V" ,"E"  ⃗ )
Матрица инцидентности
Матрица инцидентности
Матрица инцидентности
v1: v2, v3, v4 v2: v4 v3: v4: v1, v3
e1: v1, v2 e2: v1, v3 e3: v1, v4 e4: v4, v1 e5: v2, v4 e6: v4, v3
4.3 Операции на графах и их свойства
1-4 Операции добавления и удаления
5-6 Операция отождествления вершин
Операции на графах 7-9
Операции на графах 7-9
Объединение графов-12
Объединение графов
Объединение графов
ПРИМЕР 2
ПРИМЕР 2 (продолжение)
ПРИМЕР 2 (продолжение)
13- Пересечение графов
Пересечение графов
Пересечение графов
ПРИМЕР 3
ПРИМЕР 3 (продолжение)
ПРИМЕР 3 (продолжение) V = V1V2 = {1, 2, 3}.
14- Соединение графов
Соединение графов
15- Композиция графов
Композиция графов
ПРИМЕР 5: На рисунке представлены графы G1, G2 и их композиции G1ᵒG2 и G2ᵒG1.
ПРИМЕР 5: Представление в табличной форме (списком дуг)
Пример 5 Матрицы смежности вершин исходных графов
Пример 5
16- Декартово произведение графов G= G1 □ G2
16- Декартово произведение графов G= G1 □ G2
16- Декартово произведение графов G= G1 □ G2
Задача о нефтепроводе: построение графа
Задача о нефтепроводе: графическая задача

Элементы теории графов

1. ТЕМА 4. Элементы теории графов

2. Основные разделы:

4.1 Основные определения и понятия
4.2 Способы задания графа
4.3 Операции над графами и их свойства
4.4 Деревья
4.5 Обходы
4.6 Алгоритмы на графах

3.

Теория графов как математическая
дисциплина сформировалась в
середине 30-х гг. ХХ ст. Термин
«граф» впервые появился в книге
выдающегося венгерского
математика Д. Кёнига в 1936 г.
При использовании понятия
«граф» в математике чаще всего
имеют в виду графическое
определение (задание) связей
между объектами произвольной
природы.
Денеш Кёнинг (1884-1944)

4. Применение

• Анализ и синтез цепей и систем;
• проектирование каналов связи и исследование
процессов передачи информации;
• построение контактных схем и исследование конечных
автоматов;
• календарное планирование промышленного
производства;

5.

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

6.

Связь с другими разделами
математики
• теория множеств,
• теория матриц,
• теория групп,
• математическая логика,
• численный анализ,
• теория вероятностей,
• топология,
• комбинаторный анализ

7. 4.1 Основные определения и понятия

Пусть
English     Русский Правила