Математика. Курзина В.М - 208 стр.

                                          208

      граф плоский тогда и только тогда, когда он не содержит подграфа,
гомеоморфного графуK5 или K3,3 .
      Любой плоский граф можно изобразить на плоскости так, чтобы все
его ребра являлись отрезками прямых.
      Последовательность дуг (0, 1), ... , (i − 1, i), (i, i + 1), ... , (r − 1, r ) на-
зывается маршрутом, соединяющим вершины 0 и r.
      Маршрут замкнут, если u 0 = u r. Маршрут называется цепью, если
все его дуги различны, и простой цепью, если все его вершины различны.

                                      2             3
                                                                 2            3
      2                3

                                      1                 4                         6
                              4                              1
                                  6                5
  1                    5                                             4        5


             а)                           б)                             в)

          Рис. 8.3. Примеры связных (а и в) и несвязных (б) графов.

      Замкнутая (простая) цепь называется (простым) циклом. Граф назы-
вается связным, если любая пара его вершин соединена маршрутом. Мак-
симальный связный подграф графа G называется компонентой связности.
Несвязный граф имеет по крайней мере две компоненты связности. Не-
трудно проверить, что граф в том и только в том случае содержит цикл
длины l > 1, если для некоторых двух различных вершин этого графа име-
ется более одной связывающей их цепи.
      Граф называется деревом, если он является связным и не содержит
циклов.
      Длина маршрута (цепи, простой цепи) равна количеству дуг в поряд-
ке их прохождения. Длина кратчайшей простой цепи, соединяющей вер-
шины ui и uj в графе G, называется расстоянием d(ui, uj) между ui и uj.
      Для ориентированных графов, т.е. графов, каждой дуге которого
приписана ориентация, уже определенное понятие маршрута дополняется
словом ориентированный. Маршрут называется замкнутым, если его пер-
вая и последняя вершина совпадают. Путь − это маршрут, в котором все
вершины различны. Контур − это нетривиальный (содержащий хотя бы
одну дугу) замкнутый маршрут, у которого все вершины различны, кроме
первой и последней. Если существует путь из вершины u в вершину v, то
говорят, что v достижима из u . Число дуг, исходящих из v, называется
полустепенью исхода вершины v , а число дуг, входящих в v , называется