Page 4 - 4386

ЗМІСТ

ВСТУП ................................................................................................. 5
1 ОСНОВНІ ПОНЯТТЯ ТА ВИЗНАЧЕННЯ. ГРАФИ ТА

ДІЇ НАД ГРАФАМИ. ІЗОМОРФІЗМ ГРАФІВ. ЧАСТКОВІ

ГРАФИ ТА ПІДГРАФИ ..................................................................... 6

1.1 Основні поняття теорії множин ......................................... 6

1.2 Основні операції над множинами ...................................... 7

1.3 Основні поняття теорії графів. Типи графів ................... 10

1.4 Степінь вершини графа ..................................................... 14
1.5 Операції над графами ........................................................ 16

1.6 Часткові графи і підграфи ................................................. 18
1.7 Ізоморфізм графів .............................................................. 19

2 СПОСОБИ ЗАДАННЯ ГРАФІВ............................................. 22

2.1 Задання графа за допомогою діаграми ............................ 22

2.2 Задання графа переліком його елементів ........................ 22

2.3 Задання графів відповідністю ........................................... 23

2.4 Матриця суміжності, інцидентності та список

ребер графа ....................................................................................... 24

3 МАРШРУТИ НА ГРАФАХ .................................................... 30

3.1 Маршрути в неорієнтованому графі ................................ 30

3.2 Маршрути в орієнтованому графі .................................... 32

3.3 Зв’язність графів, зв’язні компоненти ............................. 34

3.4 Точки зчленування, мости ................................................ 36

3.5 Відстань між вершинами. Метрика на графах ................ 37
3.6 Алгоритм знаходження відстаней від заданої

вершини до інших вершин графа .................................................... 38

3