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

UptoLike

ВУЗ: 

ПГУ | Пенза

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

Рубрика: 

соединяющий эти вершины. Это определение означает также, что любые две
вершины силносвязного графа взаимодостижимы. Пример данного графа показан
на рис. 20а.
Орграф называется
односторонне связным или односторонним,
если для любых двух различных его вершин x
i
и x
j
существует по крайней мере
один путь из x
i
в x
j
или из x
j
в x
i
или оба пути существуют одновременно. Граф на
рис.20,б не является сильным, так как в нем нет пути из x
1
в x
3
, но является
односторонне связным.
Орграф называется
слабо связным или слабым, если для любых двух
различных вершин графа существует по крайней мере один маршрут,
соединяющий их. Граф, изображенный на рис.20,в не является ни сильным, ни
односторонним, поскольку в нем не существует путей от x
2
к x
5
и от x
5
к x
2
. Он
слабо связный.
Орграф называется
несвязным, если для некоторой пары вершин
орграфа не существует маршрута соединяющего их. (рис. 20,г).
По признаку связности могут быть классифицированны и подграфы, но сначала
введем понятие максимального подграфа. Пусть дано некоторое свойство Р,
которым могут обладать графы.
Максимальным подграфом графа G относительно свойства Р называется
порожденный подграф G
sm
, обладающий этим свойством и такой, что не
существует другого порожденного графа G
s
, у которого Х
s
⊃Х
sm
и который так же
обладает свойством Р. Так, например, если в качестве свойства Р взята сильная
связанность, то максимальным сильным подграфом графа G является сильный
x
6
x
5
x
4
x
3
x
1
x
2
x
6
x
5
x
4
x
3
x
1
x
2
x
6
x
5
x
4
x
3
x
1
x
2
x
6
x
5
x
1
x
4
x
3
x
2
а)
б)
в)
г)
Рис. 20. Виды связанных графов: а) cильно связный граф; б)одно
-сторонне связный граф; в)cлабо связный граф; )Несвязный
г
р
а
ф;
соединяющий эти вершины. Это определение означает также, что любые две
вершины силносвязного графа взаимодостижимы. Пример данного графа показан
на рис. 20а.


                                                                  x1             x2
                     x1             x2

                                                             x6
        x6
                                                                                           x3
                                              x3


                    x5                                            x5             x4
                                    x4
                               а)                                           б)
                          x1             x2                            x1             x2


             x6                                         x6
                                                                                                x3
                                                   x3
                                                                                      x4
                                                                       x5
                          x5             x4
                            в)                                        г)
                  Рис. 20. Виды связанных графов: а) cильно связный граф; б)одно
                  -сторонне связный граф; в)cлабо связный граф; )Несвязный
                  граф;



         Орграф называется односторонне связным или односторонним,
если для любых двух различных его вершин xi и xj существует по крайней мере
один путь из xi в xj или из xj в xi или оба пути существуют одновременно. Граф на
рис.20,б не является сильным, так как в нем нет пути из x1 в x3, но является
односторонне связным.
         Орграф называется слабо связным или слабым, если для любых двух
различных вершин графа существует по крайней мере один маршрут,
соединяющий их. Граф, изображенный на рис.20,в не является ни сильным, ни
односторонним, поскольку в нем не существует путей от x2 к x5 и от x5 к x2. Он
слабо связный.
         Орграф называется несвязным, если для некоторой пары вершин
орграфа не существует маршрута соединяющего их. (рис. 20,г).
   По признаку связности могут быть классифицированны и подграфы, но сначала
введем понятие максимального подграфа. Пусть дано некоторое свойство Р,
которым могут обладать графы.
      Максимальным подграфом графа G относительно свойства Р называется
порожденный подграф Gsm, обладающий этим свойством и такой, что не
существует другого порожденного графа Gs, у которого Хs ⊃Хsm и который так же
обладает свойством Р. Так, например, если в качестве свойства Р взята сильная
связанность, то максимальным сильным подграфом графа G является сильный

Страницы