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

UptoLike

ВУЗ: 

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

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

Рубрика: 

28
S =
1 1 0 1 1
1 1 0 1 1
0 0 1 0 0
1 1 0 1 1
1 1 0 1 1
⎛⎞
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎜⎟
⎝⎠
Мы видим, что 1 – ая, 2 – ая, 4 –ая и 5 – ая
строки матрицы S одинаковы.
Пример 1.15.
У ориентированного графа, изображенного
на рис. 12 две компоненты сильной связности.
Первая компонента связности включает вершины
x
1
, x
2
, x
3
, x
5
, а вторая состоит из одной вершины x
4
.
Действительно, для любой пары вершин из мно-
жества {x
1
, x
2
, x
3
, x
5
} существует хотя бы один
путь, соединяющий эти вершины. Например, путь
(x
1
, x
2
, x
5
, x
3
, x
1
) соединяет все эти вершины. Из
вершины x
4
нет пути ни в одну вершину графа.
Рис. 12.
149
6.2. Графы и химия
Еще А. Кэли рассмотрел задачу о возмож-
ных структурах насыщенных (или предельных)
углеводородов, молекулы которых задаются фор-
мулой:
C
n
H
2n+2
Все атомы углеводорода четырехвалентны,
все атомы водорода одновалентны.
Молекула каждого предельного углеводоро-
да представляет собой дерево. Если удалить все
атомы водорода, то оставшиеся атомы углеводо-
рода также будут образовывать дерево, каждая
вершина которого имеет степень не выше 4. Сле-
довательно, число возможных структур предель-
ных углеводородов, т.е. число гомологов данного
вещества
, равно числу деревьев с вершинами сте-
пени не больше четырех.
Таким образом, подсчет числа гомологов
предельных углеводородов также приводит к зада-
че о перечислении деревьев определенного типа.
Эту задачу и ее обобщения рассмотрел Д. Пойа.
Приведем следующий пример.
Насыщенным углеводородом называется со-
единение атома углерода С, имеющего валент-
ность 4, и водорода Н, имеющего валентность 1, в
котором при заданном числе атомов углерода со-
держится наибольшее число атомов водорода. 
                      ⎛1   1 0 1 1⎞
                      ⎜1   1 0 1 1⎟⎟                                     6.2. Графы и химия
                 S=   ⎜
                      ⎜0   0 1 0 0⎟                           Еще А. Кэли рассмотрел задачу о возмож-
                      ⎜            ⎟
                      ⎜1   1 0 1 1⎟                     ных структурах насыщенных (или предельных)
                      ⎜1   1 0 1 1⎟⎠                    углеводородов, молекулы которых задаются фор-
                      ⎝
                                                        мулой:
     Мы видим, что 1 – ая, 2 – ая, 4 –ая и 5 – ая                               Cn H2n+2
строки матрицы S одинаковы.
                                                              Все атомы углеводорода четырехвалентны,
                       Пример 1.15.                     все атомы водорода одновалентны.
        У ориентированного графа, изображенного               Молекула каждого предельного углеводоро-
на рис. 12 две компоненты сильной связности.            да представляет собой дерево. Если удалить все
Первая компонента связности включает вершины            атомы водорода, то оставшиеся атомы углеводо-
x1, x2, x3, x5, а вторая состоит из одной вершины x4.   рода также будут образовывать дерево, каждая
Действительно, для любой пары вершин из мно-            вершина которого имеет степень не выше 4. Сле-
жества {x1, x2, x3, x5} существует хотя бы один         довательно, число возможных структур предель-
путь, соединяющий эти вершины. Например, путь           ных углеводородов, т.е. число гомологов данного
(x1, x2, x5, x3, x1) соединяет все эти вершины. Из      вещества, равно числу деревьев с вершинами сте-
вершины x4 нет пути ни в одну вершину графа.            пени не больше четырех.
                                                              Таким образом, подсчет числа гомологов
                                                        предельных углеводородов также приводит к зада-
                                                        че о перечислении деревьев определенного типа.
                                                        Эту задачу и ее обобщения рассмотрел Д. Пойа.
                                                              Приведем следующий пример.
                                                              Насыщенным углеводородом называется со-
                                                        единение атома углерода С, имеющего валент-
                                                        ность 4, и водорода Н, имеющего валентность 1, в
                                                        котором при заданном числе атомов углерода со-
                            Рис. 12.
                                                        держится наибольшее число атомов водорода.

                              28                                                 149

Страницы