Двудольные графы

Двудольный граф (или биграф, или четный граф) — это граф G (V, E), такой что множество V разбито на два непересекающихся множества V ₁ и V ₂ (), причем всякое ребро из Е инцидентно вершине из V ₁ и вершине из V ₂ (то есть соединяет вершину из V ₁ с вершиной из V ₂). Множества V ₁ и V ₂ называются долями двудольного графа. Если двудольный граф содержит все ребра, соединяющие множества V ₁ и V ₂, то он называется полным двудольным графом. Если | V ₁| = m и | V ₂| = n, то полный двудольный граф обозначается K_m,n. В качестве примера на
рис. 8 приведена диаграмма графа К _3,3.

Рис. 8. Диаграмма двудольного графа K_3,3

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

Планарные и плоские графы

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

Таким образом, планарный граф – это граф, который можно уложить на плоскости, а плоский граф – это граф, уже уложенный на плоскости. На рис. 9 представлены диаграммы планарного и изоморфного ему плоского графов.

Рис. 9. Планарный и изоморфный ему плоский графы

Область плоскости, ограниченная ребрами плоского графа, внутри которой нет ни вершин, ни ребер, называется гранью и обозначается f _i. Ребра грани образуют простой цикл. Считается, что всякий плоский граф имеет одну бесконечную грань, т.е. часть внешней плоскости, окружающей граф.

Имеет место формула Эйлера , где f – количество граней плоского графа.

Количество граней плоского графа не зависит от способа укладки его на плоскость и равно .

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