3.07.1. Планарные графы. Вложимость графов в трехмерное пространство

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

Теорема. Всякий граф вкладывается в трехмерное евклидово пространство.

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

Замечание. Теорема справедлива также для мульти - и псевдографов.

< Предыдущая		Следующая >