І1

1.  Розмітити непомічений граф.

2. Побудувати для отриманого поміченого графа матриці: степенів, суміжності, Кірхгофа. За допомогою матриці Кірхгофа визначити число остовних дерев.

3. Знайти остов мінімальної ваги і саму вагу остову, використовуючи алгоритм:

    а) Краскала;

    б) Пріма.

Проілюструвати етапи виконання алгоритмів відповідними рисунками.


Номери варіантів:

     1, 11, 21 стор. 75, рис. 4.1 а

     2, 12, 22  стор. 75, рис. 4.1 б

     3, 13, 23  стор. 75, рис. 4.1 в

     4, 14, 24  стор. 75, рис. 4.1 г

     5, 15, 25 стор. 75, рис. 4.1 д

     6, 16, 26 стор. 75, рис. 4.1 е

     7, 17, 27 стор. 75, рис. 4.1 ж

     8, 18, 28 стор. 75, рис. 4.1 з

     9, 19, 29 стор. 75, рис. 4.1 и

     10, 20, 30 стор. 75, рис. 4.1 к

Розв'язання необхідно прикріпити у цьому завданні і форматі *.pdf.