Теоретическая часть. Рассмотрим конечный граф G=(V, E), где |V|=n, |E|=mРассмотрим конечный граф G =(V, E), где | V |= n, | E |= m. Способами аналитического представления графа являются: 1. Матрица инциденций. Ориентированный граф задается прямоугольной матрицей B (n ´ m), элементы которой определяются по правилу:
Кроме нерационального использования памяти (n× m единиц) недостатком этого способа представления является неудобный доступ к информации. Например, для ответа на вопросы: а) существует ли ребро (дуга) (vi, vj); б) к каким вершинам ведут ребра (дуги) из вершины vi требуется, в худшем случае, перебор n× m элементов, т.е. порядка n× m шагов алгоритма. 2. Матрица смежности. Элементы квадратной матрицы A (n ´ n) определяются следующим образом:
Проверка существования ребра (дуги) (vi, vj) осуществляется за один шаг, в отличие от матрицы инциденций, однако, проверка свойств графа на основе такого представления требует, в худшем случае, порядка n 2 шагов алгоритма. 3. Таблицы ребер. Она представляет собой матрицу размером m ´ 2, каждая строка которой содержит вершины инцидентные i -му ребру (i -ой дуге). Для работы со взвешенными графами нужно добавить к матрице столбцы, соответствующие весам ребер (дуг). Этому способу представления графа присущ тот же недостаток, что и матрице инциденций, - неудобство доступа к информации, хотя число шагов при поиске ребра здесь значительно меньше (порядка m). Поиск можно ускорить, введя лексикографический порядок в упорядочении пар и применяя двоичный поиск. 4. Списки инцидентности. Для каждой вершины vi Î V создается список записей, характеризующих ребра (дуги), инцидентные этой вершине. Таким образом, это представление использует объем памяти порядка (n + m), поиск вершины смежной с данной требует порядка (n + m) шагов, проверка свойств графа осуществляется за число шагов порядка. Поэтому остановимся подробнее на этом способе задания графа.
|
