Многогранные графы

Читатель, незнакомый с терминологией следующих двух параграфов, может пропустить их, не теряя нити изложения.

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

полного графа). Любой -связный подграф -многогран-пого графа снова является -многогранным. Это свойство не сохраняется при Сформулированные условия не являются достаточными для многогранника, по крайней мере, с

Полный граф с вершинами является (-многогранным, и соответствующий многогранник называется симплексом.

Интересно, что каждый полный граф с вершинами может быть представлен -многогранным. Однако до сих пор не решены вопросы о том, существует ли для любого графа множество последовательных целых чисел при которых граф является -многогранным, или можно ли объединить любые две реализации в заданном пространстве с помощью непрерывного семейства реализаций. Новые многогранные графы могут быть получены из соответствующих им многогранников с помощью: (1) двойственного многогранника, в котором роли граней изменены, т. е. -мерной грани многогранника ставится в соответствие -мерная грань двойственного ему многогранника, причем соответствующие соотношения инцидентности сохраняются, (2) разрезания -мерной грани -многогранника новой, близкой к ней -мерной гранью, (3) объединения двух -многогранников по общей грани, (4) образования выпуклой оболочки двух многогранников, имеющих возможно разную размерность и находящихся в асимметрических линейных пространствах; например, формирования пирамид, (5) взятия прямого (декартова) произведения двух многогранников, имеющих возможно различную размерность например, образования призм. Полученный многогранник является -мерным.