Практическое занятие 1

Тема. ОСНОВНЫЕ ЭЛЕМЕНТЫ И ПОНЯТИЯ ТЕОРИИ ГРАФОВ

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

1. Определение понятия граф. Виды графов

2. Модель сети связи.

3. Понятие путь, множество путей, ранг пути.

4. Алгебраическое представление графов.

5. Топологические матрицы и их построение.

6. Количественные матрицы и их построение.

7. Построение структурной матрицы В.

Структура сети, ее топология – это совокупность пунктов (узлов, станций и т.п.) и соединительных линий между ними (каналов).

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

G = [A, B],

где А ={a_i} – совокупность вершин графа (пунктов (узлов) сети),

В ={bij} – совокупность ребер графа (линий связи).

Если ребра множества А ориентированы, что обычно показывается стрелкой, то граф называется ориентированным графом, или орграфом. Ребра орграфа обычно называют дугами. Орграф приведен на рис. 1.1. Если ребра не имеют ориентации, то граф называется неориентированным (рис. 1.2).

Граф, который имеет как ориентированные, так и неориентированные ребра, называется смешанным (рис. 1.3). Если в графе между двумя любыми вершинами есть несколько ребер, то такой граф называется мультиграфом (рис. 1.4).

Рисунок 1.1 – Изображение орграфа

Рисунок 1.2 – Изображение неориентированного графа

Рисунок 1.3 – Изображение смешанного графа

Рисунок 1.4 – Изображение мультиграфа

Обычно вершинам графа приписываются номера (или обозначения x_i, x_j), чтобы различать их и иметь возможность ими оперировать в процессе анализа. Ребра графа обозначаются обычно а=(x_i, x_j), где x_i, x_j – начальная и конечная вершины, связанные данным ребром. Кроме этого обозначения применяют также a(x_i, x_j) или а(i, j), или а _{i j}. Иногда ребро (дугу) обозначают (i, j).

В используемых обозначениях i, j – номера вершин. Кроме того, ребра можно обозначать а_i, где i – номер ребра.

Путем µ _{i j} графа называется последовательность ребер, начинающаяся в вершине i, заканчивающаяся в вершине j, в которой конечная вершина каждого ребра, отличного от последнего, является начальной вершиной следующего.

Так, на рис. 1.5 последовательности дуг а₆, а₅, а₉, а₈, а₄; а₁, а₆, а₅, а₉ являются путями. Эти последовательности можно также записать в форме:

а(х_2, х₅), а(х₅, x₄), а(х₄, х₃), а(x₃, х₅), а(х₅, х₆);

а(х₁, х₂), а(х₂, х₅), а{х₅, х₄), а(х₄, х₃).

Более простой является следующая форма записи:

а₂₅, а₅₄, а₄₃, а₃₅, а₅₆;

а₁₂, а₂₅, а₅₄, а₄₃.

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

В рассмотренном примере второй путь является простым.

Цикл – это путь, начальная и конечная вершины которого совпадают.

Граф называется связным, если для любых разных вершин существует, по крайней мере, один соединяющий их путь.

В орграфе путь называют также цепью.

Напомним, что граф – это множество вершин и ребер, обозначается G=(X, А). Любое подмножество множества G называется подграфом, обозначается =( , ).

Дерево графа определяется как связное подмножество , которое не содержит циклов. Итак, для любых двух вершин графа в дереве существует единственный путь, который соединяет их.

В графе, содержащем n вершин, подграф из k вершин (k ≤ n) является деревом, если выполнены любые две из следующих условий:

1) подграф является связным;

2) подграф не имеет циклов;

3) число ребер в подграфе равняется k – 1.

Рисунок 1.5 – Изображение последовательности дуг

а₆, а₅, а₉, а₈, а₄; а₁, а₆, а₅, а₉ , которые являются путями.

Рисунок 1.6 – Изображение графа

Остовным деревом, или остовом, называется дерево, которое содержит все вершины графа. Итак, если граф содержит n вершин, то дерево с n вершинами и n – 1 ребром является остовом. Дерево для графа (рис. 1.6) представлено на рис. 1.7, остовное дерево – на рис. 1.8. Здесь для упрощения вершины графа обозначены номерами, ветви же не обозначены. Их будем обозначать при необходимости.

Заметим, что для графа можно построить несколько остовных деревьев.

В дальнейшем для упрощения, если это не обусловлено отдельно, остовное дерево будем называть просто деревом.

Рисунок 1.7 – Изображение дерева для графа (рис. 1.6)

Рисунок 1.8 – Изображение остовного дерева для графа (рис.1.6)

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

Кратчайшим (максимальным) деревом называется дерево с минимальным (максимальным) весом. Иногда такое дерево называют деревом минимальной (максимальной) стоимости.

Рисунок 1.9 – Изображение дерева графа для рис. 1.5

Рисунок 1.10 – Изображение остова графа для рис. 1.5

Деревья и остовы определяются как для ориентированных, так и для неориентированных графов.

На рис. 1.9 изображено дерево графа рис. 1.5, на рис. 1.10 – остов графа рис. 1.5.

Структура сети связи, ее топология – это совокупность пунктов (узлов, станций и т.д.) и соединяющих их линий (каналов).

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

В качестве модели используется граф G=(X, А), где X={х_і} – совокупность вершин графа, которые ставятся в соответствие пунктам сети, а А={а_іj} – совокупность ребер графа, которые ставятся в соответствие линиям связи. Поскольку каналы сети могут быть односторонними и двусторонними, ребра графа могут быть ориентированными и неориентированными. Таким образом, в качестве модели сети связи могут быть использованы ориентированные, неориентированные, смешанные графы, а также мультиграфы.

Сетевые модели широко используются на практике при проектировании систем электросвязи, систем космической и радиосвязи, телетрансляционных сетей, транспортных сетей и т.д.

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

1) построить модель сложной системы как совокупность простых;

2) составить формальные процедуры для определения качественных и количественных характеристик системы;

3) указать механизм взаимодействия компонентов системы с целью описания последней в терминах ее основных характеристик;

4) определить, которые данные необходимы для исследования системы.

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

Матричное представление графов. Для алгебраического представления графов удобно пользоваться топологическими матрицами и матрицами характеристик ребер графа (ветвей сети).

Топологические матрицы

Матрица смежности. Матрица смежности (связности) графа G – квадратная матрица А={а_іj} размером n (n – число вершин графа). Определяется следующим образом:

Рисунок 1.11 – Изображение графа матрицы смежности табл. 1.1

Элементы главной диагонали матрицы А обычно принимаются равными нулю (а_іj = 0), за исключением случаев, когда в некоторых вершинах есть петли.

Матрица смежности графа, изображенного на рис 1.11, имеет вид табл. 1.1.

В вершинах 2 и 6 есть «петли», поэтому соответствующие элементы главной диагонали а₂₂=1 и а₆₆=1. В дальнейшем будем рассматривать графы, которые не содержат «петель» в вершинах.

Таблица 1.1 – Матрица смежности графа, изображенного на рис. 1.11

А =

Отметим, что матрица А для ориентированного графа несимметричная относительно главной диагонали, симметричной она будет для неориентированного графа.

Структурная матрица. Для упрощения записи структуры и сети ребрам графа присваиваются обозначения, например, а,b,c… Эти обозначения используются в качестве элементов структурной матрицы.

Структурная матрица графа G - квадратная матрица В = [b _іj] размера n, определяется таким образом:

Здесь х – обозначение ребра на графе.

Рисунок 1.12 – Изображение графа для структурной матрицы В табл. 1.2

Для графа, изображенного на рис 1.12, структурная матрица В представлена в табл. 1.2

Таблица 1.2 – Структурная матрица графа, изображенного на рис. 1.12

В =

Матрицы количественных характеристик ребер графа. Для разных количественных оценок каждому ребру графа приписывается некоторый вес –число, которое характеризует какое-либо свойство данного ребра, например, длину, стоимость, пропускную способность, канальную емкость, время передачи информации, надежность и т.п. Указанные характеристики ребер графа представляются в форме соответствующих квадратных матриц размера n – длин, стоимостей и т.д.

Для построения, например, матрицы длин L = [l _іj] пользуются правилом:

Считая, что числа, изображенные около ребер графа черт 1.12, есть длины ребер, матрицу длин L представим в табл. 1.3

Таблица 1.3 – Матрица длин L

L =

Матрицу канальных емкостей ребер С=[с _іj] получают по правилу:

Таблица 1.4 – Матрица канальных емкостей С

С =

Считая, что числа, указанные возле ребер графа черт. 1.12 есть число каналов ребер, соответствующую матрицу канальных емкостей С представим в табл. 1.4.

Аналогично получаются и другие матрицы характеристик ребер графа. Если G – неориентированный граф, то все матрицы симметричны относительно главной диагонали, то есть их элементы х _іj = х_ji.