Читайте также:
|
Математичні моделі у вигляді графів широко використовуються при моделюванні різноманітних явищ, процесів і систем. Як результат, багато теоретичних і реальних прикладних задач можуть бути вирішені за допомогою тих чи інших процедур аналізу графових моделей. Серед безлічі цих процедур може бути виділений деякий певний набір типових алгоритмів обробки графів.
- граф (
)
для якого набір вершин 
, 
, задається множиною 
, а список дуг графа 
, 
визначається безліччю 
. У загальному випадку дуг графа можуть приписуватися деякі числові характеристики 
, (зважений граф).
Для опису графів відомі різні способи завдання. При малій кількості дуг у графі (тобто 
) доцільно використовувати для визначення графів списки, які перераховують наявні у графах дуги. Представлення досить щільних графів, для яких майже всі вершини з'єднані між собою дугами (тобто 
), може бути ефективно забезпечене за допомогою матриці інцидентності
Використання матриці інцидентності дозволяє використовувати також при реалізації обчислювальних процедур для графів матричні алгоритми обробки даних.
Далі в посібнику обговорюються паралельні способи вирішення двох типових задач на графах - знаходження мінімально охоплюють дерев і пошук найкоротших шляхів. Для представлення графів використовується спосіб завдання за допомогою матриць інцидентності.
Дата добавления: 2015-08-18; просмотров: 112 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Послідовний алгоритм. | | | Навести і описати паралельні методи розв'язання диференціальних рівнянь у частинних похідних. |