Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
865.doc
Скачиваний:
2
Добавлен:
01.07.2025
Размер:
591 Кб
Скачать
☆

Завдання 10

Скільки різних трикольорових прапорів можна зробити, маючи 5 кольорів, якщо на кожному прапорі має бути червоний?

Розв’язування:

Місце для червоного кольору можна обрати трьома способами. Після цього залишаться дві вільних смуги. Для першої зверху смуги можна вибрати колір 4 способами. Тоді для останньої смуги залишиться 3 можливих кольори. За правилом множення загальна кількість різних трикольорових прапорів складе

3*4*3 = 36.

Завдання 11

Скількома різними способами можна розмістити п'ять різних книжок на книжковій полиці?

Розв’язування:

Кількість способів, якими п’ять різних книжок можна розмістити на книжковій полиці, дорівнює кількості перестановок з 5 елементів, тобто 5!= 120.

Завдання 12

Скільки тризначних чисел можна скласти з цифр 0, 1, 2, 3, 4, 5, якщо цифри можуть повторюватися?

Розв’язування:

Першу цифру можна вибрати п’ятьма способами, оскільки цифра 0 не може стояти на першому місці. Кожну з двох інших цифр можна вибрати 6 способами.

Тоді за правилом множення шукана кількість тризначних чисел дорівнює

5*6*6 = 180.

Завдання 13

Скільки тризначних чисел можна скласти з цифр 0, 1, 2, 3, 4, 5, якщо ні одна цифра не може повторюватися?

Розв’язування:

Перша цифра тризначного числа не може бути нулем, тому її обрати можна 5 способами.

Друга цифра не може збігатися з першою, тому її можна обрати 5 способами.

Третя цифра не може збігатися з першими двома, тому її можна обрати 4 способами.

Тоді за правилом множення шукана кількість тризначних чисел дорівнює

5*5*4 = 100.

Завдання 14

Скількома способами можна упорядкувати множину так, щоб останні два елементи були і ?

Розв’язування:

За умовою треба впорядкувати елементи. Тому шукана кількість способів дорівнює кількості перестановок з елементів, тобто

Графи

Задано граф G = (X,U), вершини і ребра (дуги) якого пронумеровані числами натурального ряду.

Побудувати:

  1. Матриці суміжності і інцидентності для орієнтованого та неорієнтованого графів.

  2. Матрицю ланцюгів для неорієнтованого графу та матрицю шляхів для орієнтованого графу.

  3. Матрицю циклів неорієнтованого графу та матрицю контурів орієнтованого графу.

  4. Знайти всі можливі шляхи з 1 в 4.

  5. Знайти мінімальний шлях за алгоритмом Дейкстри.

  6. Перемалювати в неорієнтований граф та знайти мінімальне остовне дерево.

  7. Знайти гамільтонів шлях, якщо він існує.

Розв’язування:

1. Матриця суміжності показує, які вершини з’єднані ребрами або дугами.

Матриця суміжності для орієнтованого графа:

.

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

.

Матриця інцидентності показує інцидентність вершин і ребер.

Матриця інцидентності для орієнтованого графа:

.

Матриця інцидентності для неорієнтованого графа:

.

2. Матриця ланцюгів для неорієнтованого графа показує, чи існує ланцюг між вершинами:

Матриця шляхів для орієнтованого графу показує, чи існує шлях з однієї вершини до іншої:

3. Знайдемо всі прості цикли неорієнтованого графа. Запишемо кожен цикл послідовністю вершин:

Z1 = {1,2,3,1}, Z2 = {1,2,4,1}, Z3 = {1,2,5,3,1}, Z4 = {1,2,5,4,1},

Z5 = {1,3,2,4,1}, Z6 = {1,3,5,4,1}, Z7 = {1,2,3,5,4,1}, Z8 = {1,2,4,5,3,1},

Z9 = {1,3,2,5,4,1}, Z10 = {1,3,5,2,4,1}, Z11 = {2,3,5,2}, Z12 = {2,4,5,2},

Z13 = {2,3,5,4,2}.

Складемо матрицю циклів неорієнтованого графу, де простим циклам відповідають рядки, а стовпчикам відповідають ребра.

Знайдемо всі контури орієнтованого графа. Запишемо кожен контур послідовністю вершин:

Z1 = {1, 2, 5, 3, 1}, Z2 = {2, 5, 3, 2}.

Складемо матрицю контурів орієнтованого графу, де контурам відповідають рядки, а стовпчикам відповідають ребра.

4. Знайдемо всі можливі шляхи з 1 в 4. Одержимо три можливих шляхи, запишемо їх послідовністю вершин:

1-4, 1-2-4, 1-2-5-4.

5. Знайдемо мінімальний шлях за алгоритмом Дейкстри з вершини 1 до вершини 4. Вагами ребер будемо вважати їх номери.

Етап 0. Призначаємо вершині 1 постійну позначку [0, –].

Етап 1. З вершини 1 можна досягти вершин 2 і 4. Обчислюємо позначки для цих вершин, в результаті одержимо таку таблицю позначок.

Вершина

Позначка

Статус

1

[0, –]

постійна

2

[0+1, 1] = [1, 1]

тимчасова

4

[0+9, 1] = [9, 1]

тимчасова

Серед вершин 2 і 4 вершина 2 має найменше значення відстані, тому статус позначки цієї вершини змінюється на постійний.

Етап 2. З вершини 2 (останньої вершини з постійною позначкою) можна потрапити в вершини 4 і 5. Отримаємо такий список вершин:

Вершина

Позначка

Статус

1

[0, –]

постійна

2

[0+1, 1] = [1, 1]

постійна

4

[1+2, 2] = [3, 2]

тимчасова

5

[1+8, 2] = [9, 2]

тимчасова

Статус позначки вершини 4 змінюємо на постійний.

Вершина

Позначка

Статус

1

[0, –]

постійна

2

[0+1, 1] = [1, 1]

постійна

4

[1+2, 2] = [3, 2]

постійна

5

[1+8, 2] = [9, 2]

тимчасова

Найкоротший шлях визначаємо, використовуючи позначки, починаючи з вершини 4. Одержимо такий найкоротший шлях довжиною 3:

1-2-4.

6. Перемалюємо граф в неорієнтований граф.

Знайдемо мінімальне остовне дерево, використовуючи алгоритм Прима. Спочатку виберемо вершину 1.

На кожному кроці до поточного дерева додається найлегше ребро, яке з’єднує вершину з побудованого дерева, і вершину не з дерева.

З вершини 1 виходять три ребра. Найменшу вагу має 1-2, тому додамо ребро 2. Отже, дерево Х={1-2}.

З цих двох вершин виходять п’ять ребер, найменшу вагу з них має 2-4. Тому додамо це ребро: Х={1-2, 2-4}.

Перелік ребер, з яких треба вибрати найлегше ребро:

1-3 (6), 2-3 (7), 2-5 (8), 4-5 (4).

Отже, додаємо ребро 4-5: Х={1-2, 2-4, 4-5}.

Перелік ребер, з яких треба вибрати найлегше ребро:

1-3 (6), 2-3 (7), 5-3 (5).

Отже, додаємо ребро 5-3:

Х={1-2, 2-4, 4-5, 5-3}.

Всі вершини знаходяться в дереві. Робота алгоритму завершено. Маємо такий найкоротший остов.

Підсумкова довжина буде дорівнювати

1+2+4+5 = 12.

7. Шлях 1, 2, 4, 5, 3 буде гамільтоновим.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]