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

Пример 1. Для графа, показанного на рис. 15.15, записать множества ориентированных и неориентированных ребер и дуг.

Рис. 15нка 1.15, граф содержит 8 вершин и 15 ребер: |X| = 8; |U| =15,тогда множество реберU = È Ç включает в себя следующие подмножества: = { u ₁, u ₄, u ₆, u ₁₀, u ₁₂, u ₁₄}; = { u ₂, u ₃, u ₅, u ₇, u ₉, u ₁₃}; = { u ₈, u ₁₁, u ₁₅}.

Пример 2. Привести пример мультиграфа с мультичислом, равным 4.

Ответ: Мультиграф, удовлетворяющий заданным требованиям, приведен на рис. 15.16.

Рис. 15.16. Искомый мультиграф

Пример 3. Пусть граф G = (X, U) (рис. 15.17)задан графическим способом. Задать тот же граф аналитическим и матричным способом.

Рис. 15.17. Граф G

Решение: Граф, заданный на рис. 15.17, можно задать аналитическим способом следующим образом: |X| = 7; X = { x ₁, x ₂, x ₃, x ₄, x ₅, x ₆, x ₇}; Г = {Г x ₁, Г x ₂, Г x ₃, Г x ₄, Г x ₅, Г x ₆, Г x ₇}; Г x ₁ = { x ₂, x ₃, x ₄, x ₅, x ₇}; Г x ₂ = { x ₁, x ₃, x ₄, x ₅, x ₆, x ₇}; Г x ₃ = { x ₁, x ₂, x ₅, x ₆, x ₇}; Г x ₄ = { x ₁, x ₂}; Г x ₅ = { x ₁, x ₂, x ₃, x ₆}; Г x ₆ = { x ₂, x ₃, x ₅}; Г x ₇ = { x ₁, x ₂, x ₃}.

Очевидно, что такой способ задания содержит слишком много избыточной информации. Для устранения этого недостатка достаточно использовать Г x_{n -1} ─ образ и не включать в Г x_{i -1}элементы х_i,определяющие Г x_i.

Тогда получим: Г x ₁ = { x ₂, x ₃, x ₄, x ₅, x ₇}; Г x ₂ = { x ₃, x ₄, x ₅, x ₆, x ₇}; Г x ₃ = { x ₅, x ₆, x ₇}; Г x ₄ = Æ; Г x ₅ = { x ₆}; Г x ₆ = Æ; Г x ₇ = Æ.

Граф, изображенный на рис. 15.17, можно задать также в виде специальной матрицы (матрицы смежности).

.

При этом для задания неориентированного графа вполне достаточно треугольной матрицы типа R’:

.

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

.

Пример 4. Привести примеры подграфа, суграфа и дополнения до полного для графа, заданного на рис. 15.17.

На рис.15.18. изображен подграф G’ графа G, полученный удалением из графа G вершин x ₂, x ₃ и инцидентных им ребер.

На рис.15.19. изображен граф G’ = (X’, U’), являющийся суграфом графа G: |X’| = 7, |U’| = 8.

На рис.15.20. изображен граф = K \ G являющийся дополнением до полного графа G.

Рис. 15.18. Подграф графа G

Рис.15.19. Суграф графа G

Рис.15.20. Дополнение графа G

Пример 5. Для графа G, заданного на рис. 15.21 а), построить двойственный ему граф G_S.

Рис. 15.21. а) Пример графа G

Решение: Зададим смежностный (двойственный) граф G_S = (U, V) для графа G = (X, U). Для построения G_S по G на каждом ребре u_i Î U графа G выбирают среднюю точку и считают ее вершиной u_i Î U графа G_S. Граф G содержит 8 ребер, следовательно, двойственный ему граф Gs будет иметь 8 вершин.

Затем пару (u_i, u_j) соединяем ребром v_k = (u_i, u_j), если ребра u_i, u_j имеют общую вершину в G. То есть для графа G_S вершина u _1, например, будет иметь общие ребра с вершинами u ₂, u ₃, u ₄, u ₇, u ₈, так как эти ребра в исходном графе G имели общие вершины (x ₁ и x ₃). Далее продолжаем строить ребра для других вершин графа Gs.

Ответ: В результате получим следующий двойственный граф G_S (рис 15.21 б).

Рис. 15.21. б) Двойственный граф G_S

Пример 6. Задать нечеткий граф = (X, ), у которого X = { х ₁, х ₂, х ₃, х ₄, х ₅}, a = {<0,3/(х ₁, х ₁)>, <0,7/(х ₁, х ₂)>, <1/(х ₁, х ₅)>, <0,6/(х ₂, х ₄)>, <0,4/(х ₂, х ₅)>, <0,9/(х ₃, х ₄)>, <0,8/(х ₃, х ₃)>}.

Решение: Граф показан на рис. 15.22.

Рис. 1522. Нечеткий граф

Пример 7. Записать матрицу смежности нечеткого неориентированного графа = (X, ), заданного в примере 1.

Решение: Матрица смежности R _x ¹ нечеткого неориентированного графа , рассмотренного в примере 1, запишется следующим образом:

		x 1	x 2	x 3	x 4	x 5
R x ^1 =	x 1	0,3	0,7				.
x 2	0,7			0,6	0,4
x 3			0,8	0,9
x 4		0,6	0.9
x 5		0,4

Пример 8. Записать нечеткий неориентированный граф второго вида.

Решение: Зададим нечеткий неорграф второго вида = (, ), у которого = {<1/ x ₁>,<0,4/ x ₂>,<0,7/ х ₃>,<0,5/ x ₄>, <0,9/ х ₅>}, = {<0,3/(х ₁, х ₁)>, <0,7/(х ₁, х ₂)>, <1/(х ₁, х ₅)>, <0,6/(х ₂, х ₄)>.<0,4/(х ₂, х ₅)>, <0,9/(х ₃, х ₄)>, <0,8/(х ₃, х ₃)>}.

ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ

1. Что такое граф? Приведите пример. Назовите известные вам типы графов.

2. В чем состоит различие между ориентированными и неориентированными графами?

3. Опишите известные вам способы задания графов.

4. Что называется подграфом и суграфом графа?

5. Что называется дополнением графа?

6. Какой граф называется двойственным?

7. Какие операции могут выполняться над графами?

8. Что такое мультиграф и как определяется его мультичисло?

9. Дайте определение регулярного графа.

10. Дайте определение нечеткого графа. В чем состоит отличие нечеткого неориентированного графа первого и второго рода?

Дата добавления: 2015-10-26