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

UptoLike

ВУЗ: 

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

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

Рубрика: 

94
мизирующего общий километраж (или время,
стоимость и т.д.).
c) Проверка электрических, телефонных или же-
лезнодорожных линий. Проблема инспектиро-
вания распределенных систем (лишь некоторые
из которых названы выше) связана с непремен-
ным требованием проверки всех «компонент».
Поэтому она также является проблемой типа 2)
или близка к ней.
3.5. Задача китайского почтальона
Рассмотрим неориентированный граф
G.(X,.A). Среди вершин из X некоторые вершины
(скажем из множества X
+
) будут иметь четные
степени, а остальные (из множества X
–
= X \ X
+
) –
нечетные степени. Сумма степеней d
i
всех вершин
x
i
∈
X равна удвоенному числу ребер в A (т.к. каж-
дое ребро добавляет по единице к степеням двух
его концевых вершин) и поэтому равна четному
числу 2m. Следовательно,
и так как первая сумма четна, то вторая сумма
также четна. Но все d
i
в последней сумме нечетны,
значит число | X
–
| вершин нечетной степени четно.
m
X
i
x
X
i
x
X
i
x
i
d
i
d
i
d
2
=
∑
+
∑
=
∑
−
∈
+
∈
∈
83
В – Р + Г = 2,
где В – число вершин плоского графа, Р – число
его ребер, Г – число граней. Формула Эйлера
справедлива для плоских связных графов, в кото-
рых ни один из многоугольников не лежит внутри
другого.
Эту формулу можно доказать методом ма-
тематической индукции. Это доказательство мы
опускаем. Заметим только, что формула
справед-
лива и для пространственных многогранников.
Пусть все пять вершин графа соединены друг с
другом. Замечаем, что на графе нет ни одной гра-
ни, ограниченной только двумя ребрами. Если че-
рез φ
1
обозначить число таких граней, то φ
2
= 0.
Далее рассуждаем от противного, а именно: пред-
положим, что исследуемый граф плоский. Это зна-
чит, что для него верна формула Эйлера. Число
вершин в данном графе В = 5, число ребер Р.=.10,
тогда число граней
Г = 2 – В + Р = 2 – 5 + 10 = 7.
Это число можно представить в виде суммы:
Г = φ
1
+ φ
2
+ φ
3
+…,
где φ
3
– число граней, ограниченных тремя ребра-
ми, φ
4
– число граней, ограниченных четырьмя
ребрами и т. д.
С другой стороны, каждое ребро является
границей двух граней, а поэтому число граней
равно 2Р, в то же время 
  мизирующего общий километраж (или время,                               В – Р + Г = 2,
  стоимость и т.д.).                                  где В – число вершин плоского графа, Р – число
c) Проверка электрических, телефонных или же-         его ребер, Г – число граней. Формула Эйлера
    лезнодорожных линий. Проблема инспектиро-         справедлива для плоских связных графов, в кото-
    вания распределенных систем (лишь некоторые       рых ни один из многоугольников не лежит внутри
    из которых названы выше) связана с непремен-      другого.
    ным требованием проверки всех «компонент».              Эту формулу можно доказать методом ма-
    Поэтому она также является проблемой типа 2)      тематической индукции. Это доказательство мы
    или близка к ней.                                 опускаем. Заметим только, что формула справед-
         3.5. Задача китайского почтальона            лива и для пространственных многогранников.
                                                      Пусть все пять вершин графа соединены друг с
        Рассмотрим     неориентированный      граф    другом. Замечаем, что на графе нет ни одной гра-
G.(X,.A). Среди вершин из X некоторые вершины         ни, ограниченной только двумя ребрами. Если че-
(скажем из множества X +) будут иметь четные          рез φ1 обозначить число таких граней, то φ2 = 0.
степени, а остальные (из множества X – = X \ X +) –   Далее рассуждаем от противного, а именно: пред-
нечетные степени. Сумма степеней di всех вершин       положим, что исследуемый граф плоский. Это зна-
xi ∈ X равна удвоенному числу ребер в A (т.к. каж-    чит, что для него верна формула Эйлера. Число
дое ребро добавляет по единице к степеням двух        вершин в данном графе В = 5, число ребер Р.=.10,
его концевых вершин) и поэтому равна четному          тогда число граней
числу 2m. Следовательно,                                            Г = 2 – В + Р = 2 – 5 + 10 = 7.
                                                            Это число можно представить в виде суммы:
           ∑ di = ∑ + di + x ∑
          xi∈X               ∈X −
                                  di = 2m
                                                                      Г = φ1 + φ2 + φ3 +…,
                   xi∈X     i
                                                      где φ3 – число граней, ограниченных тремя ребра-
                                                      ми, φ4 – число граней, ограниченных четырьмя
и так как первая сумма четна, то вторая сумма         ребрами и т. д.
также четна. Но все di в последней сумме нечетны,           С другой стороны, каждое ребро является
значит число | X –| вершин нечетной степени четно.    границей двух граней, а поэтому число граней
                                                      равно 2Р, в то же время

                           94                                                  83

Страницы