Компьютерная математика: Часть 2. Теория графов. Волченская Т.В - 41 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

подграф, который не содержится ни в каком другом сильном подграфе. Такой
подграф называется
сильной компонентой графа. Аналогично,
односторонняя компонента представляет собой односторонний максимальный
подграф, а
слабая компонента - максимальный слабый подграф.
Например, в графе, приведенном на рис. 20,б, подграф, состоящий из
вершин {х
1
,х
4
,х
5
,х
6
}, является сильной компонентой графа. С другой стороны
подграфы, включающие вершины {х
1
, х
6
} и {х
1
, х
5
, х
6
}, не являются сильными
компонентами , (хотя и являются сильными подграфами), поскольку они
содержатся в графе, состоящем из вершин {х
1
, х
4
, х
5
, х
6
} и, следовательно, не
максимальные. В графе, показанном на рис. 20,в, подграф не содержит вершины
{х
1
, х
4
, х
5
} является односторонней компонентой.
В графе, приведенном на рис. 20,г, оба подграфа, включающие вершины {х
1
, х
5
,
х
6
} и {х
2
, х
3
, х
4
} являются слабыми компонентами, и у этого графа только две
компоненты.
Из определений сразу же следует, что односторонние компоненты графа
могут иметь общие вершины. Сильная компонента должна содержаться по
крайней мере в одной односторонней компоненте, а односторонняя компонента
содержится в некоторой слабой компоненте данного графа.
. Упражнения к п. 3.3 .
1. Найти максимальный сильно
связанный подграф
включающий вершину Е
для графа на рисунке.
Решение:
A B C D E F G K T
+
(E)
A 1 1 0 0 1 0 0 0
B 0 0 1 0 1 1 0 0
C 0 0 1 0 1 0 0 0
D 0 0 0 0 0 0 0 1
E 0 0 0 0 0 1 0 0
F 1 0 0 0 0 0 1 0
G 0 0 0 0 0 0 0 1
K 0 0 0 1 0 0 0 0
T
-
(E)
T
+
(E)={ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .},
T
-(
E)={ . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . },
T
+
(E) ∩T
-
(E)={ . . . . . . . .. . . . . . . . . . . . . . . . . . . },
G
МСС
={. . . . . . . .. . . . . . . . . . . . . . . . . . . }.
2. Какие из приведенных ниже графов являются: сильно связными, односторонне
связными, слабо связными и несвязными.
Х
1
Х
1
X
6
X
2
X
3
x
1
x
2
x
3 
подграф, который не содержится ни в каком другом сильном подграфе. Такой
подграф        называется    сильной     компонентой    графа.    Аналогично,
односторонняя компонента представляет собой односторонний максимальный
подграф, а слабая компонента - максимальный слабый подграф.
          Например, в графе, приведенном на рис. 20,б, подграф, состоящий из
вершин {х1,х4,х5,х6}, является сильной компонентой графа. С другой стороны
подграфы, включающие вершины {х1, х6} и {х1, х5, х6}, не являются сильными
компонентами , (хотя и являются сильными подграфами), поскольку они
содержатся в графе, состоящем из вершин {х1, х4, х5, х6} и, следовательно, не
максимальные. В графе, показанном на рис. 20,в, подграф не содержит вершины
{х1, х4, х5} является односторонней компонентой.
В графе, приведенном на рис. 20,г, оба подграфа, включающие вершины {х1, х5,
х6} и {х2, х3, х4} являются слабыми компонентами, и у этого графа только две
компоненты.
    Из определений сразу же следует, что односторонние компоненты графа
могут иметь общие вершины. Сильная компонента должна содержаться по
крайней мере в одной односторонней компоненте, а односторонняя компонента
содержится в некоторой слабой компоненте данного графа.

.     Упражнения к п. 3.3                                                      .
1.Найти максимальный сильно
связанный подграф
включающий     вершину Е
для графа на рисунке.
                 Решение:

           A      B    C    D     E        F   G    K        T+(E)
     A     1      1    0    0     1        0   0    0
     B     0      0    1    0     1        1   0    0
     C     0      0    1    0     1        0   0    0
     D     0      0    0    0     0        0   0    1
     E     0      0    0    0     0        1   0    0
     F     1      0    0    0     0        0   1    0
     G     0      0    0    0     0        0   0    1
     K     0      0    0    1     0        0   0    0

      T-
     (E)

       T+(E)={ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .},
       T-(E)={ . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . },
       T+(E) ∩T-(E)={ . . . . . . . .. . . . . . . . . . . . . . . . . . . },
       GМСС={. . . . . . . .. . . . . . . . . . . . . . . . . . . }.
2. Какие из приведенных ниже графов являются: сильно связными, односторонне
связными, слабо связными и несвязными.
                                                                          x2
            Х1                        X2



     X6                                            x1


                                      X3                                           x3

Страницы