Полная версия

Главная arrow Математика, химия, физика arrow Дискретная математика. Сборник задач

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

ТЕОРИЯ ГРАФОВ

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

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

Графом С называется любая пара (V, 1Т), где V- {у,, у2, ...} — множество элементов любой природы, а 1/= {, и2,...} — семейство пар элементов из V, причем допускаются пары вида (у,-, у,-) и одинаковые пары. Если пары в 1/рассматриваются как неупорядоченные, то граф называется неориентированным; если как упорядоченные, то граф называется ориентированным {орграфом).

Один из наиболее распространенных матричных способов задания графов — это матрица смежности Э (Ух V):

_ Г1, если 3 ребро или дуга (у,-, уу );

1 0 — в противном случае.

Матрица смежности неориентированного графа симметрична относительно главной диагонали, в то время как матрица смежности ориентированного графа имеет, вообще говоря, произвольный вид.

Графы с большим количеством вершин и относительно небольшим количеством ребер более эффективно можно задать при помощи матрицы инциденцийЛ (1/х V). Матрица инциденций для ориентированных графов:

если уу исток дуги «,?;

если Уу сток дуги ?/,?;

если Уу не инцидентна дуге иг

Матрица инциденций для неориентированных графов:

Г1, если Уу инцидентна ребру и,-; а(‘>Л |о^ если не инцидентна ребру иг

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

Также применяется способ задания при помощи функционального представления Г1 и Г-1:

Г1 (у,) = {Уу}: 3 дуга (у,., у,); г-1 (У/) = {Уу}: 3 дуга (уу, у,-).

Строкам матрицы смежности ориентированного графа соответствует функция Г|(У(), а столбцам — Г_|(У(). Функции г'(У|) и Г_|(У|) в представлении неориентированного графа совпадают и обозначаются ПРОСТО Г(У;).

Задачи

Задача 2.1. Дан ориентированный граф, заданный графическим способом (рис. 2.1).

Задать этот граф тремя другими способами:

  • а) с помощью матрицы смежности;
  • б) с помощью матрицы инциденций;
  • в) с помощью функционального представления.

Решение.

Как видно из графического представления, граф содержит 12 вершин. Теперь можно начинать построение требуемых способов задания графа.

а) Построение матрицы смежности. Сначала необходимо отметить принципиальное отличие между матрицей смежности ориентированного и неориентированного графа.

В случае ориентированного графа матрица ^ не обязательно должна быть симметричной. Например, как видно из рис. 2.1, дуга (уь у2) принадлежит множеству и, а дуга (у2, У]) — нет.

Сначала построим матрицу размерности 12 х 12, по вертикали и горизонтали перечислив вершины у,. Рассмотрим вершину ур Как видно из графического представления графа, из V! исходят дуги, приходящие в вершины у2, у3, у10, поэтому в соответствующих им ячейках строки У! ставим единицы. Далее рассмотрим вершину у2: по той же схеме получаем единицу в столбце у3.

Продолжая этот алгоритм для всех оставшихся вершин, получим матрицу смежности (табл. 2.1).

Таблица 2.1

Решение задачи 2.1, а

V

У1

у2

Уз

У4

У5

Уб

Уу

У8

У9

Ую

Уц

Уц

У]

0

1

1

0

0

0

0

0

0

1

0

0

у2

0

0

1

0

0

0

0

0

0

0

0

0

у3

0

0

0

1

0

1

0

0

0

0

0

0

У4

0

0

0

0

1

0

0

0

0

0

0

0

У5

0

0

0

0

0

0

0

0

1

0

0

0

Уб

0

0

0

0

0

0

0

0

0

1

0

0

У?

0

0

0

1

0

0

0

1

0

0

1

0

у8

0

0

0

0

0

0

0

0

1

0

0

1

У9

0

0

0

0

0

0

0

0

0

0

0

1

У|о

0

1

0

0

0

0

0

0

0

0

1

0

Уц

0

0

0

0

0

0

1

0

0

0

0

0

Уц

0

0

0

0

0

0

1

0

0

0

1

0

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

Сначала необходимо пронумеровать все дуги исходного графа. Стоит так же заметить, что вершинам у7иуп инцидентны одновременно две разнонаправленные дуги. Возможная нумерация ребер графа предложена на рис. 2.2. Далее построим матрицу размерности 20 х 12, по строкам перечислив дуги иа по столбцам — вершины уу. Рассмотрим вершину у,: она является истоком дуг их, и7 и м8, поэтому в соответствующих им строках столбца проставляем единицы. Вершина у3 является истоком дуг и2 и и5 и стоком для дуги их, поэтому

в ячейках матрицы А на пересечении и2, и5 и V3 проставляем единицы, а на пересечении и2 и у3 — минус единицы.

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

в) Построение функционального представления. Функциональное представление достаточно просто строится с помощью графического задания этого графа. Но наиболее простым путем здесь будет построение с помощью матрицы смежности. Несложно заметить, что строкам матрицы смежности соответствует функция Г^у,), а столбцам — Г-1 (у,)- Таким образом, получим:

Г‘(У1) = ^2, vз, у|0};

г~11) = 0;

г'(у2) = {у3>;

Г“'(у2) = {У1, у10};

Г'(у3) = {у4, у6};

Г"|3) = {у1, у2};

Г14) = {у5};

Г_14) = {у3, у7};

Г15) = {у9};

Г_15) = {у4};

г‘(у6) = {ую};

г_16) = {у3};

Г17) = {у4, у8, V,,};

Г“17) = {у11, у12};

Г18) = {';9, ^2};

Г_|8) = {у7};

г‘(у9) = {у12};

Г"'(у9) = {у5, у8};

Г1(Ую) = {у2, уп);

т_|(у,0)= {уп ув1;

г1(уп) = ^ц};

Г_1(уц) = {у7, у12};

Г1(у12) = {у7, уи};

Г_1(У12) = {у8, у12}.

Задача 2.2. Дан ориентированный граф, заданный графическим способом (рис. 2.3).

Решение задачи 2.1, б

^1

г2

у3

^5

п,

V?

^8

г9

*10

VII

VII

и1

1

0

-1

0

0

0

0

0

0

0

0

0

и2

0

0

1

-1

0

0

0

0

0

0

0

0

Ч

0

0

0

1

-1

0

0

0

0

0

0

0

и4

0

0

0

0

1

0

0

0

-1

0

0

0

“5

0

0

1

0

0

-1

0

0

0

0

0

0

ч

0

0

0

-1

0

0

1

0

0

0

0

0

и7

1

0

0

0

0

0

0

0

0

-1

0

0

Ч

1

-1

0

0

0

0

0

0

0

0

0

0

и9

0

-1

0

0

0

0

0

0

0

1

0

0

и

0

0

0

0

0

1

0

0

0

-1

0

0

“и

0

0

0

0

0

0

-1

0

0

0

1

0

и2

0

0

0

0

0

0

1

0

0

0

-1

0

«із

0

0

0

0

0

0

-1

0

0

0

0

1

«14

0

0

0

0

-1

0

0

1

0

0

0

0

«15

0

0

0

0

0

0

0

0

1

0

0

-1

иЬ

0

0

0

0

0

0

0

0

0

1

-1

0

«]7

0

0

0

0

0

0

0

0

0

0

-1

1

м18

0

0

0

0

0

1

-1

0

0

0

0

0

«19

0

0

0

0

0

0

1

-1

0

0

0

0

и2()

0

0

0

0

0

0

0

1

-1

0

0

0

Задать этот граф тремя другими способами: с помощью матрицы смежности; с помощью матрицы инциденций; с помощью функционального представления.

Задача 2.3. Дан ориентированный граф, заданный матрицей ин-циденций (табл. 2.3).

Таблица 2.3

Условие задачи 2.3

1

2

3

4

5

6

7

8

9

их

1

-1

и2

1

-1

«3

1

-1

и4

1

-1

“5

-1

1

“ь

-1

1

«7

1

-1

«8

-1

1

и9

1

-1

и()

-1

1

и

-1

1

и2

-1

1

Задать этот граф тремя другими способами:

  • а) графически;
  • б) с помощью матрицы смежности;
  • в) с помощью функционального представления.

Задача 2.4. Дан неориентированный граф, заданный матрицей смежности (табл. 2.4).

Таблица 2.4

Условие задачи 2.4

V

^1

V4

V5

V6

V!

V8

^1

1

1

у2

1

1

1

1

^3

1

1

1

1

^4

1

1

1

1

^5

1

1

^6

1

1

1

^7

1

1

^8

1

1

Задать этот граф тремя другими способами:

  • а) графически;
  • б) с помощью матрицы инциденций;
  • в) с помощью функционального представления.
 
<<   СОДЕРЖАНИЕ   >>