Теория графов. Планарный граф

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

Признак 1.

Если в составе графа есть графы K_3,3 или K₅, то эти графы никогда не будут планарными.

Тут K₅ – связный граф с 5-ю вершинами (рис 2.19 а);

K_3,3 – граф, который представляется в виде 2-х связных графов в виде треугольника (рис. 2.19 б).

1-planarnyi-graf

Рисунок 2.19 – Графы K₅ (а) и K_3,3 (б).

Признак 2.

В произвольном планарном графе с количеством вершин не менее 3 справедливо выражение

Тут v – количество вершин;

e – количество ребер.

Признак 3.

Каждый планарный граф содержит вершину 5 или менее.

Литература:

	2017-11-02 13:03:14
	3408
	user
	Логистика; Лекции; Теория графов;
	В статье рассматривается планарный граф