Задача 1. Пронумерувати вершини графа в порядку їх відвідування методом: а) «в глибину», б) «в ширину» - 10 варіантів. Задача 2. Застосувати алгоритм Прима для знаходження мінімального остовного дерева графа, починаючи з вказанної вершини (8 варіантів): 8) починаючи з вершини H. Задача 3. Застосувати алгоритм Дейкстри для побудови найкоротшого шляху (8 варіантів (від 3 до 8.) Задача 4. Видалити з графа в задачі 1 будь-які три вершини і для отриманого графа: • записати матрицю суміжності, • записати матрицю інцидентності, • записати матрицю Кіркгофа, • знайти кількість остовних дерев, • намалювати три остовних дерева, • знайти вектор степенів, щільність, нещільність, двійковий код, • побудувати хроматичний многочлен і знайти хроматичне число, • намалювати доповнення.
1) a^3 - 8 = (a-2)(a^2+2a+4) - общий знаменатель дополнительные множители к первой дроби = 1, ко второй (а-2) и к третьей = -(a^2+2a+4). в числителе тогда получаем: 4а+4+а(а-2) - 1(a^2+2a+4) = 4а+4+a^2 -2а - a^2 - 2a - 4 =0. Доказано. 2) Знаенатель х^2 - 4 = (х - 2)(х+2), следовательно, (х - 2) в числителе и знаменателе можно сократить, если рассмативать как фнкцию, то не сокращают и тогда х^2 - 4 не равен 0, и х1 не равен - 2, а х2 не равен 2. ответ (- бесконечность ; - 2) и ( - 2; 2) и (2; + бесконечность)
дополнительные множители к первой дроби = 1, ко второй (а-2) и к
третьей = -(a^2+2a+4). в числителе тогда получаем: 4а+4+а(а-2) - 1(a^2+2a+4) =
4а+4+a^2 -2а - a^2 - 2a - 4 =0. Доказано.
2) Знаенатель х^2 - 4 = (х - 2)(х+2), следовательно, (х - 2) в числителе и знаменателе можно сократить, если рассмативать как фнкцию, то не сокращают и тогда х^2 - 4 не равен 0, и х1 не равен - 2, а х2 не равен 2. ответ (- бесконечность ; - 2) и ( - 2; 2) и (2; + бесконечность)