ки, теорія алгоритмів, Лінійне програмування, математичне моделювання, теорія кодування.
У документах UNESCO вказується, что потрібен переглядання всієї системи Вивчення математичних наук з Посилення роли діскретної математики.
розв язанням
Завдання 1
заданої матриці суміжності графа
01000 10201 02001 00000 01101
Завдання 1.1
Побудуваті граф.
Завдання 1.2
Е={(V1, V2), (V2, V5), (V2, V3), (V2, V3), (V5, V5), (V3, V5)}
Завдання 1.3
(V, E)=5 - вершини=6 - ребра (V1)=1 (V2)=4 (V3)=3 (V4)=0 (V5)=4
Завдання 1.4
Створюємо матрицю інцідентності графа. Матриця буде НЕ булевом оскількі на вершіні V5 петля.
E1E2E3E4E5E6V1100000V2111100V3011010V4000000V5000112
Завдання 1.5
Будуємо граф ізоморфній даного.
Завдання 1.6
Ейлерового циклу у даного графі НЕ існує того, что вершина V1 висячі, тобто існує только Одне ребро, что з єднує ее з усіма іншімі вершинами. Це перешкоджає умів циклу того, что Кожна вершина винна буті інцідентною хоча б двом ребрам, щоб утворіті цикл Ейлера.
Завдання 1.7
Гамільтонів цикл та шлях у графі неможліві оскількі вершина ізольована, а Гамільтонів цикл та шлях передбачають відвідування всех вершин графа.
Завдання 1.8
Задаємо графу довільні ваги, тобто утворюємо зваження граф. Та Знайдемо найкоротшій шлях з вершини V1 до вершини V2.
) почнемо з вершини V1, відстань до всіх других вершин?, а до даної вершини 0.
) Оскількі інує только Одне ребро інцідентне V1, то далі йдемо до вершини V2 з вагою ребра, з єднуючого ЦІ вершини 3.
) З V2 йдемо до вершини V5 того, что вага ребра ведучого до V5 найменша (4 lt; 7 lt; 8).
) З V5 йдемо до V3 з вагою 2 і отрімаємо 3 + 4 + 2=9 - найкоротшій шлях до вершини V3 за алгоритмом Дейкстри.
Завдання 1.9
Створюємо довільній граф з п ятьма вершинами та розфарбовуємо его, причому так, щоб суміжні вершини не були розфарбовані в Однаково колір.
хроматична число?- Це найменша можлива Кількість кольорів застосовання при розфарбуванні графа.
Для даного графа? (G)=3
Завдання 2
Дано дерево
Завдання 2.1
Корінь - a
Сині - b, c
Листки - d, e, k, l, m, q, r, s, u, v, p
Внутрішні вершини - a, b, c, f, g, h, i, j, n, o, t
Завдання 2.2
-ий рівень, cI рівень, e, f, g-II рівень, i, j-III рівень, l, m, n, o, p-IV рівень, r, s, tV рівень, v-VI рівень
Висота дерева h=5
Завдання 2.3
Завершення назівають дерево у которого всі листки на одному Рівні. Дані дерево не являється завершеним.
Завдання 2.4
збалансованності деревом висота h назівають дерево, если всі его листки розташовані на рівнях h - 1 та h. Дані дерево не являється збалансованності.
Завдання 2.5
) Обхід у прямому порядку
) Обхід у внутрішньому порядку.
) Обхід у зворотнього порядку
Завдання 2.6
Ес (х) -ексцентрісітет вершини х- максимальна відстань від даної вершини до всіх других вершин (вимірюється в кількості ребер).
Ес (a)=6
Ес (b)=7
Ес (c)=5
Ес (d)=8 diametr=8
Ес (e)=8 radius=4
Ес (f)=6 центр дерева у вершіні g
Ес (g)=4
Ес (h)=7
Ес (i)=5
Ес (j)=5
Ес (k)=8
Ес (l)=8
Ес (m)=8
Ес (n)=6
Ес (o)=6
Ес (p)=6
Е...
