Сущностные характеристики плоского и планарного графа. Основные особенности формулы Эйлера и критерия Понтрягина-Куратовского, их доказательства. Общая характеристика двух критериев планарности. Сущность и значение процесса применения гамма-алгоритмов.
Аннотация к работе
Во многих случаях не имеет особого значения, как изобразить граф в виде рисунка на плоскости (диаграммы), поскольку изоморфные графы подобные по своей структуре и содержат ту же информацию. Однако существуют ситуации, когда необходимо, чтобы изображение графа на плоскости удовлетворяло определенные условия. Например, если граф является моделью некоторой электронной схемы или транспортной сети, где вершинами являются отдельные элементы схемы или станции, а ребрами, соответственно, (электрические проводники и пути, то желательно так расположить эти ребра на плоскости, чтобы избежать пересечений. Простое устройство этого графа, очевидное на изображении слева, не так легко обнаружить, рассматривая изображение справа.