Основные определения.
Пусть Х – множество вершин, 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}.
|
|
| |||
| |||
Рис.
2.1Два графа G1 и G2 изоморфны, если существует такое взаимно-однозначное соответствие между множествами их вершин Х1 и Х2, что вершины соединены ребрами в одном из графов в том и только том случае, когда соответствующие им вершины соединены в другом графе. Если ребра ориентированы, то их направления также должны соответствовать друг другу.
Пример 2.2 Изоморфны ли графы, изображенные на рис. 2.2 и 2.3?
|
|
Рис.2.2
|
|
Рис. 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 равны нулю, следовательно, в графе отсутствуют пути длиной четыре.