Математические модели в управлении. Заболотский В.П - 75 стр.

UptoLike

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

Рубрика:

Определение 2.1.17. Граф называется планарным, если можно по-

строить такую его диаграмму в двухмерном пространстве (на плоско-

сти, сфере), что любая точка, принадлежащая двум и более дугам гра-

фа, не является внутренней точкой никакой дуги этого графа.

Такая диаграмма называется геометрической реализацией графа.

На геометрической реализации графа общими точками дуг могут

быть только вершины, т. е. дуги графа при таком геометрическом пред-

ставлении не пересекаются.

Не всякий граф является планарным. Советский математик акаде-

мик Л. С. Понтрягин и польский ученый К. Куратовский независимо

друг от друга показали, что для того, чтобы конечный граф имел гео-

метрическую реализацию (был планарным), необходимо и достаточно,

чтобы он не имел частей вида, приведенных на рис. 2.1.5.

Рис. 2.1.5. Части графа, при наличии которых граф не является планарным

Рис. 2.1.4. Виды графа, приведенного на рис. 2.1.3, а: а – часть графа;

б – подграф; в – суграф

б) в)