Варіант №1
Скачати 172.17 Kb.
|
| Контрольна робота з “Основ дискретної математики” 2008-2009 н.р. |
| 7 | 5 |
| 5 | 2 |
| 4 | 4 |
| 3 | 6 |
| 5 | 6 |
| 6 | 3 |
| 5 | 1 |
| 4 | 1 |
Рисунок. Стрічкова матриця графа
Завдання 2. Розробити алгоритм перетворення довільної стрічкової матриці графа в матрицю cуміжності. Проілюструвати роботу алгоритму на матриці з завдання 1.
Завдання 3. Матриця відстаней між вершинами графа наведена в таблиці. Знайти маршрути мінімальної довжини для кожної пари вершин. Визначити ребра графа, збільшення довжини яких не відобразиться на мінімальних маршрутах.
^
| | A | B | C | D | E | F |
| A | 0 | – | 10 | 30 | – | 25 |
| B | – | 0 | – | – | 8 | – |
| C | 10 | – | 0 | 11 | – | 3 |
| D | 30 | – | 11 | 0 | 22 | 11 |
| E | – | 8 | – | 22 | 0 | 10 |
| F | 25 | – | 3 | 11 | 10 | 0 |
^
Завдання 1. Намалювати граф за матрицею cуміжності, яку наведено в таблиці 1. Обґрунтувати переваги на недоліки представлення графа матрицею суміжності та стрічковою матрицею.
^
| | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 1 | 0 | 1 | 0 | 0 | 1 |
| 2 | 0 | 1 | 0 | 0 | 1 | 0 |
| 3 | 0 | 0 | 0 | 0 | 1 | 0 |
| 4 | 1 | 0 | 0 | 0 | 0 | 0 |
| 5 | 0 | 1 | 1 | 0 | 0 | 0 |
| 6 | 0 | 0 | 0 | 1 | 1 | 0 |
Завдання 2. Розробити алгоритм перетворення довільної матриці суміжності графа в стрічкову матрицю. Проілюструвати роботу алгоритму на матриці з завдання 1.
Завдання 3. Матриця відстаней між вершинами графа наведена в таблиці 2. Знайти маршрути мінімальної довжини для кожної пари вершин. Визначити ребра графа, збільшення довжини яких не відобразиться на мінімальних маршрутах.
^
| | A | B | C | D | E | F |
| A | 0 | – | 10 | 30 | – | 25 |
| B | – | 0 | – | – | 8 | – |
| C | 10 | – | 0 | 11 | – | 3 |
| D | 30 | – | 11 | 0 | 22 | 11 |
| E | – | 8 | – | 22 | 0 | 10 |
| F | 25 | – | 3 | 11 | 10 | 0 |
Завдання 1. Намалювати граф за стрічковою матрицею, яку наведено на рисунку. Обґрунтувати переваги на недоліки представлення графа матрицею суміжності та стрічковою матрицею.
-
7
5
2
2
4
4
3
6
5
6
6
3
5
1
7
1
Рисунок. Стрічкова матриця графа
Завдання 2. Розробити алгоритм перетворення довільної стрічкової матриці графа в матрицю cуміжності. Проілюструвати роботу алгоритму на матриці з завдання 1.
Завдання 3. Матриця відстаней між вершинами графа наведена в таблиці. Знайти маршрути мінімальної довжини для кожної пари вершин. Визначити ребра графа, збільшення довжини яких не відобразиться на мінімальних маршрутах.
^
| | A | B | C | D | E | F |
| A | 0 | – | – | 20 | – | 25 |
| B | – | 0 | – | – | 8 | – |
| C | 10 | – | 0 | 10 | – | 3 |
| D | 20 | – | 11 | 0 | 22 | 11 |
| E | – | 8 | – | 5 | 0 | 10 |
| F | 25 | – | 3 | 11 | 10 | 0 |
Завдання 1. Намалювати граф за матрицею cуміжності, яку наведено в таблиці 1. Обґрунтувати переваги на недоліки представлення графа матрицею суміжності та стрічковою матрицею.
^
| | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 1 | 0 | 0 | 0 | 0 | 1 |
| 2 | 0 | 1 | 0 | 0 | 1 | 0 |
| 3 | 0 | 0 | 1 | 0 | 1 | 0 |
| 4 | 1 | 0 | 0 | 0 | 0 | 0 |
| 5 | 0 | 1 | 1 | 0 | 0 | 0 |
| 6 | 0 | 0 | 0 | 1 | 1 | 0 |
Завдання 2. Розробити алгоритм перетворення довільної матриці суміжності графа в стрічкову матрицю. Проілюструвати роботу алгоритму на матриці з завдання 1.
Завдання 3. Матриця відстаней між вершинами графа наведена в таблиці 2. Знайти маршрути мінімальної довжини для кожної пари вершин. Визначити ребра графа, збільшення довжини яких не відобразиться на мінімальних маршрутах.
^
| | A | B | C | D | E | F |
| A | 0 | – | 10 | 30 | – | 25 |
| B | – | 0 | – | – | 8 | – |
| C | 20 | – | 0 | 11 | – | 3 |
| D | 3 | – | 11 | 0 | – | 11 |
| E | – | 8 | – | 22 | 0 | 10 |
| F | 5 | – | 3 | 11 | 10 | 0 |
Варіанти №№5-24
Задача 1. Розв’язати задачу комівояжера методом динамічного програмування. Матрицю відстаней для усіх варіантів наведено в табл. 1. Звіт має містити усі проміжні результати. За зразок оформлення можна взяти С.103-104 з книги [1].
Задача 2. Побудувати мінімальне остовне (кістякове) дерево для графу з задачі 1. Граф зробити неорієнтованим, без кратних ребер. Розв’язання задачі здійснити за пожадливим алгоритмом. За зразок оформлення можна взяти С.225–228 з книги [3].
Задача 3. Знайти мінімальні відстані між кожною парою вершин графа з задачі 1. Розв’язання задачі здійснити за алгоритмом Флойда. За зразок оформлення можна взяти С.238–241 з книги [3].
^
| | | | | | | | | | | |
A | 0 | 29 | 13 | 18 | 6 | 18 | 14 | 23 | 24 | 12 |
| | 7 | 0 | 26 | 27 | 11 | 2 | 28 | 24 | 20 | 23 |
| | 16 | 13 | 0 | 20 | 24 | 18 | 9 | 18 | 26 | 17 |
| | 17 | 27 | 28 | 0 | 23 | 25 | 23 | 18 | 20 | 13 |
| | 18 | 15 | 25 | 19 | 0 | 26 | 5 | 3 | 14 | 21 |
| | 22 | 23 | 24 | 19 | 21 | 0 | 21 | 27 | 12 | 26 |
| | 6 | 29 | 17 | 9 | 18 | 27 | 0 | 17 | 30 | 23 |
| | 11 | 5 | 13 | 18 | 14 | 17 | 17 | 0 | 6 | 30 |
| | 19 | 27 | 13 | 28 | 8 | 22 | 23 | 22 | 0 | 29 |
| | 7 | 10 | 14 | 10 | 25 | 25 | 18 | 21 | 20 | 0 |
Таблиця 2
^| Варіант | Початковий та кінцевий пункт | Проміжні пункти |
| | A | B C D E |
| | B | J C F G |
| | C | B I H J |
| | D | J F G I |
| | E | G H I A |
| | F | E D B C |
| | G | F J B C |
| | H | A B C D |
| | I | E F G H |
| | J | D F G A |
| | A | E C F G |
| | B | I E H J |
| | C | A B G I |
| | D | C H I A |
| | E | I A B C |
| | F | D J B C |
| | G | A H C D |
| | H | E F G A |
| | I | D J G B |
| | J | B D F I |
Література
1. Глушков В.М. Введение в АСУ. К.Техніка – 1974.
2. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1988.– 480 с.
3. Таха Х. Введение в исследование операций. – М.: Издательский дом «Вильямс», 2001. – 911 с.
Завдання розробив професор кафедри КСУ С.Д.Штовба,
Вінницький національний технічний університет,
shtovba@ksu.vstu.vinnica.ua
www.vinnitsa.com/shtovba
Схожі:
 | Варіант а варіант Б З кожної пари професій виберіть одну, найбільш привабливу для вас І запишіть на бланку для відповідей: номер питання та варіант (А... | | Завдання для самостійної роботи студентів І курсу фізико-математичного факультету спеціальностей «Математика та основи інформатики» Варіант Вашої роботи визначається номером у списку групи (за журналом). Варіант 1 виконують студенти, номери яких 1, 11 та 21; варіант... |
| Завдання для самостійної роботи студентів І курсу фізико-математичного факультету спеціальностей «Математика та основи інформатики» Варіант Вашої роботи визначається номером у списку групи (за журналом). Варіант 1 виконують студенти, номери яких 1, 11 та 21; варіант... | | Завдання для самостійної роботи студентів ІІІ курсу фізико-математичного факультету спеціальностей «Математика та основи інформатики» Варіант Вашої роботи визначається номером у списку групи (за журналом). Варіант 1 виконують студенти, номери яких 1 та 21; варіант... |
| Завдання для самостійної роботи студентів ІІІ курсу фізико-математичного факультету спеціальностей «Математика та основи інформатики» Варіант Вашої роботи визначається номером у списку групи (за журналом). Варіант 1 виконують студенти, номери яких 1 та 16; варіант... | | Ііі варіант ІV варіант |
| Інформація про видання Назва видання issn (електронний варіант) (якщо є) issn ( друкований варіант) (якщо є) Відповідальний редактор Надіслати три його номери (спочатку надсилається поточний номер видання, а потім два наступних (одразу після їх опублікування) та... | | Завдання для самостійної роботи студентів Варіант Вашої роботи визначається номером у списку групи (за журналом). Номер варіанта – це остача від ділення на 15 Вашого номеру... |
| Завдання для самостійної роботи студентів Варіант Вашої роботи визначається номером у списку групи (за журналом). Номер варіанта – це остача від ділення на 15 Вашого номеру... | | Робочий зошит з дисципліни «кредитування І контроль» Кредитування І контроль”. Кожен студент обирає свій варіант у відповідності до порядкового номера у журналі обліку занять академічної... |
| Варіант 17 |