Дискретная математика. Ерош И.Л - 96 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

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

Рубрика: 

96
5.5. Теорема Жордана о плоских графах
Вопрос о том, является ли граф плоским или нет и какие существу
ют необходимые и достаточные условия для того, чтобы граф был плос
ким, волновали математиков давно. Первые работы на эту тему при
надлежат Жордану. Им была доказана теорема, существо которой сво
дится к следующему. Пусть на плоскости имеется некоторая непрерыв
ная замкнутая линия L. Эта линия делит всю плоскость на две части:
внутреннюю и внешнюю (рис. 5.4). Пусть на линии L имеются три пары
точек, которые нужно соединить так: a с b, c c d, e c f. Соединить a с b
можно, например, по внутренней области линией L
1
, c с d – по внеш
ней области линией L
2
, тогда линия L
3
, соединяющая e с f, обязатель
но пересечет либо L
1
, либо L
2
.
5.6. Определение числа ребер в графе
Число ребер графа можно определять различными способами. Наи
более простой способ – прямой пересчет ребер. Другой способ исполь
зует понятие степеней вершин графа. Рассмотрим граф типа a (см.
рис. 5.2) и подсчитаем степени r его вершин. Получим: r(A) = 2; r(B) = 3;
r(C) = 3; r(D) = 2; r(E) = 3; r(F) = 3. Если просуммировать степени всех
вершин и разделить это число пополам, получим количество ребер гра
фа. Так, для графа типа a имеем
233233
P8.
2
11111
22
В общем случае, пусть вершины графа обозначены A
i
(i = 1¸n), тогда
число ребер графа
12
1
P.
2
n
i
i
A
3
4
5
(5.1)
Рис. 5.4. Пояснение к теореме Жордана

Страницы