Примеры решения задач

  1. Ориентированный граф G с множеством вершин V = {1, 2, 3, 4, 5, 6, 7} задан списком дуг
    Е = {(1,4) (1, 6) (2, 1) (2, 2) (2, 6) (2, 6) (3, 2) (3,4) (3, 6) (4, 6) (5, 2) (5, 4) (5, 4) (5, 5) (6, 2) (6, 5) (7, 1) (7, 6)}.
  2. Неориентированный граф G с множеством вершин V = {1, 2, 3, 4, 5, 6, 7} задан списком ребер Е= {(1, 2), (1, 4), (1, 6), (1, 7), (2, 3), (2, 5), (2, 6), (3,4), (3,6), (4, 5), (4, 6), (5, 6), (5, 7)}.
    No
    п/п
    Алгоритм Конкретное соответствие задания заданному алгоритму
    1 Построить реализацию графа G Процесс построения реализации графа описан в тренинге умения 1
    2 Найти цикломатическое число графа G Цикломатическое число, равное размерности базиса циклов графа, определяется формулой ν=p-b+k, где р - число ребер, b - число вершин, k - число компонент связности графа p=13, b=7, k=1 (нетрудно убедиться, что граф G - связный). Следовательно ν=13-7+1.
    3 Выбрать остов графа G Поскольку число вершин графа G равно 7, в любом его остове должно быть 6 ребер. При заданном упорядочении вершин 1-7, начиная с вершины 1, последовательно добавляем ребра, присоединяющие к строящемуся дереву новую вершину: (1,2),(1,4),(1,6),(1,7),(2,3),(2,5)
    4 Построить базис циклов графа G

    1. Составим список хорд относительно построенного остова (все остальные ребра графа): (2,6),(3,4),(3,6),(4,5),(4,6),(5,6),(5,7).

    Число хорд должно быть равно цикломатическому числу графа, т.е. 7.

    2. Поочередно присоединяя к остову по одной хорде, выделяем элементарный цикл, состоящий из этой хорды и части ребер остова - единственной цепи, связывающей в остове концы хорды.
    ХордаДобавляемая цель
    *(2,6)
     (3,4)
     (3,6)
    *(4,5)
     (4,6)
    *(5,6)
     (5,7)
    (6,1),(1,2)
    (4,1),(1,2),(2,3)
    (6,1),(2,1),(2,3)
    (5,2),(2,1),(1,4)
    (6,1),(1,4)
    (6,1),(1,2),(2,5)
    (7,1),(1,2),(2,5)

    3. Выразим в построенном базисе элементарный цикл С=(6,2,1,4,5,6). Он получается сложением по модулю 2 тех базисных циклов, которые содержат хорды, принадлежащие С (Они отмечены звездочкой в предыдущей таблице: (6,2),(4,5),(5,6))

    Проверьте, что ребра цикла С содержатся в совокупности базисных циклов нечетное число раз (в частности, все хорды - ровно по одному разу), а ребра, не принадлежащие С (например, ребро (5,2)), - четное.



  3. На рисунке 1 изображены графы G1 - G12 с четырьмя вершинами в каждом. Сравнить графы.


    Рисунок 1



  4. Задать граф G1, представленный на рисунке 2, через множества вершин V1 и ребер E1.


    Рисунок 2
  5. Задать матрицами инцидентности и смежности, а также списком ребер графы G1, G3 (рис. 3)

    Рисунок 3