Материал: baldin_kv_red_matematika_dlia_gumanitariev

графов [25]. Если ребра ориентированы, то их направления также должны соответствовать друг другу.

На рис. 1.22 приведен пример изоморфных графов [10].

Рис. 1.22

В тех случаях, когда необходимо различать изоморфные графы помечают их вершины и (или) ребра (рис. 1.2 ).

вершины и ребра в маршруте могут повторяться. Например,

маршрут V1e1 V2e5 V4e6 V1e8 V6e7 V4 на рис. 1.24.

Маршрут называют открытым, если его конечные вершины различны, в противном случае он является замкнутым, на-

пример маршрут V1e1 V2e5 V4e6 V1e8 V6e7 V4e6V1 на рис. 1.24. Маршрут называют цепью, если все его ребра различны.

Цепь является открытой, если ее конечные вершины различны, в противном случае она — замкнутая.

6

V6

Рис. 1.25

На рис. 1.25 V2e1 V e V5e1 V1e5 V e8V4 — открытая цепь, а V1e1 V5e V e2 V2e1 V e7 V1 — замкнутая цепь.

Открытую цепь называют путем, если все ее вершины раз-

личны, например V4e8 V e6 V1e11 V6 на рис. 1.25.

Замкнутую цепь называют циклом, если все ее вершины за исключением концевых различны, например V e V5e1 V1e7

V на рис. 1.25.

Две несовпадающие вершины Vi и Vj в графе G называется связными, если существует маршрут Vi - Vj.

Граф G называют связным, если две его любые несовпадающие вершины могут быть соединены маршрутом. Например, связными являются графы на рис. 1.24 и 1.25, а несвязным — граф, изображенный на рис. 1.26.

7

Рис. 1.26

Деревьяилес

Большую роль в различных отраслях науки имеют связные ациклические (не имеющие циклов) графы, которые на множест- веVвершинимеютЕ=(V–1)ребер,т. е.G=(V,(V–1)).Этиграфы носят название деревьев [10, 21]. Заметим, что (V – 1) — это минимальное количество ребер для того, чтобы граф был связным.

Примерами древовидной структуры являются генеалогический граф, схема вертикали управления любой организации, совокупность всех файлов, размещенных на диске ПЭВМ. Пример дерева приведен на рис. 1.27.

Несвязный граф, компонентами которого являются деревья, называется лесом (рис. 1.28).

Матрицыграфов

1.Матрица инцидентности.

Рассмотрим простой граф G (без петель и параллельных ребер), имеющий n вершин и m ребер. Ему соответствует матрица инцидентности размера n m, т. е.

АI = [aij], где

8

12 1 14 15 16 17 18 19 20 21 22 2 24 25 26

27 28 29 0 1

Рис. 1.27

Рис. 1.28

Каждый элемент этой матрицы aij в случае ориентированного графа определяется следующим образом [10, 21].

если ребро j инцидентно вершине i и исходит из нее;

если ребро j инцидентно вершине i и входит в нее;

если ребро j неинцидентно вершине i.

В случае неориентированного графа имеем

9

если ребро j инцидентно вершине i; если ребро j неинцидентно вершине i.

Рассмотрим конкретный пример. Имеем ориентированный граф, имеющий 5 вершин и 7 ребер. (рис. 1.29).

Рис. 1.29

Ему соответствует матрица инцидентности размера 5 7 следующего вида

40