Математическое моделирование на графах. Часть 1. Берцун В.Н. - 48 стр.

UptoLike

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

Рубрика:

Глава 2

ПЛОСКИЕ И ПЛАНАРНЫЕ ГРАФЫ

2.1. Свойства плоского графа

При изготовлении различных технических устройств (микросхем,

транспортных сетей без пересечений и др.) важно знать, существует

ли изоморфное представление соответствующего графа на плоско-

сти (решение задачи), удовлетворяющее определенным технологи-

ческим требованиям.

Граф G называется плоским, если его можно нарисовать на плос-

кости так, чтобы никакие два его ребра не имели общих точек, кроме

их общей вершины. Граф называется планарным, если он изоморфен

плоскому графу (допускает плоскую укладку). На рис. 2.1 изображе-

ны планарный и плоские графы [3, 11].

Рис. 2.1

Очевидно, что плоскими графами являются: простые циклы, де-

ревья, лес, географическая карта (без островных государств).

Гранью в плоском представлении графа G называется макси-

мальное по включению множество точек плоскости, каждая пара ко-

торых может быть соединена жордановой кривой, не пересекающей

ребра графа. Длина цикла, ограничивающего грань плоского графа,

называется степенью грани. Две грани называются соседними, если