ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ
Граф
Классификация графов
Классификация графов
Лемма о рукопожатиях
Задача 1
Суграф и подграф
Применение графов
Маршруты в графе
Связный граф
Эйлеров цикл
Гамильтонов цикл
Методы представления графов в памяти ЭВМ
Матрица смежности
Задача 2
Задача 3
Задача 4
Матрица инциденций
Расстояние в графе
Расстояние в графе
Задача 5
Задача 6
Основные виды графов
Двудольный граф
Двудольный граф
Дерево
Полный граф
Операции над графами
Задача 7
Задача 8
Задача 9
Задача 10
Взвешенный граф
Задача 11
Задача 12
Алгоритм Краскала
Алгоритм Прима
Алгоритм Прима
Задача поиска кратчайшего пути в графе
Алгоритм Дейкстры
Алгоритм Дейкстры
Алгоритм Дейкстры
Обход графа в глубину (Depth-first search, DFS)
Поиск в глубину (Depth-first search, DFS)
Вычислительная сложность алгоритма обхода в глубину
Метод поиска в глубину G = (V, E)
Обход в ширину
Метод поиска в ширину (BFS, Breadth-first search)
Топологическая сортировка
Топологическая сортировка
Метод топологической сортировки с помощью обхода в глубину
Задача коммивояжера (задача о китайском почтальоне)
Задача коммивояжера
Виды задач коммивояжера
Виды задач коммивояжера
Математическая модель задачи коммивояжера
Математическая модель задачи
Метод ветвей и границ
Алгоритм решения задачи коммивояжера методом ветвей и границ
Алгоритм решения задачи коммивояжера методом ветвей и границ
Алгоритм решения задачи коммивояжера методом ветвей и границ
Алгоритм решения задачи коммивояжера методом ветвей и границ
Алгоритм решения задачи коммивояжера методом ветвей и границ
Алгоритм решения задачи коммивояжера методом ветвей и границ
Алгоритм решения задачи коммивояжера
Алгоритм решения задачи коммивояжера методом ветвей и границ
3.00M

ГрафыЛекция

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

2. Граф

Графом G называется пара множеств G = (X, Е),
где Х— непустое множество вершин {хх, х2, ..., х„}, а
элементами множества Е являются некоторые
двухэлементные подмножествах, т.е. множества ребер Е
= {(
English     Русский Правила