Ленточный график

В топологической теории графов ленточный граф — это способ представления графовых вложений , эквивалентный по мощности системам вращения со знаком или графово-кодированным картам . ^[1] Он удобен для визуализации вложений, поскольку может представлять неориентированные поверхности без самопересечений (в отличие от вложений всей поверхности в трехмерное евклидово пространство ) и поскольку он опускает части поверхности, которые находятся далеко от графа, позволяя иметь отверстия, через которые можно увидеть остальную часть вложения. Ленточные графы также называют толстыми графами . ^[2]

В представлении ленточного графа каждая вершина графа представлена ​​топологическим диском, а каждое ребро представлено топологическим прямоугольником с двумя противоположными концами, приклеенными к краям дисков вершин (возможно, к одному и тому же диску). ^[3]

Представление ленточного графа может быть получено из вложения графа на поверхность (и метрики на поверхности) путем выбора достаточно малого числа и представления каждой вершины и ребра их окрестностями на поверхности. ^{[1] [4]} При малых значениях прямоугольники ребер становятся длинными и тонкими, как ленты , что и дало название представлению.${\displaystyle \epsilon}$${\displaystyle \epsilon}$${\displaystyle \epsilon}$

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

Вложения, которые могут быть представлены ленточными графами, — это те, в которых граф вложен в 2- многообразие (без границы) и в которых каждая грань вложения является топологическим диском. ^[1]

Два представления ленточного графа называются эквивалентными (и определяют гомеоморфные вложения графов), если они связаны друг с другом гомеоморфизмом топологического пространства, образованного объединением вершинных дисков и рёберных прямоугольников, который сохраняет идентификацию этих особенностей. ^[3] Представления ленточного графа могут быть эквивалентными, даже если невозможно деформировать одно в другое в трёхмерном пространстве: это понятие эквивалентности рассматривает только внутреннюю топологию представления, а не то, как оно вложено.

Однако ленточные графы также применяются в теории узлов ^[4] , и в этом приложении могут использоваться более слабые понятия эквивалентности, учитывающие трехмерное вложение.