양당 반

그래프 이론에서, 초당적 그래프 G = (U,V,E)의 반 또는 반제곱은 정점 집합이 양분법(일반성의 손실 없이 U)의 한 면이며, G에서 서로 2의 거리에 있는 U와_i U의 두_j 꼭지점 각각에 대한 에지 uu가_ij 있는 그래프다.^[1]즉, 보다 콤팩트한 표기법에서, 위첨자 2는 그래프의 정사각형을 나타내고 대괄호는 유도 하위그래프를 나타내는 G[U²]이다.

예

예를 들어, 전체 초당 그래프_n,n K의 2분의 1은 전체 그래프 K이고_n, 하이퍼큐브 그래프의 2분의 1은 절반의 입방체 그래프다.G가 거리-정규 그래프일 때, 그것의 두 개의 초당적 반쪽은 모두 거리-정규 그래프다.^[2]예를 들어, 절반으로 줄어든 포스터 그래프는 정밀하게 많은 도-6 거리 정규 지역 선형 그래프 중 하나이다.^[3]

표현 및 경도

모든 그래프 $G{\displaystyle }$ ${\displaystyle G}$은(는) $G{\displaystyle }$ ${\displaystyle G}$의 가장자리를 두 개의 가장자리 경로로$$ 세분화하여 형성된 다른 그래프의 절반이다$$.보다 일반적으로 $G{\displaystyle }$ ${\displaystyle G}$을(를) 양분 반으로 나타내는$$ 것은 $G{\displaystyle }$ ${\displaystyle G}$의 어떤 클라이크 가장자리 커버를 취하고$$ 각 클라이크를 별로 대체함으로써 찾을 수 있다.^[4]모든 대표자는 이런 식으로 생겨난다.가장 작은 클릭 에지 커버를 찾는 것은 NP-하드이기 때문에 $G{\displaystyle }$ ${\displaystyle$ G$}$이(가) 양분점 절반인$$ 정점이 가장 적은 그래프를 찾는 것도 그렇다.^[5]

특례

지도 그래프, 즉 평면 내 내부 분리 단순 연결 영역의 교차 그래프는 정확히 초당적 평면 그래프의 절반이다.^[6]

참고 항목

• 쌍방향 이중커버전

참조