🗊Презентация Графы. Описание графов. Задача Прима-Краскала

Графы Лекция №9

Графы

Графы Если дуги имеют направление (вспомните улицы с односторонним движением), то такой граф называется направленным или ориентированным графом (орграфом). Цепью называется последовательность ребер, соединяющих две (возможно не соседние) вершины u и v. В направленном графе такая последовательность ребер называется «путь». Граф называется связным, если существует цепь между любой парой вершин. Если граф не связный, то его можно разбить на k связных компонент – он называется k-связным. В практических задачах часто рассматриваются взвешенные графы, в которых каждому ребру приписывается вес (или длина). Такой граф называют сетью. Циклом называется цепь из какой-нибудь вершины v в нее саму. Деревом называется граф без циклов. Полным называется граф, в котором проведены все возможные ребра (для графа, имеющего n вершин таких ребер будет n(n-1)/2).

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

Описание графов Для взвешенных графов недостаточно просто указать, есть ли связь между вершинами. Требуется еще хранить в памяти «вес» каждого ребра, например, стоимость проезда или длину пути. Для этого используется весовая матрица.

Задача Прима-Краскала Город будем изображать узлом (вершиной). Телефонные линии могут разветвляться только на телефонных станциях, а не в чистом поле. Поскольку требуется линия минимальной общей длины, в ней не будет циклов, потому что иначе можно было бы убрать одно звено цикла и станции по-прежнему были бы связаны. В терминах теории графов эта задача звучит так:

Жадные алгоритмы Представим себе зимовщика, которому предоставили некоторый запас продуктов на всю зиму. Конечно, он может сначала съесть все самое вкусное – шоколад, мясо и т.п., но за такой подход придется жестоко расплачиваться в конце зимовки, когда останется только соль и маргарин. Подобным образом, если оптимальное решение строится по шагам, обычно нельзя выбирать на каждом этапе «самое вкусное» – за это придется расплачиваться на последних шагах. Такие алгоритмы называют жадными. Для решения задачи Прима-Краскала используется жадный алгоритм: Требуется проверить, чтобы циклов не было. Сделать это можно так: в самом начале покрасим все вершины в разные цвета и затем, выбрав очередное ребро между вершинами i и j, где i и j имеют разные цвета, перекрасим вершину j и все соединенные с ней (то есть имеющие ее цвет) в цвет i. Таким образом, при выборе ребер, соединяющих вершины разного цвета, цикл не возникнет никогда, а после n-1 шагов все вершины будут иметь один цвет.

Жадные алгоритмы, код

Работа с деревьями

Кратчайший путь

Алгоритм Дейкстры

Вывод результата

Алгоритм Дейкстры. Пример