Математика. Быкадорова Г.В. - 51 стр.

                                   51
          Между двумя вершинами может быть несколько ребер (ребра
 x3 , x 4 , x5 на рисунке 6.8,а), и их число называется кратностью ребра.
Ребро АВ имеет кратность, равную 3.
          Число ребер, инцидентных вершине, называется степенью вершины
и обозначается deg(A). Например, вершина А на рис. 6.8,а имеет степень
deg(А)=5. Вершина является четной (нечетной), если ее степень четное
(нечетное) число.
          Вершина графа, имеющая степень, равную нулю, называется
изолированной, а граф, состоящий из изолированных вершин, называется
нуль-графом. Вершина графа, имеющая степень 1, называется висячей.
          Граф называется полным, если любые две его различные вершины
соединены одним и только одним ребром.
          Дополнением графа G = M ; R является граф G = M ; R ′ с теми же
вершинами М и имеющий те и только те ребра R ′ , которые необходимо
добавить к графу G, чтобы он стал полным (рис.6.8,в,г).
                    А             c
         х5        •              •              •              •
                       x1 b              d
              x4           •            • •             • •           •
                 x3 x2
  •В                   a•        •e       •        •      •         •
                 С•
         a)                   б)               в)           г)
       Рис. 6.8. Граф со смежными вершинами (а), полный граф (б),
                  графы (в) и (г), дополняющие друг друга.
     Последовательность ребер неориентированного графа, в которой
вторая вершина предыдущего ребра совпадает с первой вершиной
следующего, называется маршрутом. Число ребер маршрута есть длина
маршрута.
     Если начальная вершина маршрута совпадает с конечной, то такой
маршрут является замкнутым или циклом. Если ребро встретилось только
один раз, то маршрут называется цепью.
     Расстоянием между двумя вершинами называется минимальная
длина из всех возможных маршрутов между этими вершинами:
d(a,b)=min|a…b| .
     В орграфе маршрут является ориентированным и называется путем.
При этом направление каждой дуги должно совпадать с направлением
пути и ни одно ребро не должно встречаться дважды. Другими словами,
путь – упорядоченная последовательность дуг ориентированного графа.
     Цепь, путь и цикл в ориентированном графе называются простыми,
если они проходят через любую вершину не более одного раза.