2.11.3 Задачи для самостоятельного решения

1. Для вершин v₁иv₆графаG(рисунок 14) привести примеры маршрута, цепи, простой цепи, цикла, простого цикла.

v₄

v₃v₅

v₂

v₁v₈

v₉v₁₀

v₇

Рисунок 14 – К задачам 1, 3 (2.11.3)

2. Найти минимальный путь в нагруженном орграфе из вершины v₁вv₇. Орграф задан матрицей весов:

а) ; б);

в) .

2. Определить путь из вершины v₁вv₇ минимальной длины в каждом нагруженном орграфе (см. рисунок 14) среди путей изv₁вv_7,содержащих не болееkдуг, где: а)k= 2; б)k= 3; в)k= 4.

3. Найти минимальный путь в невзвешенном орграфе из вершины v₁вv₇. Орграф задан матрицей смежности:

а); б);

в) .

2. Определить минимальный путь из вершины v₁в вершинуv₁в орграфах, диаграммы которых приведены на рисунке 15а, б. Пусть должен содержать не более 5 дуг.

   а)	б)
   Рисунок 15 – К задаче 5 (2.11.3)

3. Определить, имеются ли в нагруженном орграфе с заданной матрицей весов Спростые контуры отрицательной длины? Найти пути минимальной длины изv₁во все остальные вершины среди путей, содержащих не более шести дуг. Рассмотреть случай:

7. Проверить, существуют ли в мультиграфах, заданных матрицами смежности, эйлеровы цепи и циклы? Если да, то найти их. Рассмотреть случаи:

а) ; б).

8. Найти максимальные потоки в сетях G₁–G₄:

	G1	G2			G3	G4
х	с(х)	с(х)		х	с(х)	с(х)
v1v2	12	10		v1v2	10	11
v1v3	6	4		v1v3	10	7
v1v4	4	3		v1v4	6	8
v2v3	6	8		v2v3	3	6
v2v4	4	7		v2v4	5	4
v2v6	3	6		v2v5	2	3
v3v5	4	2		v2v7	4	4
v3v6	8	9		v4v6	5	8
v4v5	3	10		v5v6	3	4
v5v7	15	12		v5v7	6	10
v6v5	1	6		v6v8	18	5
v6v7	7	5		v7 v8	7	9

3 Технические и инструментальные средства

В целях освобождения от рутинных расчетов, повышения уровня наглядности результатов расчетов, осуществления самоконтроля в процессе самостоятельной работы при подготовке к практическим занятиям, к контрольной работе и к экзамену студентам предлагается использовать следующее программное обеспечение:

1. MapleV;

2. MATLAB;

3. Мathematica5;

4. Mathcad12 .

Предлагаемые пакеты пригодны для работы на любом IBM-совместимом компьютере.