Сильная, односторонняя и слабая связность В неориентированном графе две вершины либо связаны . В ориентированном графе отношение связанности вершин несимметрично, а потому определение связности отличается. Говорят, что две вершины . Говорят, что две вершины гг и . Говорят, что две вершины . Если все вершины в орграфе сильно . Сильная связность влечет одностороннюю связность, которая влечет слабую связность. Пример На рис. Компоненты сильной связности Компоненты сильной связности . Связность в орграфах . Если вершина не связана с другими, то считаем, что она сама образует КСС. Пример На рис. Выделение компонент сильной связности Следующий алгоритм, основанный на методе поиска в глубину, находит все компоненты сильной связности орграфа. Выделение компонент сильной связности Вход. Процедура КСС выделяет все КСС, достижимые из вершины, выбранной в основном алгоритме. Кратчайшие пути Задача нахождения кратчайшего пути в графе имеет столько практических применений и интерпретаций, что читатель, без сомнения, может сам легко привести множество примеров. Здесь рассматриваются два классических алгоритма, которые обязан знать каждый программист. Длина дуг Алгоритм Уоршалла позволяет ответить на вопрос, существует ли цепь . Часто нужно не только определить, существует ли цепь, но и найти эту цепь. Длиной пути называется сумма длин дуг, входящих в этот путь. Наиболее часто на практике встречается задача отыскания кратчайшего пути. Алгоритм Флойда Алгоритм Флойда находит кратчайшие пути между всеми парами вершин в . В этом алгоритме для хранения информации о путях используется матрица Я. Заметим, что всего в графе . Таким образом, непосредственное представление всех путей потребовало бы памяти объема . Экономия памяти достигается за счет интерпретации представления, то есть динамического вычисления некоторой части информации вместо ее хранения в памяти. В данном случае любой конкретный путь . Обоснование Алгоритм Флойда имеет много общего с алгоритмом Уоршалла . Покажем по индукции, что после выполнения г. Пусть теперь перед началом выполнения тела цикла на г. В таком случае, если в результате добавления вершины . Таким образом, после окончания цикла, когда г . р, то есть искомые кратчайшие пути. Алгоритм не всегда выдает решение, поскольку оно не всегда существует. Алгоритм Дейкстры Алгоритм Дейкстры находит кратчайший путь между двумя данными вершинами в . А именно, достаточно выполнения неравенства треугольника. Обоснование Для доказательства корректности алгоритма Дейкстры достаточно заметить, что при каждом выполнении тела цикла, начинающегося меткой М, в качестве . Рассмотрим вновь помеченную вершину . Заметим, что если известен . Связность путь, проходящий через помеченные вершины, то тем самым известен кратчайший путь. Тогда на этом пути должны быть непомеченные вершины. Комментарии Изложение центрального результата этой главы — теоремы Менгера . Алгоритм нахождения максимального потока в сети заимствован из . Алгоритм выделения компонент сильной связности приведен в . Алгоритмы Флойда и Дейкстры нахождения кратчайших путей принадлежит к числу классических общеизвестных алгоритмов, описание которых можно найти в большинстве учебников по дискретной математике, в частности, в . Доказать вторую теорему подраздела . Доказать, что наибольшее число непересекающихся множеств вершин, разделяющих вершины кии, равно . Имеется конечное множество юношей, каждый из которых знаком с некоторым конечным подмножеством множества девушек. Каждый юноша желает взять в жены более чем одну знакомую девушку. Найти необходимое и достаточное условия решения этой задачи. Как может измениться количество компонент сильной связности орграфа при добавлении к нему одной дуги. Вероятность успешного прохождения пути определяется как произведение вероятностей составляющих его дуг. Построить алгоритм нахождения наиболее надежного . Для них выполняются многие свойства, которые не всегда выполняются для графов в общем случае. Применительно к деревьям многие доказательства и рассуждения оказываются намного проще. Более половины объема этой главы посвящено рассмотрению конкретных применений деревьев в программировании. Свободные деревья Изучение деревьев целесообразно начать с самых общих определений и установления основных свойств. Определения Граф без циклов называется ациклическим, или лесом. Связный ациклический граф называется . Таким образом, компонентами связности леса являются деревья. В связном графе . Пример На рис. Основные свойства деревьев Следующая теорема устанавливает, что два из четырех свойств — связность, ацикличность, древовидность и субцикличность — характеризуют граф как дерево. Пусть далее х — ребро, соединяющее любую пару несмежных вершин в . Тогда следующие утверждения эквивалентны. любые две вершины соединены в . Пусть существуют две цепи . Пусть ребро х — не мост. Само ребро х — вторая цепь. Пусть есть цикл с п вершинами и п ребрами. Остальные р — п вершин имеют инцидентные им ребра, которые связывают их с циклом. Соединив две несмежные вершины, получим единственный простой цикл. Пусть цепь не единствен ная. Иллюстрации к доказательству теоремы о свойствах деревьев . Действительно, пусть это не так. Если в этом дереве соединить несмежные вершины, то получим второй цикл. Общая схема доказательства представлена на рис. Граф доказательства сильно связен, следовательно, теорема доказана. О СЛЕДСТВИЕ В любом нетривиальном дереве имеются по крайней мере две висячие вершины. Доказательство Рассмотрим дерево . Дерево — связный граф, следовательно, . Деревья Вычисление От противного Рис. Схема доказательства теоремы о свойствах деревьев Далее от противного. Ориентированные, упорядоченные и бинарные деревья Ориентированные . Ориентированные деревья Ориентированным деревом . существует единственный узел, полустепень захода которого равна . Он называется корнем ордерева. полустепень захода всех остальных узлов равна .