Графически закодированная карта

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

Граф-кодированная карта для вложенного графа — это еще один кубический граф вместе с 3-рёберной раскраской . Каждое ребро из расширяется ровно на четыре вершины в , по одной для каждого выбора стороны и конечной точки ребра. Ребро в соединяет каждую такую ​​вершину с вершиной, представляющей противоположную сторону и ту же конечную точку ; эти ребра по соглашению окрашены в красный цвет. Другое ребро в соединяет каждую вершину с вершиной, представляющей противоположную конечную точку и ту же сторону ; эти ребра по соглашению окрашены в синий цвет. Ребро в третьего цвета, жёлтого, соединяет каждую вершину с вершиной, представляющей другое ребро , которое встречается на той же стороне и в той же конечной точке. ^[1]${\displaystyle G}$ ${\displaystyle H}$${\displaystyle H}$${\displaystyle е}$${\displaystyle G}$${\displaystyle H}$${\displaystyle H}$${\displaystyle е}$${\displaystyle H}$${\displaystyle е}$${\displaystyle H}$${\displaystyle е'}$${\displaystyle е}$

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

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

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