Комбинаторика
<<  Более сложные задачи по комбинаторике Комбинаторика  >>
Краткое введение в теорию графов
Краткое введение в теорию графов
Определение графа
Определение графа
Дерево
Дерево
Обход дерева в ширину
Обход дерева в ширину
Обход дерева в глубину
Обход дерева в глубину
Остовное дерево графа
Остовное дерево графа
Классификация ребер при поиске в глубину
Классификация ребер при поиске в глубину
Топологическая сортировка
Топологическая сортировка
Двусвязные компоненты
Двусвязные компоненты
Поиск точек сочленения
Поиск точек сочленения

Презентация на тему: «Краткое введение в теорию графов». Автор: iceslice. Файл: «Краткое введение в теорию графов.ppt». Размер zip-архива: 212 КБ.

Краткое введение в теорию графов

содержание презентации «Краткое введение в теорию графов.ppt»
СлайдТекст
1 Краткое введение в теорию графов

Краткое введение в теорию графов

Салищев С. И.

2 Определение графа

Определение графа

Ориентированный Граф

Вершина

Дуга

Неориентированный Граф

Ребро

3 Дерево

Дерево

Дерево – связный неориентированный ациклический граф Корневое дерево – дерево с выделенной вершиной (корнем), корень задает ориентацию Ориентированное дерево – связный ориентированный граф в котором все вершины кроме одной имеют входящую степень 1, одна вершина (корень) имеет входящую степень 0 Лист – вершина с исходящей степенью 0 Лес – множество деревьев

4 Обход дерева в ширину

Обход дерева в ширину

Порядок посещения вершин по слоям BFS(start_node, goal_node) { // изначально список посещённых узлов пуст for(all nodes i) { visited[i] = false;} queue.push(start_node); // начиная с узла-источника visited[start_node] = true; while(! queue.empty() ) { // пока очередь не пуста node = queue.pop(); // извлечь первый элемент в очереди if(node == goal_node) { // проверить, не является ли текущий узел целевым return true;} // все преемники текущего узла, ... foreach(child in expand(node)) { // ... которые ещё не были посещены ... if(visited[child] == false) { queue.push(child); // ... добавить в конец очереди... visited[child] = true; // ... и пометить как посещённые } } } return false; // Целевой узел недостижим }

5 Обход дерева в глубину

Обход дерева в глубину

1 procedure DFS(G,v): 2 label v as discovered 3 for all edges e in G.adjacentEdges(v) do 4 if edge e is unexplored then 5 w ? G.adjacentVertex(v,e) 6 if vertex w is unexplored then 7 label e as a discovered edge 8 recursively call DFS(G,w) 9 else 10 label e as a back edge 11 label v as explored

Посещение вершин по правилу левой руки Время обнаружения и время завершения образуют правильную скобочную последовательность – любые два интервала либо не пересекаются либо один содержится в другом

6 Остовное дерево графа

Остовное дерево графа

Поддерево (лес) неориентированного графа, содержащее все его вершины Деревья поиска в ширину и глубину – остовные Хорда – ребро графа не из остовного дерева

7 Классификация ребер при поиске в глубину

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

Ребра дерева Прямые ребра соединяют вершину с потомком в дереве Обратные ребра соединяют вершину с предком в дереве Перекрестные ребра – остальные ребра В неориентированном графе все ребра не в дереве - обратные

8 Топологическая сортировка

Топологическая сортировка

Топологическая сортировка упорядочивает вершины ориентированного графа в порядке не нарушающем направление дуг Обратный порядок завершения при поиске в глубину дает топологическую сортировку Граф имеет цикл если поиск в глубину находит обратное ребро Порядок обхода в ширину дает топологическую сортировку (следует добавить виртуальную вершину для объединения истоков)

9 Двусвязные компоненты

Двусвязные компоненты

Точка сочленения (шарнир) – вершина, удаление которой из графа делает его несвязным Двусвязный граф – не содержащий точек сочленения Двусвязная компонента – максимальный двусвязный подграф Мост – ребро при удалении нарушающее связность графа Мост – двусвязная компонента из одного ребра Граф разбивается на множество двусвязных компонент, разделенных точками сочленения Двусвязные компоненты образуют дерево

10 Поиск точек сочленения

Поиск точек сочленения

Поиск в глубину не находит обратных ребер между двусвязными компонентами Пусть вершины занумерованы временем обнаружения при поиске в глубину d(v) Для каждой вершины найдем L(v) – минимальный номер вершины, в которую можно вернуться по обратному ребру из v или потомков v или номер родителя, если обратных ребер нет v является точкой сочленения тогда и только тогда Корень, если у него больше одного ребенка Другие вершины, если есть ребенок u и L(u)=d(v) Пример: (4, 2), (5, 2) – обратные ребра L(2)=1, L(3)=2, L(4)=2, L(5)=2, L(6)=5 2, 5 – точки сочленения (1, 2), (5, 6) – мосты [(2, 3), (3, 4), (4, 5), (4, 2), (5, 2)] – двусвязная компонента

«Краткое введение в теорию графов»
http://900igr.net/prezentacija/algebra/kratkoe-vvedenie-v-teoriju-grafov-61158.html
cсылка на страницу

Комбинаторика

25 презентаций о комбинаторике
Урок

Алгебра

35 тем
Слайды
900igr.net > Презентации по алгебре > Комбинаторика > Краткое введение в теорию графов