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

Алгоритм Крускала, так само, як і алгоритм Прима призначений для пошуку дерева мінімальної вартості неорієнтованого графа. Основна відмінність між даними алгоритмами полягає в тому, що пошук дерева мінімальної довжини за алгоритмом Крускала починається з n дерев, кожне з яких складається з однієї вершин. І на кожному кроці виконуємо операцію об'єднання двох дерев, використовуючи для цього ребро найкоротшої довжини. Процес продовжується поки не отримаємо єдине дерево, яке охоплює всі n вершин вхідного графа, і не містить циклів.

Розглянемо деякий неорієнтований граф, і спробуємо побудувати для нього дерево мінімальної вартості за вище розглянутим алгоритмом.

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

Крок 1: вибираємо ребро найменшої вартості: 1−3=1. В результаті отримаємо одне дерево, яке складається з двох вершин і одного ребра (на малюнку позначено зеленим кольором) та 4 дерева, які містять по одній вершині.

Читати повністю

Графічний метод. Приклад розв'язання задачі лінійного програмування графічним методом

Для виготовлення товару A і B підприємство використовує три види сировини I, II, III. Норми витрат сировини на виробництво одного товару кожного виду, ціна одиниці товару A, B а також загальна кількість сировини наведені в наступній таблиці:

510

Потрібно організувати випуск даної продукції таким чином, щоб прибуток від її реалізації був максимальним.

Позначимо через 28 — кількість товару виду А; 33 — кількість товару виду В. Тоді математична модель даної задачі полягає у визначенні максимального значення функції мети:

215

при обмеженнях:

68

46

Читати повністю

Графічний метод розв'язання задачі лінійного програмування

Графічний метод доцільно застосовувати для розв'язування задач лінійного програмування із двома змінними. Обмежене використання даного методу зумовлене складністю побудови багатокутника розв'язків для задач з трьома змінними, а графічне зображення де кількість змінних перевищує число три, взагалі неможливе.

Розглянемо задачу лінійного програмування:

117при обмеженнях:

214

37

Читати повністю

Знаходження дерева мінімальної вартості за алгоритмом Крускала на Delphi(1)

Основним завданням даної програми є  побудови остового дерева мінімальної віртості використовуючи алгоритм Крускала. Розглянемо її роботу на конкретному прикладі. Отже, нехай дано неорієнтований гряа виду:

17

для якого будемо шукати дерево мінімальної вартості.

Читати повністю

Знаходження дерева мінімальної вартості за алгоритмом Прима на Delphi(1)

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

14

Запустимо проект на виконання, в результаті на екрані монітора появиться форма наступного виду:

Читати повністю