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

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

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

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

Пример 1.

v₁ v₂

1º v₁, v₃, v₁, v₄ – маршрут, но не цепь.

2º v₁, v₃, v₅, v₂, v₃, v₄ – цепь, но не простая ( т.к. не все

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

3º v₁, v₄, v₃, v₂, v₅ – простая цепь, но не цикл ( т.к. не

v₄v₅ замкнута)

4º v₁, v₃, v₅, v₂, v₃, v₄, v₁ – но не простой ( т.к. цепь не простая хотя, замкнутая)

5º v₁, v₃, v₄, v₁ – простой цикл ( все ребра и все вершины различны)

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

Пример 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 – граф, возможно ориентированный. Маршрут называется путём, если все его дуги различны. Путь называется контуром, если v₀=v_k. Вершина v называется достижимой из вершины u, если <u, v> путь. Расстоянием между вершинами называется длина кратчайшей цепи <u, v>

Пример 3.

2 4 5

1 3

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

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

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

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

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

М =

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

H t wx:val="Cambria Math"/><w:i/><w:sz w:val="28"/><w:sz-cs w:val="28"/></w:rPr><m:t>,</m:t></m:r><m:r><w:rPr><w:rFonts w:ascii="Cambria Math" w:fareast="Times New Roman" w:h-ansi="Cambria Math"/><wx:font wx:val="Cambria Math"/><w:i/><w:sz w:val="28"/><w:sz-cs w:val="28"/><w:lang w:val="EN-US"/></w:rPr><m:t>j</m:t></m:r></m:e></m:d></m:oMath></m:oMathPara></w:p><w:sectPr wsp:rsidR="00000000"><w:pgSz w:w="12240" w:h="15840"/><w:pgMar w:top="1134" w:right="850" w:bottom="1134" w:left="1701" w:header="720" w:footer="720" w:gutter="0"/><w:cols w:space="720"/></w:sectPr></w:body></w:wordDocument>"> =

Пример 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

A_G=(A_{i, j}) = ; A_G=

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

B_G=(B_{i, j}) =

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

J = 1,2,…,n

Пример 2.

a2 4 a3

3

1 2

a1

B_G=

m×n_3×6

Тема: Комбинаторика

1. Размещения из n элементов по m это - упорядоченные подмножества из n элементов по m.

Число размещений

(n-факториал)

2. Перестановки - размещение и n элементов по n т.е. частный случай размещений число перестановок P_n=n!

3. Сочетания – подмножество из п элементов по m, отличающихся друг от друга хотя бы одним элементом называются сочетаниями. Число сочетаний

Пример:

1. Сколькими способами можно расположить 5 различных книг на полке? Р₅=1*2*3*4*5=120 способов.

2. Сколько способов распределить 3 различных путевки среди 8 человек бригады?

3. Сколько способов распределить 3 одинаковых обязанностей в группе из 25 человек?

способов т.к. обязанности одинаковы – это сочетания