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

                                    207

может соединяться двумя или более ребрами (дугами одного направления),
такие ребра (дуги) называются кратными. Дуга (или ребро) может начи-
наться и кончаться в одной и той же вершине, такая дуга (ребро) называет-
ся петлёй. Вершины, соединенные ребром или дугой, называются смеж-
ными. Ребро (дуга) и любая из его двух вершин называются инцидентны-
ми. Говорят, что дуга (i, j) соединяет вершины i и j, а ребро [i, j] начина-
ется в вершине i и кончается в вершине j.
      Граф называется плоским (планарный граф), если он может быть
изображен на плоскости так, что вершинам соответствуют различные точ-
ки плоскости, а линии, соответствующие ребрам, (исключая их концевые
точки), не проходят через точки, соответствующие вершинам и не пересе-
каются. Говорят, что плоский граф − это граф, допускающий правильную
укладку на плоскости. (Задачи о проектировании коммуникаций, сетей
приводят к плоским графам). Любая правильная (без пересечения ребер)
укладка связного плоского графа порождает разбиение плоскости на от-
дельные области (грани). Такое разбиение плоскости называется плоской
картой.
      Теорема. Для любой плоской карты имеет место формула Эйлера:
                  n−m+r = 2 ,                                           (8.1)
где n − число вершин; m − число ребер; r− число областей карты (включая
внешнюю область).
      Примеры.

        2


               3
11



        4


      K 4,1               K 4,2                 K5                 K 3, 3

      Рис. 8.2 . K 4,1 − плоский граф; K 4,2− плоский граф; K5 − полный граф
с n = 5; K3,3 − полный двудольный граф, имеющий по три вершины в каж-
дой доле.

     Подграфом G′ (V′, E′) графа G (V, E) называется граф с множеством
вершин V ′ ⊆ V и множеством ребер (дуг) E ′ ⊆ E , каждое из которых
инцидентно только вершинам из V′.
     Графы K5 и K3,3 являются в некотором смысле минимальными непло-
скими графами в силу теоремы Понтрягина-Куратовского: