I ³ 3

n₃ + n₄ +n₅ ³ 4 т. е. в графе G', а тем более в графе G, имеется по край­ней мере 4 вершины со степенями, не превышающими 5.

§ 39. Критерии планарности

Имеется несколько критериев планарности графа. Мы рассмотрим характеризации планарности графов, данные G. С. Понтрягиным, К. Куратовским, К. Вагнером и С. Наклейном. Следует заметить, что практическая про­верка условий, которыми ниже характеризуются планарные графы, не всегда является простой. Однако разработаны эффективные алгоритмы, позволяющие для любого заданного графа или найти его плоскую укладку, или установить, что граф непланарен. Один из таких алгорит­мов приведен в § 41.

Для того чтобы сформулировать широко известный критерий Понтрягина — Куратовского, введем понятие гомеоморфизма графов. Нам понадобится операция под­разбиения ребра е = аb графа. Она состоит в следующем:

из графа удаляется ребро е и добавляются два новых ребра е₁ = аv, e₂ = vb, где v — новая вершина.

Два графа называются гомеоморфными, если оба они могут быть получены из одного и того же графа подразбиением его ре­бер.

На рис. 39.1 изображены гомеоморфные графы.

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

Исторически первым критерием планарности графов является следующий критерий, доказанный Л. С. Понтрягиным (1927 г.) и К. Куратовским (1930 г.) независимо друг от друга.