78190

Графы. Алгоритмы на графах

Реферат

Информатика, кибернетика и программирование

Геометрическое - графом называется фигура, состоящая из точек (называемых вершинами) и отрезков, соединяющих некоторые из этих вершин. Соединяющие отрезки могут быть направленными (дугами), ненаправленными (ребрами)

Русский

2015-02-07

224.61 KB

7 чел.

Графы. Алгоритмы на графах

Оглавление

Введение в теорию графов 1

Матрица смежности 2

Матрица инцидентности 2

Маршруты и связность 3

Контрольные вопросы 6

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

Предлагается разделить (условно) терминологию теории графов на:

  1.  геометрическую,
  2.  теоретико-множественную,
  3.  матричную.

Одно и то же понятие теории графов тогда будет можно формулировать на трех "языках". Так, например, определение графа:

Геометрическое - графом называется фигура, состоящая из точек (называемых вершинами) и отрезков, соединяющих некоторые из этих вершин. Соединяющие отрезки могут быть направленными (дугами), ненаправленными (ребрами), прямолинейными или криволинейными. Отрезок, соединяющий вершину с самой собой, называется петлей.

   

Теоретико-множественное - графом называется пара (V,R), где V – это  множество  вершин  или  узлов, R – это множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых  рёбрами. Обозначается граф обычно через G(V,R). 

Вершины и рёбра графа называются также  элементами  графа, число вершин в графе  | V | — порядком, число рёбер  | R |размером графа.

Вершины  u  и  v называются концевыми вершинами (или просто концами) ребра r = {u,v}. Ребро, в свою очередь,  соединяет  эти вершины. Две концевые вершины одного и того же ребра называются соседними.

Два ребра называются смежными, если они имеют общую концевую вершину.

Ребро называется петлёй, если его концы совпадают, то есть r = {v,v}.

Степенью  degV  вершины  V  называют количество рёбер, для которых она является концевой (при этом петли считают дважды).

Вершина называется изолированной, если она не является концом ни для одного ребра; висячей  (или  листом), если она является концом ровно одного ребра.

Дуга — это упорядоченная пара вершин (v, w), где вершину v называют началом, а w — концом дуги. Можно сказать, что дуга v  w ведёт от вершины v  к вершине w.

Путём (или цепью) в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершин ребром.

Ориентированным путём в орграфе называют конечную последовательность вершин  vi  (i=1,…,k), для которой все пары (vi,vi + 1) (i=1,…,k-1) являются (ориентированными) рёбрами.

Циклом называют путь, в котором первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер. Заметим, что если вершины  u  и  v являются концами некоторого ребра, то согласно данному определению, последовательность (u,v,u) является циклом.

Путь (или цикл) называют простым, если ребра в нём не повторяются; элементарным, если он простой и вершины в нём не повторяются.

Ребро графа называется мостом, если его удаление увеличивает число компонент.

Матричное - графом называется множество (класс) квадратных (0,1)-матриц, перестановочно подобных между собой.

Первое и самое простое задание графа - это представление его с помощью картинки в соответствии с геометрическим определением графа. При этом в соответствии с договоренностью выше, вершинам конкретного представления графа будут приписаны номера.

Так на рисунке 1 даны два представления одного и того же графа.

Рисунок 1.

Другое задание графа - списком. Можно считать, что в соответствии с теоретико-множественным определением графа все элементы множества RVV, входящего в определение, упорядочены сначала по первым элементам пар, а затем по вторым, в соответствии с нумерацией вершин. Тогда два представления графа с рисунка 1 будут заданы двумя списками:

1 2, 3, 4   I II, III, V

2 3       II IV    

3 4       III V    

4 5       IV I    

5 1       V II  

В первом столбце - первые элементы пар, затем по строкам, списком через запятую, идут вторые элементы.

Третье задание графа - матрицами. Ниже выписаны две матрицы - A и B, задающие два представления графа с рисунка 1:

Матрица смежности

Матрица смежности — таблица, где как столбцы, так и строки соответствуют вершинам графа. В каждой ячейке этой матрицы записывается число, определяющее наличие связи от вершины-строки к вершине-столбцу (либо наоборот).

Недостатком являются требования к памяти — очевидно, квадрат количества вершин.

  1.  двумерный массив;
  2.  матрица с пропусками;
  3.  не явное задание (при помощи функции).

Матрица инцидентности

Каждая строка соответствует определённой вершине графа, а столбцы соответствуют связям графа. В ячейку на пересечении i-ой строки с j-м столбцом матрицы записывается:

1  - в случае, если связь j «выходит» из вершины i,

−1 - если связь «входит» в вершину,

0  - во всех остальных случаях (т.е. если связь является петлёй или связь не инцидентна вершине)

Данный способ является самым ёмким  и неудобным для хранения, но облегчает нахождение циклов в графе.

Список рёбер — это тип представления графа в памяти, подразумевающий, что каждое ребро представляется двумя числами — номерами вершин этого ребра. Список рёбер более удобен для реализации различных алгоритмов на графах по сравнению с матрицей смежности.

Обычно в теории графов выделяют некоторые разновидности графов. Среди таких разновидностей выделим следующие:

  1.  полный граф - граф, матрица смежности которого состоит из одних единиц;
  2.  полный обыкновенный граф - граф, у матрицы смежности которого все элементы, за исключением нулевых элементов главной диагонали, равны единице;
  3.  пустой (нулевой) граф - граф, матрица смежности которого нулевая (обыкновенный граф, все вершины которого изолированы, т.е. нет ни одной пары смежных вершин);
  4.  единичный граф - граф, матрица смежности которого единичная (граф, все вершины которого имеют петли и изолированы);
  5.  плоский (планарный) граф - граф, который можно начертить на плоскости так, чтобы его ребра (дуги) пересекались только в его вершинах.

Маршруты и связность

Одно из наиболее простых свойств, которым может обладать граф, это свойство быть связным. Маршрутом в графе G называется чередующаяся последовательность вершин и ребер.

Замкнутый маршрут называется простым циклом, если все его n вершин различны и n3.

Рис. 2. Граф для иллюстрации маршрутов

В помеченном графе G на рис. 2 v0v1v2vn – маршрут, который не является цепью, v1v2v5v4v2v3 – сложная цепь,  v1v2v5v4 – простая цепь,  v2v4v5v2 – простой цикл.

Обозначим через Gn граф, состоящий из одного простого цикла с n вершинами, и через  простую цепь с n вершинами;  часто называют треугольником. Граф G называется связным, если любая пара его вершин соединена простой цепью. Максимальный связный подграф графа G, называется компонентой связности, или просто компонентой графа G.

Таким образом, несвязный граф имеет, по крайней мере, две компоненты. Граф на рис. 3 имеет 10 компонент.

Рис. 3. Граф с 10 компонентами

Расстоянием d(u,v) между двумя вершинами u и v графа G называется длина кратчайшей простой цепи, соединяющей их; если u и v не соединены, то полагаем d(u,v)=. 

Нарисуем теперь два графа: полный обыкновенный граф К5 и полный двудольный граф К3,3  ввиду их особой значимости.

Рис. 5.

Выпишем также их матричные представления:

,          .

Используя введенные выше обозначения, с графом G, заданным матрицей A, можем связать матрицу , которую будем называть матрицей расстояний. Матрица D, вообще говоря, не будет (0,1)-матрицей, у этой матрицы на месте (u,v) будет стоять число d(u,v), поэтому она и называется матрицей расстояний.

Для графа на рисунке 2 его матрицы A и D будут иметь вид:

,             

По матрице D легко определяется диаметр графа d, как максимальное значение элементов этой матрицы. В приведенном примере d=2.

В ографе степень исхода вершины совпадает со степенью захода вершины и называется просто степенью вершины. Вершины со степенью, равной 1, называются висячими. Степень вершины v обозначают как deg v.

Ограф называется ациклическим, если в нем нет циклов. Дерево — это связный ациклический ограф. Каждый ограф, не содержащий циклов, называется лесом. Компонентами леса являются деревья.

Деревом называется связный ограф, у которого число ребер на единицу меньше числа вершин.

Для избежания противоречий под деревом мы будем понимать ограф с числом вершин n, где n2 .

В любом дереве имеются, по крайней мере, две висячие вершины.

Рисунок 6.

Матрицы деревьев изображенных на рисунке 6:

,,,

,,.

Рис.7(а) Дерево

Рис.7(б) Ориентированное выходящее дерево (вершина x3)

Рис.7(в) Ориентированное входящее дерево (вершина x3)

Каждое ребро ограничивается двумя вершинами.

Вершина, ограничивающая некоторое ребро, называется инцидентной этому ребру.

Два ребра называются смежными, если они инцидентны одной и той же вершине.

Так на рисунках 1 и 2 даны по два представления одного и того же графа.

Рисунок 1.

Рисунок 2.

Тогда два представления графа с рисунка 1 будут заданы двумя списками:

1 2, 3, 4   I II, III, V

2 3       II IV    

3 4       III V    

4 5       IV I    

5 1       V II

Два представления графа с рисунка 2 будут заданы списками:

1 2, 3, 4, 5 I II, III, IV, V

2 1, 3   II I, IV, V

3 1, 2, 4   III I, V

4 1, 3, 5   IV I, II

5 1, 4   V I, II, III

В первых столбцах таблиц - первые элементы пар, затем по строкам, списком, через запятую, идут вторые элементы.

Два представления графа с рисунка 2 будут заданы также своими множествами X:

Третье задание графа - матрицами. Ниже, в соответствии с матричным определением 1, выписаны две матрицы смежности – А1 и А2, задающие два представления графа с рисунка 1:

и две матрицы смежности и , задающие два представления графа с рисунка 2:

Кроме того, графы с рисунка 2 могут быть заданы своими матрицами инциденций и :  

(Нумерация ребер произведена в том порядке, в котором пары, задающие ребра, выписаны в соответствующих множествах ).

Контрольные вопросы

  1.  Дать определение графа в геометрической терминологии и его основным компонентам.
  2.  Дать определение графа в теоретико-множественной терминологии и его основным компонентам.
  3.  Дать определение графа в матричной терминологии и его основным компонентам.
  4.  Дать определение матрице смежности. Как формируется матрица? Примеры.
  5.  Дать определение матрице инцидентности. Как формируется матрица? Примеры.
  6.  Дать определение матрице расстояний. Как формируется матрица? Примеры.
  7.  Дать определение матрице деревьев. Как формируется матрица? Примеры.
  8.  Как представить граф множеством?

 

А также другие работы, которые могут Вас заинтересовать

20690. Охрана труда в чрезвычайных ситуациях 1.23 MB
  В учебном пособие рассматриваются на примерах с расчетными данными общие требования и нормативные документы регламентирующие организацию охраны труда на производстве в мирное время и в чрезвычайных ситуациях.
20691. АНАЛИЗ ФИНАНСОВОЙ ДЕЯТЕЛЬНОСТИ ЧЕРЕПОВЕЦКОГО ОТДЕЛЕНИЯ 8638/0146 ОАО «СБЕРБАНКА РОССИИ» 355.1 KB
  Депозитная политика – это документ, регламентирующий процесс привлечения средств. По моему мнению депозитная политика – это также операции по привлечению денежных средств на определенный срок, либо до востребования. Объектами депозитных операций являются депозиты
20692. Сплайн-інтерполяція. Інтерполяційні поліноми Лагранжа 221.07 KB
  Мета роботи: познайомитися з методами інтерполяції складних функцій реалізувати заданий за варіантом метод інтерполяції у середовищі МatLAB. Завдання до виконання роботи: Доповнити систему МatLAB файлом що реалізує заданий метод інтерполяції відповідно до варіанту.
20693. ЗАДАЧИ И ОСНОВЫ ОРГАНИЗАЦИИ ЕДИНОЙ ГОСУДАРСТВЕННОЙ СИСТЕМЫ ПРЕДУПРЕЖДЕНИЯ И ЛИКВИДАЦИИ ЧРЕЗВЫЧАЙНЫХ СИТУАЦИЙ (РСЧС) 363.5 KB
  В производственной сфере главная ответственность за предупреждение аварий и катастроф, осуществление мер по их ликвидации, по защите персонала объектов и населения жилых зданий, находящихся в опасной зоне, возлагалась на руководителей предприятий, отраслевые министерства и ведомства.
20694. Единая Европа: источники, образование, перспективы 136.5 KB
  ЕС является ключевым политическим и экономическим партнером России на Западе даже в условиях санкций. Особенно активно развиваются торгово-экономические связи. ЕС и Россия должны быть направлены на дальнейшее развитие конструктивного сотрудничества. В связи с этим понимание истоков, идей создания ЕС и его развитие является актуальным.
20695. ФОРМЫ УЧАСТИЯ ПРОКУРОРА В ГРАЖДАНСКОМ СУДОПРОИЗВОДСТВЕ В РК И ЗАРУБЕЖНЫХ СТРАНАХ 186 KB
  Дискуссия по поводу ограничения или, наоборот, усиления роли прокурора как в суде, так и в общем надзоре, не являются на сегодняшний день чем-то новым в истории прокуратуры, для которой характерен непрекращающийся поиск оптимальных форм осуществления полномочий.
20696. Розв’язання систем нелінійних рівнянь. Метод Ньютона 18.5 KB
  0001; J = [diffy1'x1' diffy1'x2' diffy1'x3' ; diffy2'x1' diffy2'x2' diffy2'x3' ; diffy3'x1' diffy3'x2' diffy3'x3' ]; p=[2;2;2]; x1=p1; x2=p2; x3=p3; dp=[inf;inf;inf]; while maxabsdp1:3 eps dp=[0;0;0]; Fk=[0;0;0]; Jk=evalJ; for i=1:3 Fki=evalFi:; end dp=invJkFk; p=pdp; x1=p1; x2=p2; x3=p3; end p 2.
20697. Криптографічна система RSA 54.28 KB
  5 зашифруємо повідомлення Створемо ключ Зашифруємо файл Відповідно до завдання лабораторної роботи проведемо розрахунки Повідомлення CRDHQS RSA p=5 q=7 N=57=35 p1q1=24 D=5 edmodp1q1=1 e5mod24=1 E=5 Ключ24 e =5 3^5 mod 35=33 18^5 mod 35=23 4^5 mod 35=9 8^5 mod 35=8 17^5 mod 35=12 19^5 mod 35=24 Зашифроване повідомлення 33 23 9 8 12 24 Розшифруєм повідомлення використовуючи ключ d=5 33 33^5 mod 35=3 23^5 mod 35=18 9^5 mod 35=4 8^5 mod 35=8 12^5 mod 35=17 24^5 mod 35=19 Висновки:...
20698. Розподіл ключів, протокол Діфф-Хеллмана 57.93 KB
  При роботі алгоритму кожна сторона: генерує випадкове натуральне число a закритий ключ спільно з віддаленою стороною встановлює відкриті параметри p і g зазвичай значення p і g генеруються на одній стороні і передаються іншій де p є випадковим простим числом g є первісних коренем по модулю p обчислює відкритий ключ A використовуючи перетворення над закритим ключем A = ga mod p обмінюється відкритими ключами з видаленою стороною обчислює загальний секретний ключ K використовуючи відкритий ключ видаленої сторони B і свій закритий ключ a...