Графы и сети. Харитонова Е.В. - 17 стр.

UptoLike

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

Рубрика:

Например, граф, изображенный на рис. 1.32, изображается также другим способом

(рис. 1.33). Граф, изображенный на рис. 1.34, может быть изображен, как показано на рис.

1.35.

Рис. 1.32 Рис. 1.33

Рис. 1.34 Рис. 1. 35

● Планарным графом называется граф, который может быть изображен в

плоскости, так что его ребра не пересекаются. Граф, который не является пла-

нарным, называется непланарным.

Рассмотрим граф как рисунок, изображенный на листе бумаги. Если граф

планарен и нарисован так, что никакие линии не пересекаются, и его необходи-

мо разрезать вдоль

ребер, то граф окажется разделенным на части, включая

внешнюю часть. Такие части называются гранями. Граница каждой грани явля-

ется циклом.

● Грань планарного графа – максимальный участок плоскости такой, что

любые две точки этого участка могут быть соединены кривой, не пересекаю-

щей ребро графа.

ТЕОРЕМА 1.7. Если G – связный планарный граф, содержащий

υ вер-

шин, e ребер и f граней, то υ – e + f = 2.

ТЕОРЕМА 1.8. Полный двудольный граф K

3,3

не является планарным.

Лемма. В произвольном связном планарном графе G с количеством вер-

шин не менее трех имеет место неравенство 3υ – e ≥ 6.

ТЕОРЕМА 1.9. Полный граф K

не является планарным.

d b

c d e

a b

c d e