Что такое планарный граф: определение термина
Граф, для которого существует изображение на плоскости, где вершины отмечены точками, а ребра проведены линиями без пересечений. Важно понимать: граф может быть планарным, даже если вы сначала нарисовали его с пересечениями.
Главное, что существует другой способ нарисовать его без пересечений. В планарном графе ребра могут встречаться только в вершинах, а не «крест-накрест» в середине. Такие графы часто появляются в задачах про карты, дороги и схемы.
Где встречаются планарные графы
Планарные графы помогают моделировать ситуации, которые происходят на поверхности, например на листе бумаги или на карте. Так можно описывать районы города и дороги между ними, электрические схемы, маршруты и связи без пересечений.
У них есть особые свойства, например при правильном рисунке плоскость делится ребрами на области, которые называют гранями. Проверять планарность бывает полезно, чтобы понять, можно ли построить схему без пересекающихся проводов или линий. Поэтому планарные графы важны и в математике, и в реальных задачах.
