В топологической теории графов , А граф-закодирована карта или драгоценный камень представляет собой метод , кодирующий клеточное вложение графа с использованием другого графа с четырьмя вершин на край исходного графа. [1] Это топологический аналог runcination , геометрической операции над многогранниками . Графические карты были сформулированы и названы Линсом (1982) . [2] Альтернативные и эквивалентные системы для представления клеточных вложений включают системы вращения со знаком и ленточные графы .
Карта с кодировкой графа для встроенного графа это еще один кубический граф вместе с 3-краевой окраски из. Каждый край из раскладывается ровно на четыре вершины в , по одному для каждого выбора стороны и конечной точки ребра. Край в соединяет каждую такую вершину с вершиной, представляющей противоположную сторону и тот же конец ; эти края обычно окрашиваются в красный цвет. Еще одно преимущество в соединяет каждую вершину с вершиной, представляющей противоположную конечную точку и ту же сторону ; эти края обычно окрашены в синий цвет. Край в третьего цвета, желтого, соединяет каждую вершину с вершиной, представляющей другое ребро что встречает на той же стороне и на той же конечной точке. [1]
Альтернативное описание является то , что она имеет вершину для каждого флага из(взаимно инцидентная тройка вершины, ребра и грани). Если является флагом, то есть ровно одна вершина , край и лицо такой, что , , а также тоже флаги. Три цвета краев впредставляют каждый из этих трех типов флагов, которые отличаются одним из своих трех элементов. Однако такая интерпретация карты с графической кодировкой требует большей осторожности. Когда одна и та же грань появляется с обеих сторон ребра, как это может случиться, например, при плоском вложении дерева , две стороны образуют разные вершины камня. И когда одна и та же вершина появляется на обоих концах петли , два конца ребра снова порождают разные вершины камня. Таким образом, каждая тройкаможет быть связано с четырьмя различными вершинами драгоценного камня. [1]
Когда кубический граф может быть трехреберным, так что все красно-синие циклы раскраски имеют длину четыре, цветной граф может быть интерпретирован как карта с кодировкой графа и представляет собой вложение другого графа . Чтобы восстановить и его вложения, интерпретируйте каждый двухцветный цикл как лицо вложения на поверхность, сожмите каждый красно-желтый цикл в одну вершину, и замените каждую пару параллельных синих ребер, оставшихся после сжатия, одним ребром . [1]
Двойственный граф графа кодированной карты может быть получен из карты, перекрашивания его так , что красные края драгоценного камня стали синими и синими края становятся красными. [3]
Рекомендации
- ^ а б в г Боннингтон, К. Пол; Литтл, Чарльз ХК (1995), Основы топологической теории графов , Нью-Йорк: Springer-Verlag, стр. 31, DOI : 10.1007 / 978-1-4612-2540-9 , ISBN 0-387-94557-1, MR 1367285
- ^ Линс, Sóstenes (1982), "Граф-кодированных карт", Журнал комбинаторной теории , Series B, 32 (2): 171-181, DOI : 10,1016 / 0095-8956 (82) 90033-8 , МР 0657686
- ^ Bonnington & Литтл (1995) , стр. 111-112.