Презентация на тему «Краткое введение в теорию графов»

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

Салищев С. И.

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

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

Вершина

Дуга

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

Ребро

Дерево

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

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

Порядок посещения вершин по слоям 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; // Целевой узел недостижим }

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

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

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

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

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

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

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

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

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

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

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

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

Поиск в глубину не находит обратных ребер между двусвязными компонентами Пусть вершины занумерованы временем обнаружения при поиске в глубину 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)] – двусвязная компонента