<<
>>

Основные определения.

Пусть Х – множество вершин, V –множество ребер, соединяющие вершины. Граф G=(X,V) cчитается заданным, если дано множество его вершин Х и способ отображения Г этого множества в самого себя.

Подграфом GA графа G=(Х, Г) называется граф, в который входит лишь часть вершин графа G, образующих множество А, вместе с дугами, соединяющими эти вершины:

где .

Частичным графом GD по отношению к графу G=(Х, Г) называется граф, содержащий только часть дуг графа G, т.е. определяемый условием:

где .

Важными понятиями в теории графов являются понятия пути, длины пути, контур

. Для описания графа используются матрицы смежности и матрицы инцидентности.

Пример 2.1 Построить граф G, заданный множеством вершин Х={X1, X2, X3, X4} и их отображениями Г(Х1)={X1, X2}, Г(Х2)={X3, X4}, Г(X3)={X1, X4}, Г(Х4)={X1, X2, X3}.

X1
X2
Решение. Данный граф приведен на рис. 2.1

X4
X3

Рис.

2.1

Два графа G1 и G2 изоморфны, если существует такое взаимно-однозначное соответствие между множествами их вершин Х1 и Х2, что вершины соединены ребрами в одном из графов в том и только том случае, когда соответствующие им вершины соединены в другом графе. Если ребра ориентированы, то их направления также должны соответствовать друг другу.

Пример 2.2 Изоморфны ли графы, изображенные на рис. 2.2 и 2.3?

A2
A1

Рис.2.2

B1
B2

Рис. 2.3

Решение. Графы А1 и А2 не изоморфны, хотя они и имеют одинаковое число вершин и ребер. Но в графе А1 одно из ребер направлено от а к b, а в графе А2 оно направлено в другую сторону. Графы В1 и В2 изоморфны, т.к. они имеют одно и то же число вершин и любые две вершины графа В1 соединены ребром только тогда, когда соответствующие им вершины графа В2 также соединены ребром.

Пример 2.3 Являются ли полными (без учета петель) графы А1, В1, изображенные на рис. 2.2 и 2.3?

Решение. Граф В1 не является полным, т.к.

не все пары его вершин соединены ребрами. Например, (а1, а6), (а3, а8) и другие. Граф А1 не является полным, т.к. ребро (a, b) ориентировано только в одном направлении.

Рис. 2.4

Пример 2.4 Дан ориентировнный граф (рис. 2.4). Построить его матрицы смежности и инцидентности.

Решение. В соответствии с определением матрица смежности есть квадратная матрица с элементами множества вершин в качестве координат ее столбцов и строк.

Элемент матрицы в строке i и столбце j равен 1, если есть ребро от вершины i к вершине j, -1- если есть ребро к вершине i от вершины j и 0 – если вершины i и j не соединены. Матрица смежности приведена в таблице 2.1

Таблица 2.1 Таблица 2.2

V

X

a b c d V

X

V1 V2 V3 V4
a 0 1 0 1 a 1 0 0 1
b -1 0 -1 1 b -1 -1 1 0
c 0 1 0 0 c 0 1 0 0
d -1 -1 0 0 d 0 0 -1 -1

В матрице инцидентности координатами строк являются элементы множества вершин, а координатами столбцов – элементы множества ребер. Элемент матрицы в строке i и столбце j равен 1, если ребро j исходит из вершины i, -1 – если ребро j входит в вершину i, 0 – если ребро j не инцидентно вершине i. Матрица инцидентности приведена в таблице 2.2.

Пример 2.5 На рис.

2.5. задан граф G. Построить матрицу смежности и выяснить, сколько путей длины три существует в графе G.

Х2 Х4

V1 V2 V3

X1 X3

Рис. 2.5

Решение.

Элемент , следовательно, в данном графе существует единственный путь длиной три. Это путь из вершины Х1 в вершину Х4:

.

Все элементы матрицы А4 равны нулю, следовательно, в графе отсутствуют пути длиной четыре.

<< | >>
Источник: Алексеев В.В.. Элементы теории множеств и теории графов (Сборник задач и упражнений по курсу “Дискретная математика”). 2001

Еще по теме Основные определения.:

  1. Глава 11ОСНОВНЫЕ ЧЕРТЫ ДУХОВНОСТИ РУССКОГО НАРОДА
  2. 2.1. Основные определения
  3. 3.1 Основные определения
  4. 5.1 Основные определение.
  5. (§12. Основные определения, характеризующие аналитические и синтетические утверждения}[127]
  6. § 2. Методологические проблемы определения понятия «экологическое преступление»
  7. Основные определения
  8. Основные определения
  9. 4.1. Основные определения. Частные производные. Дифференциалы.
  10. Конечные графы и сети. Основные определения.
  11. Ряды. Основные определения.