Введение в теорию графов

Методы разбиения графа на максимальные сильно связные подграфы

Разбить на страницы
Показывать лекцию целиком

Метод Мальгранжа

Пусть дан граф G=(X, A), где X={ хi }, i =1, 2, ... , n – множество вершин, а A={ ai }, i =1, 2, ..., m – где множество дуг, описанных матрицей смежности. Алгоритм разбиения заключается в следующем [4].

  • Для произвольной вершины $$х_{i} \in X$$ находим прямое T+(хi) и обратное T-(хi) транзитивные замыкания.
  • Находим $$T^{+}(х_{i}) \cap T^{-}(х_{i})$$. Множество вершин этого пересечения составляют вершины максимального сильно связного подграфа G1 = (Х1, A1).
  • Из исходного графа вычитаем подграф G1:G '=G\G1, Х'=X\Х1 .
  • Граф G ' принимаем за исходный граф и пока $$X ' \ne \varnothing$$ пункты 1, 2, 3 алгоритма повторяются.
    •

    Рассмотрим этот алгоритм более подробно на примере разбиения графа, представленного на ,a, матрица смежности которого показана на ,б.

    (рис 7.1) а – граф; б – матрица смежности и транзитивные замыкания для вершины х1

    РАЗБИЕНИЕ – 1 .

    X1 X7 X11
    X1 1
    A7= X7 1
    X111 1

  • Начальной вершиной первого разбиения выберем х1 . Построим прямое и обратное транзитивные замыкания. T+(х1) – столбец, показанный справа от матрицы А, а T-(х1) – строка, находящаяся ниже матрицы смежности.

    T+(х1) = {х1, х4, х5, х6, х7, х8, х11 },

    T-(х1) = {х1, х2, х3, х7, х9, х10, х11}.

  • Находим $$T^{+}(х_{1}) \cap T^{-}(х_{1}) = \{ х_{1}, х_{7}, х_{11}\}$$. Эти вершины и составляют первый выделенный, максимальный сильно связный подграф G1 = (Х1, A1), где Х1 = {х1, х7, х11}, а матрица смежности A1 подграфа G1 показана на .

  • Из исходного графа G вычитаем подграф G1 G ' = G \G1 ;

    G ' = (X ', A'), X ' = { х2, х3, х4, х5, х6, х8, х9, х10 }.

  • Так как X ' не пустое множество, то G' принимаем за G и переходим ко второму разбиению.
    •

    РАЗБИЕНИЕ – 2

    X2 X3 X4 X5 X6 X8 X9 X10  T+(x2)
    X21 1 0
    X3 1 1 1 1
    X4 1 1
    X5 1
    A= X6 1 1
    X8 1
    X9 1
    X10 1 1 1
     
    T-(x2)0
  • Выбираем любую вершину, принадлежащую X, например, х2 , и находим T+(х2) и T-(х2). Это показано в таблице 7.2. T+(х2) = { х2, х8 } ; T-(х2) = { х2 }.
  • $$T^{+}(х_{2}) \cap T^{-}(х_{2}) = \{ х_{2} \}$$. Следовательно, второй выделенный подграф G2 состоит из одной вершины х2 .
  • G ' = G \G2; G ' = (X ', A'); X ' = { х3, х4, х5, х6, х8, х9, х10 }.
  • Так как X ' не пустое множество, то G ' принимаем за G и процесс разбиения продолжается.
    •

    РАЗБИЕНИЕ – 3

    X3 X4 X5 X6 X8 X9 X10  T+(x3)
    X31 1 1 1 0
    X4 1 1 1
    X5 1 2
    A= X6 1 1
    X8
    X8
    X91 1
    X10 1 1 1 1
     
    T-(x3)0 1 2
  • Выберем, например, вершину х3 () T+(х3) = { х3, х4, х5, х9, х10}, T-(х3) = { х3, х9, х10 }.
  • $$T^{+}(х_{3}) \cap T^{-}(х_{3}) = \{ х_{3}, х_{9}, х_{10} \}$$. Следовательно, третий подграф G3 состоит из вершин х3 , х9 , х 10 , матрица смежности которого показана на .
  • G ' = G \G3; G ' = (X ', A'); X ' = { х4, х5, х6, х8 }.
  • $$X ' \ne \varnothing ,$$ следовательно, процесс разбиения продолжаем: G' -> G; X ' -> X.
    •
    X3 X9 X10
    X31 1 1
    A= X91
    X10 1

    РАЗБИЕНИЕ – 4

    X4 X5 X6 X8  T+(x4)
    X41 1 0
    X51 1
    A= X6 1 1
    X8
     
    T-(x4)0 1
  • Выберем $$х_{4} \in X$$ ( ) T+(х4) = { х4, х5 }; T-(х4) = { х4, х5 ).
  • $$T^{+}(х_{4}) \cap T^{-}(х_{4}) = \{ х_{4}, х_{5} \} , G_{4} = (Х_{4}, A_{4}); Х_{4} = \{ х_{4}, х_{5} \}$$, матрица смежности A4 показана на .
  • G ' = G \G4; G ' = (X ', A'); X ' = { х6, х8 }.
  • $$X ' \ne \varnothing$$, следовательно, переходим к пятому разбиению.
    •
    X4 X5
    A4= X41 1
    X51

    РАЗБИЕНИЕ – 5

  • Выберем х6 . T+(х6) = { х6, х8 }; T-(х6) = { х6 }.
  • $$T^{+}(х_{6}) \cap T^{-}(х_{6}) = \{ х_{6} \} ; G_{5} = (Х_{5}, A_{5} ); Х_{5} = \{ х_{6} \}$$.
  • G ' = G \G5; X ' = { х8 }.
  • $$X ' \ne \varnothing$$, но состоит из одной вершины, поэтому очевидно, что шестой подграф содержит вершину х8 . На этом процесс разбиения завершается.
    •

    Итак, результат разбиения:

    G1 =( Х1, A1 ), Х1 = { х1, х7, х11 },

    G2 = ( Х2, A2 ), Х2 = { х2 },

    G3 = ( Х3, A3 ), Х3 = { х3, х9, х10 },

    G4 = ( Х4, A4 ), Х4 = { х4, х5 },

    G5 = ( Х5, A5 ), Х5 = { х6 },

    G6 = ( Х6, A6 ), Х6 = { х8 }

    показан на ,а, где каждый подграф G1, ... ,G6 представляет собой сильную компоненту графа. Граф ,б).

    (рис 7.2) Результат разбиения: а – гиперграф; б – конденсация

    Матричный метод разбиения

    Метод разбиения графа на максимальные сильно связные подграфы по матрицам достижимости R и контрдостижимости Q состоит в следующем.

  • По матрице смежности строится матрица достижимости R. Используя операцию транспонирования, находим матрицу контрдостижимости Q.
  • Находится матрица C = { сij }, i,j = 1, 2, 3, ..., n, где n – число вершин исходного графа, а каждый элемент $$C_{ij} = r_{ij}\wedge q_{ij}$$, т. е. матрица C получается поэлементным логическим умножением матриц R и $$Q: С = R \wedge Q$$.
  • Элементы, имеющие одинаковые строки и столбцы в матрице С группируем перестановкой строк и столбцов, получаем блочно диагональную матрицу Св , где каждая группа элементов и есть максимальный сильно связный подграф.
    •

    Рассмотрим пример разбиения для графа, представленного на ,а. Как следует из определения матрицы и . В результате логического умножения получили матрицу ), в которой находим одинаковые строки. Например, для вершины ) полученные подграфы совпадают с результатом разбиения по методу Мальгранжа .

    X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
    X1 1 1 1 1 1 1 1
    X21 1 1 1 1 1 1 1
    X31 1 1 1 1 1 1 1 1 1
    X4 1 1
    R= X5 1 1
    X6 1 1
    X71 1 1 1 1 1 1
    X8 1
    X91 1 1 1 1 1 1 1 1 1
    X101 1 1 1 1 1 1 1 1 1
    X111 1 1 1 1 1 1
    X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
    X11 1 1 1 1 1 1
    X2 1
    X3 1 1 1
    X41 1 1 1 1 1 1 1 1
    Q= X51 1 1 1 1 1 1 1 1
    X61 1 1 1 1 1 1 1
    X71 1 1 1 1 1 1
    X81 1 1 1 1 1 1 1 1
    X9 1 1 1
    X10 1 1 1
    X111 1 1 1 1 1 1
    Пример матричного метода разбиения
    X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
    X11 1 1
    X2 1
    X3 1 1 1
    X4 1 1
    C= X5 1 1
    X6 1
    X71 1 1
    X8 1
    X9 1 1 1
    X10 1 1 1
    X111 1 1
    X1 X7 X11 X2 X3 X9 X10 X4 X5 X6 X8
    X11 1 1
    X71 1 1
    X111 1 1
    X2 1
    CВ= X3 1 1 1
    X9 1 1 1
    X10 1 1 1
    X4 1 1
    X5 1 1
    X6 1
    X8 1
    Страницы:

    Метод Мальгранжа

    Пусть дан граф G=(X, A), где X={ хi }, i =1, 2, ... , n – множество вершин, а A={ ai }, i =1, 2, ..., m – где множество дуг, описанных матрицей смежности. Алгоритм разбиения заключается в следующем [4].

  • Для произвольной вершины $$х_{i} \in X$$ находим прямое T+(хi) и обратное T-(хi) транзитивные замыкания.
  • Находим $$T^{+}(х_{i}) \cap T^{-}(х_{i})$$. Множество вершин этого пересечения составляют вершины максимального сильно связного подграфа G1 = (Х1, A1).
  • Из исходного графа вычитаем подграф G1:G '=G\G1, Х'=X\Х1 .
  • Граф G ' принимаем за исходный граф и пока $$X ' \ne \varnothing$$ пункты 1, 2, 3 алгоритма повторяются.
    •

    Рассмотрим этот алгоритм более подробно на примере разбиения графа, представленного на ,a, матрица смежности которого показана на ,б.

    (рис 7.1) а – граф; б – матрица смежности и транзитивные замыкания для вершины х1

    РАЗБИЕНИЕ – 1 .

    X1 X7 X11
    X1 1
    A7= X7 1
    X111 1

  • Начальной вершиной первого разбиения выберем х1 . Построим прямое и обратное транзитивные замыкания. T+(х1) – столбец, показанный справа от матрицы А, а T-(х1) – строка, находящаяся ниже матрицы смежности.

    T+(х1) = {х1, х4, х5, х6, х7, х8, х11 },

    T-(х1) = {х1, х2, х3, х7, х9, х10, х11}.

  • Находим $$T^{+}(х_{1}) \cap T^{-}(х_{1}) = \{ х_{1}, х_{7}, х_{11}\}$$. Эти вершины и составляют первый выделенный, максимальный сильно связный подграф G1 = (Х1, A1), где Х1 = {х1, х7, х11}, а матрица смежности A1 подграфа G1 показана на .

  • Из исходного графа G вычитаем подграф G1 G ' = G \G1 ;

    G ' = (X ', A'), X ' = { х2, х3, х4, х5, х6, х8, х9, х10 }.

  • Так как X ' не пустое множество, то G' принимаем за G и переходим ко второму разбиению.
    •

    РАЗБИЕНИЕ – 2

    X2 X3 X4 X5 X6 X8 X9 X10  T+(x2)
    X21 1 0
    X3 1 1 1 1
    X4 1 1
    X5 1
    A= X6 1 1
    X8 1
    X9 1
    X10 1 1 1
     
    T-(x2)0
  • Выбираем любую вершину, принадлежащую X, например, х2 , и находим T+(х2) и T-(х2). Это показано в таблице 7.2. T+(х2) = { х2, х8 } ; T-(х2) = { х2 }.
  • $$T^{+}(х_{2}) \cap T^{-}(х_{2}) = \{ х_{2} \}$$. Следовательно, второй выделенный подграф G2 состоит из одной вершины х2 .
  • G ' = G \G2; G ' = (X ', A'); X ' = { х3, х4, х5, х6, х8, х9, х10 }.
  • Так как X ' не пустое множество, то G ' принимаем за G и процесс разбиения продолжается.
    •

    РАЗБИЕНИЕ – 3

    X3 X4 X5 X6 X8 X9 X10  T+(x3)
    X31 1 1 1 0
    X4 1 1 1
    X5 1 2
    A= X6 1 1
    X8
    X8
    X91 1
    X10 1 1 1 1
     
    T-(x3)0 1 2
  • Выберем, например, вершину х3 () T+(х3) = { х3, х4, х5, х9, х10}, T-(х3) = { х3, х9, х10 }.
  • $$T^{+}(х_{3}) \cap T^{-}(х_{3}) = \{ х_{3}, х_{9}, х_{10} \}$$. Следовательно, третий подграф G3 состоит из вершин х3 , х9 , х 10 , матрица смежности которого показана на .
  • G ' = G \G3; G ' = (X ', A'); X ' = { х4, х5, х6, х8 }.
  • $$X ' \ne \varnothing ,$$ следовательно, процесс разбиения продолжаем: G' -> G; X ' -> X.
    •
    X3 X9 X10
    X31 1 1
    A= X91
    X10 1

    РАЗБИЕНИЕ – 4

    X4 X5 X6 X8  T+(x4)
    X41 1 0
    X51 1
    A= X6 1 1
    X8
     
    T-(x4)0 1
  • Выберем $$х_{4} \in X$$ ( ) T+(х4) = { х4, х5 }; T-(х4) = { х4, х5 ).
  • $$T^{+}(х_{4}) \cap T^{-}(х_{4}) = \{ х_{4}, х_{5} \} , G_{4} = (Х_{4}, A_{4}); Х_{4} = \{ х_{4}, х_{5} \}$$, матрица смежности A4 показана на .
  • G ' = G \G4; G ' = (X ', A'); X ' = { х6, х8 }.
  • $$X ' \ne \varnothing$$, следовательно, переходим к пятому разбиению.
    •
    X4 X5
    A4= X41 1
    X51

    РАЗБИЕНИЕ – 5

  • Выберем х6 . T+(х6) = { х6, х8 }; T-(х6) = { х6 }.
  • $$T^{+}(х_{6}) \cap T^{-}(х_{6}) = \{ х_{6} \} ; G_{5} = (Х_{5}, A_{5} ); Х_{5} = \{ х_{6} \}$$.
  • G ' = G \G5; X ' = { х8 }.
  • $$X ' \ne \varnothing$$, но состоит из одной вершины, поэтому очевидно, что шестой подграф содержит вершину х8 . На этом процесс разбиения завершается.
    •

    Итак, результат разбиения:

    G1 =( Х1, A1 ), Х1 = { х1, х7, х11 },

    G2 = ( Х2, A2 ), Х2 = { х2 },

    G3 = ( Х3, A3 ), Х3 = { х3, х9, х10 },

    G4 = ( Х4, A4 ), Х4 = { х4, х5 },

    G5 = ( Х5, A5 ), Х5 = { х6 },

    G6 = ( Х6, A6 ), Х6 = { х8 }

    показан на ,а, где каждый подграф G1, ... ,G6 представляет собой сильную компоненту графа. Граф ,б).

    (рис 7.2) Результат разбиения: а – гиперграф; б – конденсация

    Матричный метод разбиения

    Метод разбиения графа на максимальные сильно связные подграфы по матрицам достижимости R и контрдостижимости Q состоит в следующем.

  • По матрице смежности строится матрица достижимости R. Используя операцию транспонирования, находим матрицу контрдостижимости Q.
  • Находится матрица C = { сij }, i,j = 1, 2, 3, ..., n, где n – число вершин исходного графа, а каждый элемент $$C_{ij} = r_{ij}\wedge q_{ij}$$, т. е. матрица C получается поэлементным логическим умножением матриц R и $$Q: С = R \wedge Q$$.
  • Элементы, имеющие одинаковые строки и столбцы в матрице С группируем перестановкой строк и столбцов, получаем блочно диагональную матрицу Св , где каждая группа элементов и есть максимальный сильно связный подграф.
    •

    Рассмотрим пример разбиения для графа, представленного на ,а. Как следует из определения матрицы и . В результате логического умножения получили матрицу ), в которой находим одинаковые строки. Например, для вершины ) полученные подграфы совпадают с результатом разбиения по методу Мальгранжа .

    X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
    X1 1 1 1 1 1 1 1
    X21 1 1 1 1 1 1 1
    X31 1 1 1 1 1 1 1 1 1
    X4 1 1
    R= X5 1 1
    X6 1 1
    X71 1 1 1 1 1 1
    X8 1
    X91 1 1 1 1 1 1 1 1 1
    X101 1 1 1 1 1 1 1 1 1
    X111 1 1 1 1 1 1
    X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
    X11 1 1 1 1 1 1
    X2 1
    X3 1 1 1
    X41 1 1 1 1 1 1 1 1
    Q= X51 1 1 1 1 1 1 1 1
    X61 1 1 1 1 1 1 1
    X71 1 1 1 1 1 1
    X81 1 1 1 1 1 1 1 1
    X9 1 1 1
    X10 1 1 1
    X111 1 1 1 1 1 1
    Пример матричного метода разбиения
    X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
    X11 1 1
    X2 1
    X3 1 1 1
    X4 1 1
    C= X5 1 1
    X6 1
    X71 1 1
    X8 1
    X9 1 1 1
    X10 1 1 1
    X111 1 1
    X1 X7 X11 X2 X3 X9 X10 X4 X5 X6 X8
    X11 1 1
    X71 1 1
    X111 1 1
    X2 1
    CВ= X3 1 1 1
    X9 1 1 1
    X10 1 1 1
    X4 1 1
    X5 1 1
    X6 1
    X8 1
    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^