Задание 1. Способы представления графов. Нахождение характеристик графа.

ПРАКТИЧЕСКАЯ РАБОТА № 9.

Тема: «Операции над множествами и графами».

Теоретические сведения.

Граф - Пара объектов G = (X, Г), где Х - конечное множество, а Г –конечное подмножество прямого произведения Х*Х. При этом Х называется множеством вершин, а Г - множеством дуг графа G.

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

Если в множестве Г все пары упорядочены, то такой граф называют ориентированным.

Дуга - ребро ориентированного графа.

Граф называется вырожденным, если у него нет рёбер.

Вершина Х называется инцидентной ребру G, если ребро соединяет эту вершину с какой-либо другой вершиной.

Подграфом G(V₁, E₁) графа G(V, E) называется граф с множеством вершин V₁ Î V и множеством ребер (дуг) E_ Î E, - такими, что каждое ребро (дуга) из E₁ инцидентно (инцидентна) только вершинам из V₁. Иначе говоря, подграф содержит некоторые вершины исходного графа и некоторые рёбра (только те, оба конца которых входят в подграф).

Подграфом, порождённым множеством вершин U называется подграф, множество вершин которого – U, содержащий те и только те рёбра, оба конца которых входят в U. Подграф называется основным подграфом, если множество его вершин совпадает с множеством вершин самого графа.

Вершины называются смежными, если существует ребро, их соединяющее.

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

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

Задание для студентов.

Задание 1. Для орграфа G ₁, заданного матрицей смежности,

- нарисовать граф;

- привести теоретико-множественное представление графа;

- задать граф соответствием;

- определить полустепени исхода и захода всех вершин;

- определить количество петель графа;

- построить матрицу инциденций;

- построить список концов ребер.

Задание 2. Для орграфов G ₁ и G ₂, выполнить бинарные операции матричным способом: объединения; пересечения; разности, кольцевой суммы.

Задание 3. Для орграфа G ₁ выполнить операции: дополнения; удаление вершины x_i; удаление дуги a_i; отождествление вершин x_i и x_j;

- стягивание дуги a_i.

Примечание: номера вершин i и j выбрать самостоятельно.

Примеры решения задач:

Задание 1. Способы представления графов. Нахождение характеристик графа.

Необходимо для орграфа G _1:

- нарисовать граф;

- привести теоретико-множественное представление графа;

- задать граф соответствием;

- определить полустепени исхода и захода всех вершин;

- определить количество петель графа;

- построить матрицу инциденций;

- построить список концов ребер.

Решение. a) Задана квадратная матрица , размерность которой определяет число вершин графа и отношение между вершинами графа G 1.

b) Теоретико-множественное представление графа задает граф G ₁ перечислением множества вершин и дуг:

G ₁= (X, A), где X ={ x_i }, i =1, 2,..., 5 – множество вершин,

A ={ a _i}, i =1, 2,..., 11– множество дуг,

причем a ₁ = (x ₁, x ₃), a ₂ = (x ₁, x ₄), a ₃ = (x ₁, x ₅), a ₄ = (x ₂, x ₁), a ₅ = (x ₂, x ₂), a ₆ = (x ₂, x ₄),
a ₇ = (x ₃, x ₄), a ₈ = (x ₄, x ₁), a ₉ = (x ₄, x ₃), a ₁₀ = (x ₅, x ₂), a ₁₁ = (x ₅, x ₄).

В случае задания графа соответствием граф обозначается парой G = (X, Г),

где Г – отображение множества Х в Х.

Отображением вершины x_i – Г(x_i) является множество вершин, в которые существуют дуги из вершины x_i, т. е. Г(x_i) = { x_j / $ дуга (x_i, x_j) Î A }.

Так для орграфа G ₁ задание соответствием выглядит следующим образом:

G ₁= (X, A), где X ={ x_i }, i =1, 2,..., 5 – множество вершин,

Г(x ₁) ={ x ₃, x ₄, x ₅}, Г(x ₂) = { x ₁, x ₂, x ₄}, Г(x ₃) ={ x ₄}, Г(x ₄) ={ x ₁, x ₃}, Г(x ₅) ={ x ₂, x ₄}.

c) Определение полустепеней исхода и захода вершин графа G ₁.

Полустепенью исхода вершины x_i – d ₀(x_i) называется количество дуг исходящих из этой вершины. Полустепенью захода вершины x_i – d_t (x_i) называется количество дуг, входящих в эту вершину.

Характеристики вершин удобно находить по матрице смежности. Так сумма элементов i-й строки матрицы дает полустепень исхода вершины xi, а сумма элементов i-го столбца дает полустепень захода вершины xi.

Дляграфа G ₁ характеристики полустепеней исхода и захода следующие:

d) Определение количество петель графа G ₁.

Количество петель графа можно определить по графу визуально или по матрице смежности, определив количество элементов вида a_ii. В графе G ₁ одна петля.