Математика (стр. 4 )

1 V = - множество вершин

3 Е = -

Множество дуг

4

Если имеется несколько дуг, исходящих из вершины v1 в вершину v2 , такие дуги называются кратными, граф называется кратным.

Если все элементы множества Е – упорядоченные пары, то граф G называется ориентированным (орграф), элементы V называются узлами, а множество Е дугами, т. е. если (а, b) E, (b, a) ∉ E

Если элементом Е может быть пара одинаковых (не различных) элементов V, то такой элемент называется петлей, а граф называется графом с петлями (псевдографом). Если Е содержит несколько одинаковых элементов, то эти элементы называются кратными ребрами, a G - мультиграфом.

Если (а, b) E /\ (b, a) E, то G называется неориентированным (неографом). В этом случае дуга называется ребром и обозначается в виде отрезка, соединяющего вершины, а вершины а и b называются концами ребра и информацию об этих дугах пишут: =

или - ребро графа

Маршруты, цепи, циклы. Длина маршрута.

Маршрутом в графе G называется чередующаяся последовательность вершин и ребер: v0, l1, v1, l2,…,lk, vk, в которой любые два соседних элемента инцидентны. Это определение подходит и для псевдо и мультиграфов. В орграфе достаточно указать только последовательность вершин (узлов) или только последовательность ребер (дуг) если v0=vk, то маршрут называется замкнутым, если нет, то открытым.

Если все ребра различны, то маршрут называется цепью, если все вершины различны, то маршрут называется простой цепью В цепи v0 и vk называются концами цепи; цепь соединяющая вершины u и v обозначают < u, v>; замкнутая цепь называется циклом; простая замкнутая цепь прстым циклом. Граф без циклов называется ациклическим.

Для орграфов цепь называется путем, а цикл – контуром.

Пример 1.

v1 v2

1º v1, v3, v1, v4 – маршрут, но не цепь.

2º v1, v3, v5, v2, v3, v4 – цепь, но не простая ( т. к. не все

v3 вершины различны, а различны рёбра)

3º v1, v4, v3, v2, v5 – простая цепь, но не цикл ( т. к. не

v4 v5 замкнута)

4º v1, v3, v5, v2, v3, v4, v1 – но не простой ( т. к. цепь не простая хотя, замкнутая)

5º v1, v3, v4, v1 – простой цикл ( все ребра и все вершины различны)

Длиной маршрута называется количество ребер в нем (с повторениями).

Пример 2.

Дан граф G, в нем:

1 2 (1,2), (1,2,4,7), (3,4,5,6) – простые цепи

(3,4,5,6) – цепь простая, но не ЦИК

3 4 5 6

(1,2,4,7,8,4) – не простая цепь ( есть одинаковые

вершины)

7 8 (1,2,4,7,8,4,1) – цикл, но не простой.

Пусть G – граф, возможно ориентированный. Маршрут называется путём, если все его дуги различны. Путь называется контуром, если v0=vk. Вершина v называется достижимой из вершины u, если <u, v> путь. Расстоянием между вершинами называется длина кратчайшей цепи <u, v>

Пример 3.

2 4 5

 

1 3

Контур (1,2,3)

Вершина 5 достижима из любой вершины; из вершины 5 недостижима ни одна из остальных вершин

Матрица инциденций вершин и ребер

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

Для неографа:

М =

Для ориентированного графа:

H =

Пример 1. (Неограф)

v1 L1 v2

G: L4 L5 L2

v4 L3 v3

G: - матрица инциденций вершин и ребер для графа G

Пример 2.(Орграф)

V1 L1 V2

D: L4 L5 L2

V4 L3 V3

D: - матрица смежности вершин и ребер в орграфе

Матрица смежности вершин

Матрица инциденций вершин отражает смежность вершин.

Пример 1.

а1 а2

G: а5

а3 а4

AG=(Ai, j) = ; AG=

Для мультиграфа G матрица инцидентности дуг и вершин

BG=(Bi, j) =

Это – матрица размера m×n, I = 1,2…,m

J = 1,2,…,n

Пример 2.

a2 4 a3

3

 

1 2

a1

BG=

m×n3×6