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

Определение 1.31. Компонентой связности не-                В построенном графе можно перейти по
ориентированного графа называется его связный        ребрам от любой вершины к любой другой, и в
подграф, не являющийся собственным подграфом         нем нет циклов. Такой граф называется деревом.
никакого другого связного подграфа данного гра-            Пусть молекула содержит n атомов углерода
фа (максимально связный подграф).                    и m атомов водорода, тогда граф будет содержать
Определение 1.32. Компонентой сильной связно-        n + m вершин. Далее воспользуемся соотношени-
сти ориентированного графа называется его силь-      ем: в дереве число ребер на единицу меньше числа
но связный подграф, не являющийся собственным        вершин. Следовательно, в графе n + m – 1 ребер.
подграфом никакого другого сильно связного под-      Из вершин графа, обозначающих атомы углерода,
графа данного графа (максимально сильно связ-        выходит по 4 ребра, а из вершин, обозначающих
ный подграф).                                        атомы водорода, – одно. Используя простой факт,
Определение 1.33. Компонентой односторонней          что сумма степеней вершин, то есть сумма числа
связности неориентированного графа называется        ребер, выходящих из вершин, равна удвоенному
его односторонне связный подграф, не являющий-       числу ребер (это утверждение очевидно, посколь-
ся собственным подграфом никакого другого од-        ку каждое ребро соединяет ровно 2 вершины, и на-
носторонне связного подграфа данного графа           зывается леммой о рукопожатиях), можно напи-
(максимально односторонне связный подграф).          сать соотношения: 4n + m = 2(n + m – 1). Отсюда
      Пусть G = (X, A) неориентированный граф с      получаем, что m = 2п + 2. Следовательно, формула
множеством вершин X = {x1, ..., xn}. Квадратная      насыщенного углеводорода, имеющего n атомов
матрица S = (sij) порядка n, у которой               углерода:
                                                                          Cn H2n + 2.
             ⎧1, если вершины xi и x j принадлежат
      sij = ⎪⎨ одной компоненте связности,                          6.3. Графы и биология
             ⎪0, в противном случае                        Деревья играют большую роль в биологиче-
             ⎩
                                                     ской теории ветвящихся процессов. Для простоты
называется матрицей связности графа G.               мы рассмотрим только одну разновидность ветвя-
     Для ориентированного графа квадратная           щихся процессов – размножение бактерий. Пред-
матрица T = (tij) порядка n, у которой               положим, что через определенный промежуток

                            26                                                151