Анализ графов на ЭВМ. Методические указания. Макарычев П.П - 25 стр.

      Произвольный ориентированный маршрут (vi, vj), не являющийся
простой цепью, превращается в простую цепь после устранения ''лишних
звеньев''. Поэтому верны утверждения:
 1. При i, не равном j, всякий маршрут (vi, vj) содержит простую цепь.
 2. Всякий цикл содержит простой цикл.
 3. Если C, D - два несовпадающих простых цикла, имеющих общее ребро
ui, то граф (C ∪ D) также содержит простой цикл.
                               Лабораторное задание
 1. Выполните генерацию матрицы смежности M(G) неориентированного
помеченного графа G порядка             n ≥ 8 . Метки графа выберите из
подмножества натуральных чисел {1,2,…,n}. Отождествляя каждую
вершину графа с одним из элементов на рис.6, постройте функциональную
схему электронного узла. При этом входы элементов с номерами 1, 2
являются входами, а выходы элементов с номерами n, n - 1 — выходами
всего учла.
 2. Вычислите остов минимального веса и базисные циклы Li, i = 1, 2,..., m
в графе G. При отсутствии базисных циклов в графе по согласованию с
преподавателем осуществите добавление ребра (ребер)
 3. Определите через базисные циклы все остальные циклы Lj, j = m+1,
m+2,… в графе G. В соответствии с найденными циклами графа укажите
на функциональной схеме узла все замкнутые цепи (контуры).
 4. Осуществите генерацию матрицы смежности M(H) помеченного
орграфа H порядка n ≥ 8 . Определите все вершины, достижимые из
вершины       v1.   Выберите     достижимую   вершину   vj,   j   =   2,3,…,n,
определяющую самый длинный маршрут. Определите, является ли самый
длинный маршрут простой ориентированной цепью. Если маршрут не
является простой ориентированной цепью, то удалите ''лишние звенья''.




                                        25