1 Уилсон р. Введение в теорию графов. – м.: Мир, 1977.

Понятие планарности играет принципиально важную роль в теории

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

1) Изучить такие основополагающие понятия теории графов, как граф и его грани, планарный граф и плоский граф, гомеоморфизм и стягивание графа (/1/, с. 9-24, 74-81).

2) Доказать теорему Куратовского, которая дает простой критерий планарности графа (/1/, с. 77-80).

3) Доказать теорему Эйлера о плоских графах (/1/, § 13; /2/, с. 59-75).

Литература, рекомендуемая для изучения темы