Способы задания графов

Рассмотрены два способа описания графов: графически и в виде двух множеств вершин V и ребер Е, когда каждое ребро еÎЕ определено парой инцидентных ему концевых вершин .

Опишем множество его вершин и ребер, а также отношение инцидентности. Занумеруем вершины графа G: V₁, V₂, …, V_i, V_n и ребра: е₁, е₂, …, е_i, е_m.

Отношение инцидентности задается:

1. Матрицей инцидентности размера m x n: по вертикали и горизонтали указываются вершины и ребра соответственно, а на пересечении i-ой вершины и j-го ребра, в случае н – графа проставляется 1, если они инцидентны и 0 – в противном случае, т.е.

В случае орграфа: -1, если вершина является началом ребра;

1, если вершина является концом ребра;

0, если вершина и ребро не инцидентны.

Если некоторая вершина является для ребра началом и концом (петля), проставляется любое другое число, например, 2, т.е.

2. Списком ребер графа, представленным двумя столбцами: в левом перечисляются все ребра е_iÎЕ, а в правом – инцидентные ему вершины , ; для н – графа порядок вершин в строке произволен, для орграфа первым стоит номер начала ребра;

3. Матрицей смежности - квадратной матрицей размера n x n; по вертикали и горизонтали перечисляются все вершины V_jÎV, а на пересечении и вершин в случае н-графа проставляется число, равное числу ребер, соединяющих эти вершины; для орграфа равно числу ребер с началом в вершине и концом в .

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

Пример 1: Задать матрицами инцидентности и смежности, а также списком ребер графы G₁, G₃ (рис 2).

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

Табл.1

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

Табл.2

Список ребер:

Табл. 3

Пример 2: Пусть дан сетевой граф:

Рис. 3

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

1) Графически (Рис 3).

2) С помощью задания двух множеств:

V = {1, 2, 3, 4, 5, 6} и Е= {(1, 2), (1, 3), (2, 5), (2, 4), (5, 6), (4, 4), (3, 4)}.

3) Матрицей инцидентности:

Табл. 4

Особенностью графа является то, что начального события 1 только выходят, а в конечное 6 – только входят. Поэтому в первой строке единицы со знаком минус, а в последней - со знаком плюс.

4) Матрицей смежности:

Табл. 5

5) Список ребер:

Табл. 6

Пример 3: Задать различными способами графы G₁, G₂ (рис.4,5) соответственно.

Как вычислить число вершин и число ребер по матрицам и списку ребер? Сформировать правила переходов от описания графа списком ребер и матрице инцидентности и от матрицы смежности к списку ребер.

Матрицы инцидентности н – графа G₁ и орграфа G₂ приведены в таблице 7 и таблице 8. Список ребер – в таблице 9, матрицы смежности – в таблице 10.

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

Табл. 7

Табл. 8

Списки ребер:

Табл. 9

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

Табл. 10

Матрица смежности н – графа симметрична относительно главной диагонали . Все ребра определяются верхним правым треугольником матрицы, расположенным над диагональю, включая последнюю. Число ребер н – графа по матрице смежности сумме элементов, расположенных на диагонали и выше, т.е. равно .

Ребра орграфа определяются всеми элементами матрицы смежности, поэтому их число равно .

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

Построение матрицы инцидентности по списку ребер:

Каждая строка списка соответствует строке матрицы с тем же номером. Для н – графа в строке списка указаны номера элементов строки матрицы инцидентности, равные 1. Для орграфа в этой строке первым стоит номер элемента, равного 1. При совпадении номеров в строке списка ребер в названном элементе строки матрицы инцидентности проставляется, например, 2.

Построение по матрице смежности списка ребер:

Элементу матрицы, расположенному в i ^ой строке и j ^ом столбце, соответствует строк списка ребер (при = 0 ни одной строки), в каждой из которых записаны номера i и j. Для Н – графа эти строки соответствуют только элементам верхнего правого треугольника матрицы смежности, т.е. элементам с , а для орграфа нужно рассматривать все элементы все элементы .

Практическое занятие по теме: «Теория графов»

1) Даны графы

Рис. 1

Задать граф G₁, представленный на рис. 1, через множества вершин V_1, и ребер Е₁.

Решение: Граф G₁ может быть полностью определен:

· двумя множествами – поименованных вершин и поименованных ребер ;

· множеством ребер, каждое из которых представлено парой своих концевых вершин .

Порядок указания вершин безразличен, т.к. все ребра в графе G₁ неориентированные.

2) Задать графы G₂ – G₃ (рис.1) множествами их вершин и рёбер. Сравнить G₁ – G_3.

3) Равны ли графы G₁ – G₂ (рис.2).

Задать графы G₁ – G₃ множествами их вершин и рёбер. Сравнить графы.

4) Определить дополнение графа , если:

а) G – пятиугольник;

б) G – треугольник.

Какой ориентированный граф соответствует графу G (представить графически)?

G

Рис. 2

5) Даны графы

Рис. 3

Определить, изоморфны ли графы G₁, G₂, изображенные на рис. 3.

Решение: В первом G₁ и во второмG₂ графах |V₁| = |V₂| = 5, |E₁| = |E₂| = 7.

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

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

Табл. 1

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

Табл. 2

Список рёбер:

Табл. 3

Для проверки изоморфности графов G₁ и G₂, например, по матрице смежности, потребуется определить, существует ли перестановка строк и столбцов в матрице смежности G₁ такая, чтобы в результате была получена матрица смежности G_2.

Для проверки изоморфности графов G₁ и G₂ по матрице инцидентности (и списку рёбер) требуется осуществить всевозможные перестановки строк и столбцов матрицы G₁, чтобы проверить, получается ли в результате пары перестановок и матрица инцидентности, соответствующая графу G₂. Maксимальное число перестановок равно n!m! = 5!×7!, поэтому решение задачи таким способом не менее трудоемко.

Однако в нашем случае по графическим представлениям G₁и G₂ нетрудно обнаружить сходство графов.

Для этого достаточно на рис. G₂ “поднять” вершину В до условия вершин 2, 4, что позволяет обнаружить изоморфность графов.

Таким образом, графы G₁ и G₂ изоморфны и отличаются только нумерацией.

Нетрудно определить требуемые перенумерации вершин и рёбер графа G₂, позволяющие перейти от матриц инцидентности, смежности или списка рёбер графа G₁ к соответствующим представлениям графа G₂:

и .

6) Задать графы G₁ – G₃ , изображенные на рис.1, матрицами инцидентности и смежности, а также списком ребер.

7) Задать различными способами графы G₁ – G₇, определённые ниже. Проверить справедливость сформулированных в примере 3 правил переходов от одного способа задания графа к другому:

а) G₁ – тетраэдр;

б) G₂ – тетраэдр с петлями во всех вершинах;

в) G₃ – куб;

г) G₄ –граф, представленный на рис.4а;

д) G₅ – граф на рис.4б;

е) G₆ – граф на рис.4в;

ж) G₇ – граф на рис.4г.

Рис. 4

8) Построить матрицы инцидентности и смежности, а также список рёбер для графа G₃ (рис. 3). Изоморфен ли граф G₃ графам G₁ и G₂ (рис.3). Проверить по матрицам смежности (или инцидентности) графов.

9)

Рис. 5

Графы (рис.5) задать матрицами смежности. Определить, изоморфны ли эти графы?

10)

Рис. 6.

Показать, что два графа (рис.6) изоморфны.

Не нашли, что искали? Воспользуйтесь поиском: