Плоские графы. Определение 2.6. Граф G(X,T)называется плоским, если его можно изобразить на плоскости так, чтобы никакие два его ребра не имели других общих точек

Определение 2.6. Граф G(X,T)называется плоским, если его можно изобразить на плоскости так, чтобы никакие два его ребра не имели других общих точек, кроме их общей вершины. Чертеж графа, на котором никакие два ребра не пересекаются, называют плоским представлением графа.

Примерами плоских графов могут служить простые циклы, деревья, лес и т. д.

Дан граф (рис. 2.14, а). Его плоским представлением является граф, изобра­женный на рис. 2.14, б.

Плоское представление имеет только плоский граф, и обратно: у всякого плоского графа всегда найдется плоское представление.

Рис. 2.14

В качестве примера неплоского графа можно привести полный граф с пятью вершинами (рис. 2.15).

Рис.2.15

Любые попытки начертить его плоское представ­ление обречены на неудачу.

Гранью в плоском представлении графа G(X.T) называется часть плоскости, ограниченная простым циклом и не содержащая внутри других циклов. Часть плоскости, расположенная вне плоского представления графа и ограниченная изнутри простым циклом, называется бесконечной гранью.

Две грани называются соседними, если их границы имеют хотя бы одно общее ребро.

Граф, представленный на рис. 2.16, имеет четыре обычные грани, ограничен­ные циклами (х₁, х₂, х₆, х₁), (х₅, х₆ х₇, х₅), (х₂, х₃, х₄, х₅, х₂), (х₂, х₅, х₇, х₆, х₂) и одну бесконечную грань, ограниченную циклом (х₁, х₂, х₃, х₄, х₅, х₆, х₁).

Грани (х₁, х₂, х₆, х₁) и (х₂, х₅, х₇, х₆, х₂) соседние, а грани (х₁, х₂, х₆, х₁) и (х₂, х₃, х₄, х₅, х₂) соседними не являются. Часть плоскости, ограничен­ная простым циклом (х₂, х₅, х₆, х₂) не признается гранью, так как содержит внутри себя цикл (х₅, х₆ х₇, х₅).

В графе, показанном на рис. 2.17, часть плоскости, ограниченная простым циклом (х₁, х₂, х₃, х₄,х₁), считается гранью, поскольку ребро (х₁, х₅), рас­положенное внутри грани, не является циклом.

x4 x2 x1
Рис. 2.16	Рис. 2.17	Рис. 2.18

Рассмотрим граф, изображенный на Рис. 2.18. Часть плоскости, заключенная между циклами (х₁, х₂, х₃, х₄, х₅, х₁) и (х₆ х₇, х₈, х₆), не является гранью, так как содержит внутри себя цикл и к тому же не ограничена циклом. Ребро (х₁, х₆) − мост, соединяющий два цикла.

Мост, соединяющий два цикла, называется перегородкой.

Граф, изображенный на рис. 2.19, не имеет бесконечной грани, поскольку она не ограничена изнутри простым циклом. Мост (х₁, х₂) явля­ется перегородкой. В плоском представлении дерева за грань при­нимают всю плоскость чертежа. Для всякого плоского графа без перегородок число вершин n,число ребер mи число граней с учетом бесконечной gсвязаны соотношением n − m + g = 2, которое называется формулой Эйлера.

Операция добавления новых ребер, в результате которой в плоском представлении графа каждая грань имеет три вершины, называется триангуляцией графа.

Плоский граф G(X,T)называется максимально плоским, или триангулирован­ным, если к нему невозможно добавить ни одного ребра так, чтобы полученный граф был плоским.

	а	б
Рис. 2.19	Рис. 2.20

Рассмотрим граф (рис. 2.20, а). Этот граф можно сделать максимально плоским (рис. 2.20, б).Каждая грань в плос­ком представлении максимально плоского графа имеет три вершины.

Эйлеровым путем в графе называется путь, содержащий все ребра графа и проходящий через каждое по одному разу.

Рассмотрим граф (рис. 2.21). Он имеет эйлеров путь (х₄, х₁, х₃, х₂, х₁, х₅, х₃).

Эйлеровым циклом в графе называется цикл, содержащий все ребра графа и проходящий через каждое ребро по одному разу.

Граф, обладающий эйлеровым циклом, называется эйлеровым графом.

X3
Рис. 2.21	Рис. 2.22

Рассмотрим граф (рис. 2.22). Данный граф является эйлеровым, так как он имеет эйлеров цикл (х₂, х₅, х₄, х₁, х₂, х₃, х₄, х₂).

Гамильтоновым путем в графе называется путь, проходящий через каждую вершину графа в точности по одному разу.

Например, граф на рис. 2.23 имеет гамильтоновы пути (х₃, х₄, х₅, х₁, х₂) и (х₃, х₄, х₂, х₅, х₁).

Гамильтоновым циклом в графе называется цикл, проходящий через каждую вершину графа в точности по одному разу.

Граф, обладающий гамильтоновым циклом, называется гамильтоновым графом.

Рис. 2.23	Рис. 2.24

Граф, изображенный на рис.2. 24, является гамильтоновым, так как имеет гамильтоновы циклы (х₁, х₇, х₆, х₃, х₄, х₅, х₂, х₁) и (х₁, х₆, х₃, х₄, х₅, х₂, х₇, х₁).

Всякий полный граф является гамильтоновым, так как он содержит такой простой цикл, которому принадлежат все вершины графа.