конспекты по информатике. Конспект Главы 3,6. Конспект Главы Графы Основные свва графов ориентированный граф g определяется как пара (V,E), где v конечное множество, а е бинарное отношение на V.
 Скачать 18.33 Kb.
|
|
Конспект Главы 3. Графы Основные св-ва графов: ориентированный граф G определяется как пара (V,E), где V - конечное множество, а Е - бинарное отношение на V. Множество V называется множеством вершин графа С, а его элементы - вершинами. Множество Е называется множеством ребер графа С, а его элементы, соответственно, ребрами. В неориентированном графе G = (V,E) множество ребер Е состоит из неупорядоченных пар вершин В неориентированном графе петли запрещены, так что каждое ребро содержит две разные вершины. Если (u, v) - ребро ориентированного графа G = (V, Е), то ребро выходит из вершины и u входит в вершину v. Если (u,v) - ребро неориентированного графа G = (V,E), то оно соединяет вершины u и v и называется инцидентным этим вершинам. Если в графе G имеется ребро (u, v), то говорят, что вершина v смежна с вершиной u. Для неориентированных графов отношение смежности является симметричным; для ориентированных графов это утверждение неверно. Степенью вершины в неориентированном графе называется количество ребер, соединяющих ее с другими вершинами. Вершина, степень которой равна О, называется изолированной. В ориентированном графе различают исходящую степень, равную количеству выходящих из вершины ребер, и входящую степень, равную числу входящих в вершину ребер. Степень вершины в ориентированном графе равна сумме ее входящей и исходящей степеней. Путь длины k от вершины и к вершине и' в графе G = (V,E) представляет собой такую последовательность (v0,v1'v2 ,". ,vk) вершин, что и = v0 , u' = vk и (v,_pv;)eE для i=l,2, ... ,k . Длиной пути называется количество составляющих его ребер. Путь содержит вершины v0,vpv2,.",vk и ребра (v0,v1 ), (vpv2), ••• , (vk_Pvk). Всегда существует путь нулевой длины из вершины в нее саму. Если имеется путь р из вершины и в вершину и' , то говорят, что вершина и' достижима из и по пути р, что иногда в ориентированном графе G записывается как р и- и' . Путь является простым, если все его вершины различны. Неориентированный граф является связным, если любая его вершина достижима из другой по некоторому пути. Для неориентированного графа отношение «быть достижимым из» является отношением эквивалентности (т.е. оно рефлексивно, симметрично и транзитивно, как, например, отношение равенства между числами) на множестве вершин. Неориентированный граф связен тогда и только тогда, когда он состоит из единственного связного компонента. Полным называется неориентированный граф, в котором каждая пара вершин являются смежными, т.е. который содержит все возможные ребра. Ациклический неориентированный граф называется лесом, а связный ациклический неориентированный граф - деревом. Для представления графа в памяти компьютера обычно используется один из двух стандартных способов: как множества списков смежных вершин или в виде матрицы смежности. Оба способа применимы как для ориентированных, так и для неориентированных графов. Вершины в каждом списке обычно хранятся в произвольном порядке. Представление графа с помощью матрицы смежности предполагает, что вершины графа пронумерованы в некотором порядке. Для неориентированного графа можно, воспользовавшись симметричностью отношения смежности, хранить в памяти только половину матрицы - поскольку матрица смежности для неориентированного графа симметрична. Поиск в ширину: поиск в ширину является одним из простейших алгоритмов для обхода графа и основой для многих других алгоритмов для работы с графами. Поиск в ширину наэывается так потому, что в процессе обхода, перед тем как приступить к поиску вершин на расстоянии k + 1 выполняется обход всех вершин на расстоянии k. Для отслеживания работы алгоритма поиск в ширину раскрашивает вершины графа в белый, серый и черный цвета. В каждой вершине графа хранится также дополнительная информация - цвет вершины (в поле color) и ее предшественник (в поле р) Стратегия поиска в глубину состоит в том, чтобы идти вглубь графа, пока это возможно. При выполнении поиска в глубину исследуются все ребра, выходящие из последней открытой вершины, и мы покидаем вершину только тогда, когда не остается неисследованных. При этом происходит возврат в вершину, из которой была открыта текущая вершина. Этот процесс продолжается до тех пор, пока не будут открыты все вершины, достижимые из исходной. Если при этом остаются неоткрытые вершины, то одна из них выбирается в качестве новой исходной вершины, и поиск возобновляется из нее. Процесс повторяется до тех пор, пока не будут открыты все вершины графа. В отличие от поиска в ширину, где подграф предшествования образует дерево, при поиске в глубину подграф предшествования может состоять из нескольких деревьев, так как поиск может выполняться из нескольких исходных вершин. Поиск в глубину самостоятельно используется редко и обычно является частью другого алгоритма. Подграф предшествования поиска в глубину, таким образом, образует лес, который состоит из нескольких деревьев поиска в глубину. Вершины графа раскрашиваются в разные цвета, указывающие их состояние. Каждая вершина изначально белая, затем при ее открытии в процессе поиска она окрашивается в серый цвет, а по завершении сканирования ее списка смежности она становится черной. Это гарантирует, что каждая вершина в конечном счете находится только в одном дереве поиска в глубину. Топологическую сортировку графа можно рассматривать как такое упорядочение его вершин вдоль горизонтальной линии, что все ребра направлены слева направо. Алгоритм поиска в глубину позволяет легко и просто выполнить топологическую сортировку - достаточно выполнить поиск в глубину. Топологическая сортировка ориентированного ациклического графа представляет собой такое линейное упорядочение всех его вершин. Конспект Главы 6. Комбинаторные алгоритмы. Метод исчерпывающего перебора может потребоваться для задач, для решения которых нет полиномиальных алгоритмов, задач небольшого размера, для которых проще сгенерировать все возможные варианты, чем реализовывать сложный полиномиальный алгоритм Задача генерации всех подмножеств множества из n элементов тесно связана с генерацией последовательности всех 2" n-битовых чисел. Если каждое очередное число отличается от предыдущего только одним битом, то такие последовательности носят название кодов Грея. Каждое последующее подмножество получается из предыдущего путем единственного добавления или удаления элемента. Генерация всех подмножеств данного множества-задача генерации всех подмножеств множества из п элементов тесно связана с генерацией последовательности всех 2n п-битовых чисел. При сопоставлении каждому элементу множества своего бита в n-битовом числе любое подмножество однозначно отображается на n-битовое число, в котором единичные биты означают наличие в подмножестве соответствующих элементов множества, а нулевые - их отсутствие. Генерация всех перестановок-множество переставляемых элементов - это множество целых чисел от 1 до n, которые в общем случае можно рассматривать как индексы элементов n-элементного множества. Получить решение задачи генерации всех n перестановок можно путем вставки n в каждую из n возможных позиций среди элементов каждой из перестановок n-1 элементов. Все эти перестановки будут различны, а их общее количество будет равно n(n-1)! = n!. Получаем все возможные перестановки исходного множества целых чисел от 1 до n. Число n можно вставлять в ранее сгенерированные перестановки как слева направо, так и справа налево. Преимущество этого способа генерации перестановок - каждая перестановка получается из непосредственной предшественницы при помощи обмена местами только двух элементов. Генерация всех сочетаний -особенность алгоритма-значение n в явном виде использовано в нём только один раз-при инициализации. Генерация всех разбиений числа-данный алгоритм реализован в виде класса-перечислителя. Генерация всех деревьев-комбинаторный алгоритм, который генерирует все возможные корректные расстановки n пар скобок (под корректной расстановкой мы подразумеваем расстановку, когда пары либо вложены одна в другую, либо не пересекаются). Имеется однозначная связь между лесом и бинарным деревом -для этого выполняется связывание всех потомков каждой семьи и удаление всех вертикальных связей, за исключением связи первого дочернего узла с родителем. В результате мы получим бинарное дерево. Для генерации всех лесов с n узлами, как и для генерации всех бинарных деревьев с n внутренними узлами, достаточно сгенерировать все расстановки n пар скобок |