그래프 인코딩 맵

평면에 있는 그래프의 그래프 인코딩 맵(회색 삼각형 및 색상의 가장자리)(흰색 원 및 검은색 가장자리)

위상 그래프 이론에서 그래프 인코딩 맵이나 보석은 원래 그래프의 가장자리당 4개의 정점이 있는 다른 그래프를 사용하여 그래프의 셀룰러 내장 방식을 인코딩하는 방법이다.^[1]그것은 다면체에서의 기하학적 수술인 런시팅의 위상학적 아날로그다.그래프 인코딩 맵은 린스(1982)가 공식화하고 이름을 붙였다.^[2]셀룰러 임베디딩을 표현하기 위한 대체 및 동등한 시스템에는 서명된 회전 시스템과 리본 그래프가 포함된다.

내장된 그래프 $G{\displaystyle }$ ${\displaystyle G}$에 대한 그래프 인코딩 맵은 $H{\displaystyle }${\$displaystyle H}$의 3-엣지 색상과$$ 함께 또 다른 $입방{\displaystyle }$ 그래프$$H {\$displaystyle$ $H$$}$이다$.$ $G{\displaystyle }$ ${\$$displaystyle G$$}$의 각 에지 $e{\displaystyle }$ ${\$$displaystystyte$$}$는 각 선택마다 $정확히{\displaystyle }$ 4개의 꼭지점으로 확장된다$.$가장자리의 측면과 끝점$H{\displaystyle }$ ${\displaystyle H}$의 가장자리는 $e{\displaystyle }$ ${\displaystyle e}$의 반대쪽 및 동일한 끝점을 나타내는 꼭지점에 각각 연결되며$,$ 이러한 가장자리는 관례상 빨간색으로 칠해져 있다.$H{\displaystyle }$ ${\$$displaystyle H}$의 또 다른 에지는 $각{\displaystyle }$ 정점을 e {\$displaystyle$ e$}$의 반대쪽 끝점과 같은 면을 나타내는 정점에 연결하며$,$ 이러한 에지는 관례적으로 파란색이다.세 번째 색상의$$ $H{\displaystyle }$ ${\displaystyle$ $H$$}$ 에지는 각 꼭지점을 동일한 측면과 끝점에서$$ $e{\displaystyle }$ ${\displaystyle$ $e$$}$을 만나는$$ 다른$$에지 $e{\displaystyle {}^{}}$edge {\$displaystyle$ e$'}$을 나타내는 정점에 연결한다.^[1]

$H{\displaystyle }$ ${\displaystyle H}$에 대한 다른 설명은 $G{\displaystyle }$ ${\displaystyle G}$의 각 플래그에 대한 정점(정점, 가장자리 및 면의 상호 입사 3중)이 있다는 것이다$$.$$If ${\displaystyle (v,e,f)}$ is a flag, then there is exactly one vertex ${\displaystyle v'}$, edge ${\displaystyle e'}$, and face ${\displaystyle f'}$ such that ${\displaystyle (v',e,f)}$, ${\displaystyle (v,e',f)}$, and ${\displaystyle (v,e,f^{\prime })}$${\displaystyle(v,e,f')$도 플래그다$$.$H{\displaystyle }$ ${\displaystyle H}$의 세 가지 가장자리 색상은 세 가지 요소 중 하나에 의해 다른 세 가지 유형의 플래그를 각각 나타낸다$$.그러나 그래프로 인코딩된 지도를 이런 식으로 해석하려면 더 많은 주의가 필요하다.예를 들어 나무의 평면 임베딩과 같이 가장자리의 양쪽에 동일한 얼굴이 나타날 때, 양쪽은 서로 다른 보석 정점을 갖게 된다.그리고 자기루프의 양쪽 끝점에 동일한 꼭지점이 나타날 때, 가장자리의 두 끝은 다시 다른 보석 정점을 만들어낸다.이러한 방식으로 각 3중$({\displaystyle v}$, ${\displaystyle e}$, f${\displaystyle }$) ${\displaystyle(v,e,f)}$은 보석의 최대 4개의 서로 다른 정점과 연관될 수 있다$$.^[1]

입방 그래프 $H{\displaystyle }$ ${\displaystyle H}$이(가) 3-엣지 색상이 될 때마다$$ 색상의 빨간색-파란 주기가 모두 길이 4를 갖도록 색상이 표시된 그래프는 그래프 인코딩 맵으로 해석할 수 있으며, $다른{\displaystyle }$ 그래프 G ${\displaystyle G}$을(를) 내장하고 있는 것을 $나타낸다{\displaystyle }$.$$G {\$displaysty G$}와$$ 그 내장을 복구하려면 각 2-c를 해석하십시오$.$표면 $위$에$$H {\$displaystyle$ H$}$을(를) 내장한 $면$으로서 H ${\displaystyle H}$의 그레이드 사이클을 올리고, $각{\displaystyle }$ 적색 사이클을 G ${\displaystyle G}$의 단일 꼭지점으로 수축하고$,$ 수축에 의해 남겨진 각 쌍의 평행 청색 $가장자리$를 G$${\$displaysty G}$의 단일 가장자리로 교체한다$.$^[1]

그래프로 인코딩된 지도의 이중 그래프는 보석의 빨간색 가장자리가 파랗게 되고 파란색 가장자리가 빨갛게 되도록 그것을 기억하여 지도에서 얻을 수 있다.^[3]

참조