Варіант №1 icon

Варіант №1




Скачати 172.17 Kb.
НазваВаріант №1
Дата30.06.2012
Розмір172.17 Kb.
ТипДокументи

Контрольна робота з
“Основ дискретної математики”
2008-2009 н.р.


Варіант №1


Завдання 1. Намалювати граф за стрічковою матрицею, яку наведено на рисунку. Обґрунтувати переваги на недоліки представлення графа матрицею суміжності та стрічковою матрицею.

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



^

Варіант №2


Завдання 1. Намалювати граф за матрицею cуміжності, яку наведено в таблиці 1. Обґрунтувати переваги на недоліки представлення графа матрицею суміжності та стрічковою матрицею.
^

Таблиця 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. Знайти маршрути мінімальної довжини для кожної пари вершин. Визначити ребра графа, збільшення довжини яких не відобразиться на мінімальних маршрутах.
^

Таблиця 1. Відстані між вершинами графа





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
^


Варіант №3


Завдання 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
^


Варіант №4


Завдання 1. Намалювати граф за матрицею cуміжності, яку наведено в таблиці 1. Обґрунтувати переваги на недоліки представлення графа матрицею суміжності та стрічковою матрицею.
^

Таблиця 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. Знайти маршрути мінімальної довжини для кожної пари вершин. Визначити ребра графа, збільшення довжини яких не відобразиться на мінімальних маршрутах.
^

Таблиця 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 iconВаріант а варіант Б
З кожної пари професій виберіть одну, найбільш привабливу для вас І запишіть на бланку для відповідей: номер питання та варіант (А...
Варіант №1 iconЗавдання для самостійної роботи студентів І курсу фізико-математичного факультету спеціальностей «Математика та основи інформатики»
Варіант Вашої роботи визначається номером у списку групи (за журналом). Варіант 1 виконують студенти, номери яких 1, 11 та 21; варіант...
Варіант №1 iconЗавдання для самостійної роботи студентів І курсу фізико-математичного факультету спеціальностей «Математика та основи інформатики»
Варіант Вашої роботи визначається номером у списку групи (за журналом). Варіант 1 виконують студенти, номери яких 1, 11 та 21; варіант...
Варіант №1 iconЗавдання для самостійної роботи студентів ІІІ курсу фізико-математичного факультету спеціальностей «Математика та основи інформатики»
Варіант Вашої роботи визначається номером у списку групи (за журналом). Варіант 1 виконують студенти, номери яких 1 та 21; варіант...
Варіант №1 iconЗавдання для самостійної роботи студентів ІІІ курсу фізико-математичного факультету спеціальностей «Математика та основи інформатики»
Варіант Вашої роботи визначається номером у списку групи (за журналом). Варіант 1 виконують студенти, номери яких 1 та 16; варіант...
Варіант №1 iconІіі варіант ІV варіант

Варіант №1 iconІнформація про видання Назва видання issn (електронний варіант) (якщо є) issn ( друкований варіант) (якщо є) Відповідальний редактор
Надіслати три його номери (спочатку надсилається поточний номер видання, а потім два наступних (одразу після їх опублікування) та...
Варіант №1 iconЗавдання для самостійної роботи студентів
Варіант Вашої роботи визначається номером у списку групи (за журналом). Номер варіанта – це остача від ділення на 15 Вашого номеру...
Варіант №1 iconЗавдання для самостійної роботи студентів
Варіант Вашої роботи визначається номером у списку групи (за журналом). Номер варіанта – це остача від ділення на 15 Вашого номеру...
Варіант №1 iconРобочий зошит з дисципліни «кредитування І контроль»
Кредитування І контроль”. Кожен студент обирає свій варіант у відповідності до порядкового номера у журналі обліку занять академічної...
Варіант №1 iconВаріант 17

Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи