Контрольная работа по предмету Высшая математика на тему: Задачи по теории графов. Вариант 24

В а р и а н т 24
1. Пусть орграф D задан матрицей смежности. Найти количество компонент сильной связности орграфа и определить матрицы смежности этих компонент. Постройте изображения орграфа и его компонент сильной связности. V1 V2 V3 V4 V5 V6 V1 1 0 0 1 0 0 V2 0 1 0 1 0 1 A(D)= V3 0 0 0 0 0 0 V4 1 0 1 0 0 1 V5 1 0 1 0 0 0 V6 0 1 0 0 0 1
2. Определить минимальный путь из v1 в v7 в нагруженном орграфе с заданной матрицей длин дуг. V1 V2 V3 V4 V5 V6 V7 V1        V2        C(D)= V3        V4        V5        V6        V7              
3. Определить минимальное остовное дерево нагруженного графа. V1 V2 V3 V4 V5 V6 V7 V1        V2        C(G)= V3        V4        V5        V6        V7       
4. Найти максимальный поток и минимальный разрез в транспортной сети. V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 V1           V2           V3           V4     5      C(D)= V5           V6           V7           V8           V9           V10          
5. Даны орграфы D1, D2. Найдите D1D2, D1D2 . Для орграфа D1D2 запишите все формы представления, определите полустепени исхода и захода вершин, постройте частичный граф, подграф, дополнительный орграф.
D1: 1 2 D2: 1
4 3 3 2
 Нарисуйте два орграфа D1, D2 (2-3 вершины). Найдите D1  D2, D1+D2. Полученный орграф постройте.