На головну

алгоритм Краскала

  1.  II. Вивчити і представити класифікацію вищеперелічених товарних груп у вигляді схем, таблиць, алгоритмів, малюнків.
  2.  V. Алгоритмізація та програмування. Мови програмування високого рівня
  3.  V. Алгоритмізація та програмування. Мови програмування високого рівня
  4.  алгоритм
  5.  алгоритм
  6.  алгоритм
  7.  алгоритм

Нехай дано повний граф. Ребрах приписані штрафи. На основі цього графа будують дерево, що має мінімальний сумарний штраф.

Для цього на кожному кроці вибирають ребро, що має мінімальний штраф і не утворює цикл з вже обраними ребрами.

.

Приклад.


2 3 5 5

6

4 4 8 6

6

Жирними лініями виділено мінімальне дерево

теорема Келідля розфарбованих дерев.

Для n вершин існує nn-2 різних помічених дерев.

Наприклад, існує 16 різних дерев з чотирма вершинами.

 1 2 3 4

 4 3 2 1

4 вершини ? 44 - 2 = 16 різних помічених дерев

1 2 3


планарні графи

Граф - плоский, Якщо він зображений на площині без перетину ребер.

Граф - планарний, Якщо він може бути зображений на площині без перетину ребер.

 Будь-плоский граф може бути перетворений в граф з прямими ребрами.

               
       


 ? ?

неплоский, але плоский плоский з

планарний прямими ребрами

Граф, де всі вершини стикаються із зовнішнім гранню - внешнепланарний.

Два "чудових" непланарних графа:


К5 К3,3

Наведемо без доведення дві теореми:

Будь-граф, що містить в якості подграфа До5 або К3,3 - Непланарен.

два графа гомеоморфні якщо вони тотожні з точністю до вершин зі ступенем r = 2.

Будь-граф, що містить в якості подграфа граф гомеоморфними До5 або К3,3 або - непланарен.

Теорема (Ейлера для планарних графів):

У будь-якому планарном графі

В + Г = Р + 2.

де: В - число вершин

Г - число граней

Р - число ребер

Доведення:

 1 + 1 = 0 + 2

 2 + 1 = 1 + 2

 3 + 2 = 3 + 2


4 + 2 = 4 + 2

Нехай є граф з n вершинами, для якого це співвідношення вірно.

Додавання ребра призводить до збільшення на едітніцу або числа граней, або вершин.

 




 Категоричні висловлювання. |  Модальні логіки. |  теорія Автоматів |  приклади автоматів |  виходів |  мінімізація автоматів |  Перехід від автомата Мура до автомату Мілі і навпаки |  теорія графів |  теорема Ейлера |  Повні графи і дерева |

© um.co.ua - учбові матеріали та реферати