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


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

Признак 1.

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

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

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

1-planarnyi-graf

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

Признак 2.

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

2-planarnyi-graf,

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

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

 

Признак 3.

 

 

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

 

 

Литература:

  1. Шевченко В.В. Конспект лекций по курсу "Логистика". Донецк, ДонНТУ - 2009 г.
  2. Ткачук А.Н. Конспект лекций по курсу "Логистика". Донецк, ДонНТУ - 2008 г.


Категории: Логистика  

Об этой статье

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