Основные понятия теории графов. Гладких О.Б - 27 стр.

UptoLike

ВУЗ: 

ЕГУ им. Бунина | Елец

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

Рубрика: 

150
Найдите формулу насыщенного углеводорода, со-
держащего n атомов углерода.
Рассмотрим граф, в котором вершинами яв-
ляются атомы, а ребрами – соответствующие ва-
лентные связи между ними. Покажем от противно-
го, что в графе не существует цикла, то есть воз-
можности, переходя по ребрам графа из вершины
в вершину, вернуться в исходную вершину. Если
цикл есть, то должен быть составлен из атомов уг-
лерода, поскольку водород имеет валентность 1 и
может соединяться только с одним атомом. В слу-
чае существования цикла разорвем связь между
двумя атомами углерода и присоединим к каждо-
му из них еще по атому водорода. Число атомов
водорода увеличится, значит, исходный граф опи-
сывал не молекулу насыщенного углеводорода.
Рис. 6.1.
Н
С
С
С
С
Н Н
Н
Н
вершина
ребро
Н
Н
Н
Н
Н
27
t
ij
=
1, если существует путь из в ,
0, в противном случае
ij
x
x
⎧
⎨
⎩
называется матрицей односторонней связности
(достижимости).
Квадратная матрица S = (s
ij
) порядка n, у ко-
торой
s
ij
=
1, если существует путь из
в и из в ,
0, в противном случае
i
jji
x
xxx
⎧
⎪
⎨
⎪
⎩
называется матрицей сильной связности.
Пример 1.14.
У неориентированного графа, изображенно-
го на рис. 11 две компоненты связности. Первая
компонента связности включает вершины x
1
, x
2
, x
4
,
x
5
, а вторая состоит из одной вершины x
3
.
Рис. 11.
Матрица связности этого графа имеет вид: 
Найдите формулу насыщенного углеводорода, со-
                                                          tij = ⎧⎨
                                                                 1, если существует путь из xi в x j ,
держащего n атомов углерода.                                    ⎩0, в противном случае
      Рассмотрим граф, в котором вершинами яв-
ляются атомы, а ребрами – соответствующие ва-       называется матрицей односторонней связности
лентные связи между ними. Покажем от противно-      (достижимости).
го, что в графе не существует цикла, то есть воз-         Квадратная матрица S = (sij) порядка n, у ко-
можности, переходя по ребрам графа из вершины       торой
в вершину, вернуться в исходную вершину. Если                     ⎧1, если существует путь из xi
цикл есть, то должен быть составлен из атомов уг-          sij = ⎪⎨ в x j и из x j в xi ,
лерода, поскольку водород имеет валентность 1 и                   ⎪
может соединяться только с одним атомом. В слу-                   ⎩0, в противном случае
чае существования цикла разорвем связь между        называется матрицей сильной связности.
двумя атомами углерода и присоединим к каждо-
му из них еще по атому водорода. Число атомов                           Пример 1.14.
водорода увеличится, значит, исходный граф опи-            У неориентированного графа, изображенно-
сывал не молекулу насыщенного углеводорода.         го на рис. 11 две компоненты связности. Первая
                                                    компонента связности включает вершины x1, x2, x4,
      Н        Н         Н         Н    вершина     x5, а вторая состоит из одной вершины x3.
                                        ребро
 Н    С        С         С         С    Н


      Н        Н         Н         Н


                       Рис. 6.1.
                                                                              Рис. 11.

                                                         Матрица связности этого графа имеет вид:

                         150                                                        27

Страницы