Карта в графическом кодировании

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

Карта, закодированная в виде графа, для встроенного графа $G$ это еще один кубический граф $H$ вместе с 3-краевой раскраской $H$ . Каждое ребро $e$ из $G$ разлагается ровно на четыре вершины в $H$ , по одному для каждого выбора стороны и конечной точки ребра. Преимущество в $H$ соединяет каждую такую вершину с вершиной, представляющей противоположную сторону и ту же конечную точку $e$ ; эти края традиционно окрашены в красный цвет. Еще одно преимущество в $H$ соединяет каждую вершину с вершиной, представляющей противоположную конечную точку и ту же сторону $e$ ; эти края традиционно окрашены в синий цвет. Преимущество в $H$ третьего цвета, желтого, соединяет каждую вершину с вершиной, представляющей другое ребро. $e'$ который встречает $e$ на той же стороне и в конечной точке. ^[1]

Альтернативное описание $H$ заключается в том, что у него есть вершина для флага каждого $G$ (взаимно инцидентная тройка вершины, ребра и грани). Если $(v,e,f)$ это флаг,тогда существует ровно одна вершина $v'$ , край $e'$ , и лицо $f'$ такой, что $(v',e,f)$ , $(v,e',f)$ , и $(v,e,f')$ тоже флаги. Три цвета краев в $H$ представляют каждый из этих трех типов флагов, которые отличаются одним из трех элементов. Однако подобная интерпретация карты, закодированной в графе, требует большей осторожности. Когда одна и та же грань появляется по обе стороны ребра, как это может случиться, например, с плоским вложением дерева , две стороны порождают разные вершины драгоценного камня. И когда одна и та же вершина появляется в обеих конечных точках самоцикла , два конца ребра снова порождают разные вершины драгоценного камня. Таким образом, каждая тройка $(v,e,f)$ может быть связано с четырьмя различными вершинами драгоценного камня. ^[1]

Всякий раз, когда кубический граф $H$ может быть окрашен в 3 цвета, так что все красно-синие циклы раскраски имеют длину четыре, цветной граф можно интерпретировать как карту, закодированную графом, и представляет собой вложение другого графа $G$ .Чтобы восстановить $G$ и его вложение интерпретируют каждый двухцветный цикл $H$ как лицо вложения $H$ на поверхность , сжать каждый красно-желтый цикл в одну вершину $G$ и замените каждую пару параллельных синих ребер, оставшихся в результате сжатия, на одно ребро $G$ . ^[1]

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

Ссылки

^ Jump up to: ^а ^б ^с ^д Боннингтон, К. Пол; Литтл, Чарльз Х.К. (1995), Основы топологической теории графов , Нью-Йорк: Springer-Verlag, с. 31, номер домена : 10.1007/978-1-4612-2540-9 , ISBN 0-387-94557-1 , МР 1367285
^ Линс, Состенес (1982), «Карты с графическим кодированием», Журнал комбинаторной теории , серия B, 32 (2): 171–181, doi : 10.1016/0095-8956(82)90033-8 , MR 0657686
^ Боннингтон и Литтл (1995) , стр. 111–112.

[bl-1] Jump up to: ^а ^б ^с ^д Боннингтон, К. Пол; Литтл, Чарльз Х.К. (1995), Основы топологической теории графов , Нью-Йорк: Springer-Verlag, с. 31, номер домена : 10.1007/978-1-4612-2540-9 , ISBN 0-387-94557-1 , МР 1367285

[l-2] Линс, Состенес (1982), «Карты с графическим кодированием», Журнал комбинаторной теории , серия B, 32 (2): 171–181, doi : 10.1016/0095-8956(82)90033-8 , MR 0657686

[3] Боннингтон и Литтл (1995) , стр. 111–112.

[1]

[2]

[3]