Планарность связных графов

Теория графов - это область дискретной математики, особенностью которой является геометрический подход к изучению объектов. Основной объект теории графов-граф и его обобщения.

Одна из задач теории графов – это задача определения планарности графа, то есть поиск ответа на вопрос, можно ли изобразить граф на плоскости без пересечений ребер.

Цели исследования: изучение истории возникновения понятия планарности графов, основных понятий и свойств; исследование планарности графов на конкретных задачах; подбор задач для решения на математическом кружке.

Задачи исследования: научиться решать задачи по определению планарности с применением основных теорем и свойств связных графов; провести анализ решаемости задач на графах по количеству вершин  и ребер;

Гипотеза: для того, чтобы определить планарность исследуемого графа,  достаточно выяснить, содержит ли он подграф изоморфный графам типа K5 или K3,3.

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

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

Проведен анализ решаемости задач на графах по количеству вершин и ребер.

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