Геометрическая интерпретация и реализация графов

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

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

Теорема1. Каждый конечный граф можно реализовать в трехмерном евклидовом пространстве.