Елементи теорії графів

B = AAT – diag[d1, d2, …, dn],

де AT– це транспонована матриця A, di – степінь i-ї вершини, diag[d1, d2, …, dn] – діагональна матриця з елементами d1, d2, …, dn на головній діагоналі.

Трох****

1.3. Графи та відношення

Граф як форма подання відношення на множині V. Об'єднання, перетин та композиція (добуток) графів. Відбиття властивостей відношень на графах. Декартовий добуток графів.

Транзитивне, транзитивно-рефлексивне та транзитивно-рефлексивно-симетричне замикання відношення суміжності. Зв'язок із матрицею суміжності та її степенями.

Задачі

****

2. Шляхи в графах

Шлях, ланцюг, цикл, прості шляхи. Зв'язність. Компонент зв'язності. Відстані між вершинами. Діаметри, радіуси, центри.

Задачі

****ГС1: 5, 6, 7, 8, 10, 11, 12, 14(2), 15(2), 25(4, 5), 26, 27, 39(1, 2)

РНД8.8: 4,

ГС4: 6(1абв), 8(1, 3),

Відмітки-відстані на ребрах. Найкоротші шляхи. Алгоритм Дейкстри.

****

Ейлерові ланцюги та графи. Теорема Ейлера. Гамільтонові цикли та ланцюги. Задача комівояжера.

Задачі

****(Ейл.ц.)РНД8.8: 52, на малюнках.

****(Гам.ц.)ГС1: 32, 33, 35, 36, 37, 38, 42, 43

3. Дерева

Дерево, ліс. Код дерева. Охоплююче дерево (каркас, кістяк) мінімальної ваги. Алгоритми Прима та Краскала.

ГС4: 1', 2, 3, 4, 5', 6(2), 7, 8(2), 9, 10, 11, 12, 13(…), 14, 15, 16, 17, 25(1)****про коди: 18(…), 19(…), 20(1, 2), 21(…), 22, 23, 25(2)

РНД8.8: 10, 28,