Введение в теорию графов

Введение в теорию графов

Граф

G = (V, R)

V – множество вершин

R - множество ребер, соединяющих пару вершин

R 12

V 2

V 1

V 5

R 25

R 15

R 23

R 14

R 45

R 35

V 3

V 4

R 34

Мощность множества – количество вершин (ребер)

вершины

не смежные

смежные

- соединяются ребром

- не соединяются ребром

R 12

V 1

V 2

R 25

R 15

V 5

R 23

R 14

V 6

R 45

R 35

V 4

V 3

R 34

V 6 – изолированная вершина

Степень вершины

- количество инцидентных ей ребер

V 1

3

V 2

3

V 3

V 4

3

3

V 5

4

R 12

V 2

V 1

R 15

R 25

V 5

R 23

R 14

R 45

R 35

V 4

V 3

R 34

Маршрут графа

- последовательность чередующихся вершин и ребер

простая цепь

замкнутый (цикл)

все вершины и ребра различны

начальная и конечная вершины совпадают

R 12

V 2

V 1

V 5

R 15

R 25

R 23

R 14

R 45

R 35

V 4

V 3

R 34

Ориентированный граф

• каждое ребро ( дуга ) имеет одно направление. Дуга – упорядоченная пара вершин.

входящая степень вершины

исходящая степень вершины

- число входящих в вершину дуг

- число исходящих из вершины дуг

Определите входящие и исходящие степени вершин графа:

R 21

V 1

V 2

R 12

R 14

R 23

R 32

R 24

V 1

входящая

исходящая

V 2

V 3

V 4

V 3

V 4

R 34

Взвешенный граф (сеть)

• ребрам или дугам графа поставлены в соответствие числовые величины.

R 21

5

V 2

V 1

R 12

5

4

R 14

R 23

R 32

R 24

8

3

7

V 3

V 4

R 34

5

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

- табличная форма представления графа

номера вершин

1

1

0

2

2

3

35

35

3

4

4

0

0

0

17

32

32

17

0

0

0

18

18

0

несмежные вершины

составить матрицу смежности для ориентированного графа:

5

V 2

V 1

R 12

5

4

R 14

R 23

R 24

R 32

8

3

7

V 3

V 4

R 34

5

Подграф

• граф, у которого все вершины и ребра принадлежат исходному графу.

R 12

V 2

V 1

R 12

V 2

V 1

R 25

V 5

R 15

R 23

R 14

V 5

R 15

R 14

R 45

R 35

V 2

R 45

V 4

V 3

R 34

R 25

V 5

V 4

R 23

R 35

V 3

Остовной связной подграф

• подграф, содержащий все вершины исходного графа и каждая вершина достижима из любой другой.

V 1

V 2

R 12

V 2

V 1

V 5

R 12

R 25

R 15

R 23

R 14

R 45

V 5

R 35

R 23

R 14

V 4

V 3

R 34

R 35

V 4

V 3

R 34

Дерево

• граф, в котором нет циклов.

V 1

V 2

R 12

R 15

V 1

R 25

V 5

V 2

R 23

R 14

R 45

V 5

R 35

R 23

V 4

V 3

R 34

R 35

V 3

V 4

R 34

остовное связное дерево

Преобразование графа в остовное связное дерево минимального веса.

цикломатическое число

γ = m – n + 1

m – количество ребер

n – количество вершин

V 1

V 2

R 12

R 15

V 5

R 25

γ = 8 – 5 + 1= 4

R 23

R 45

R 35

V 4

V 3

R 34

Преобразовать граф в остовные связные деревья:

V 2

V 1

R 12

R 15

R 25

V 5

R 23

R 45

R 35

V 3

V 4

R 34

Алгоритм Крускала

Построение остовного связного дерева минимального веса.

остовной подграф с изолированными вершинами.

1. Удалить из графа все ребра

V 1

V 1

V 2

V 2

R 12

10

3

7

6

V 5

R 25

V 5

R 15

6

R 23

4

R 45

8

R 35

V 4

V 3

V 3

V 4

R 34

10

2. Сортировка ребер по возрастанию весов.

R 12

10

R 12

V 2

V 1

10

R 34

10

3

R 35

8

7

V 5

6

R 25

R 15

6

R 23

7

R 25

R 14

4

8

R 45

R 14

6

R 35

V 4

V 3

6

R 23

R 34

10

R 45

4

R 15

3

3. Ребра последовательно включают в остовное дерево по возрастанию их весов:

10

R 12

R 34

10

V 2

V 1

8

R 35

7

R 25

3

7

R 15

R 25

V 5

6

R 14

6

R 23

4

6

R 45

R 23

R 45

4

V 3

V 4

R 15

3

4. Алгоритм заканчивает работу, когда все вершины будут объединены в одно множество. Оставшиеся ребра не включаются в остовное дерево.

R 12

10

R 34

V 2

10

V 1

8

R 35

3

7

R 15

R 25

V 5

6

R 23

4

6

R 14

R 45

V 3

V 4

γ = 8 – 5 + 1= 4

вес графа = 3 + 4 + 6 + 7 = 20