사다리꼴 그래프

그래프 이론에서 사다리꼴 그래프는 두 수평선 사이의 사다리꼴의 교차 그래프다.구간 그래프와 순열 그래프를 하위 클래스로 포함하는 공동 비교성 그래프의 한 클래스다.그래프는 해당 사다리꼴이 교차하는 경우에만 두 정점이 에지로 결합되도록 그래프의 정점에 해당하는 사다리꼴 그래프다.사다리꼴 그래프는 다간, 골룸빅, 핀터가 1988년에 도입했다.색수, 가중 독립 집합, 클라이크 커버 및 최대 가중 클라이크에 대한 $O{\displaystyle (n}$ ${\displaystyle \log \mathrm{logn}}$) ${\displaystyle {O}(n\log n)$ 알고리즘이$$ 있다.

정의 및 특성화

채널이 두 개의 수평선으로 이루어진 쌍으로 주어진 경우, 이들 선 사이의 사다리꼴은 상단의 두 점, 하단의 두 점으로 정의된다.그래프는 해당 사다리꼴이 교차하는 경우에만 두 정점이 에지로 결합되도록 그래프의 정점에 해당하는 사다리꼴 그래프다.부분 순서 집합인 =( ,<) ${\displaystyle P=(X$의 구간 순서 치수는 P₁ = P₁ … ……P의_dd 최소 d이다.부분적으로 순서가 지정된 =( ,<) ${\$$displaystyle P$$=(X,<)}$의 비교불가능성 그래프는 x와 y가 P에서 비교불가능할 경우에만 g에서 x가 y에 인접한 비방향$$ 그래프 $G{\displaystyle }$=${\displaystyle }$($X$, $E$)이다$.$비방향 그래프는 구간 순서 치수가 최대 2인 부분 순서의 비호환성 그래프인 경우에만 사다리꼴 그래프다.^[1]

적용들

VLSI 설계의 채널 라우팅 문제와 최대 분류 검색 및 사다리꼴 그래프 색상의 문제는 연결된다.양면 채널의 상단과 하단에 라벨이 부착된 일부 단자가 있을 경우, 동일한 라벨을 가진 단자는 공통 그물에 연결된다.이 그물은 동일한 라벨을 가진 가장 오른쪽 단자와 가장 왼쪽 단자를 포함하는 사다리꼴로 나타낼 수 있다.해당 사다리꼴이 교차하지 않는 경우에만 교차점 없이 그물을 라우팅할 수 있다.따라서 교차점 없이 망을 라우팅하는 데 필요한 레이어 수는 그래프의 색수와 같다.

등가표현황

사다리꼴 표현

사다리꼴 그래프는 사다리꼴 그래프의 정의를 사용하여 사다리꼴 그래프를 나타낼 수 있다.사다리꼴 그래프의 사다리꼴 표현은 그림 1에서 볼 수 있다.

상자 표현

지배적인 직사각형 또는 박스 표현은 사다리꼴 표현에서 두 선의 하단에 있는 점을 x축에 놓여 있는 것으로, 상단의 점은 유클리드 평면의 y축에 놓여 있는 것으로 매핑한다.각 사다리꼴은 평면의 축 평행 박스에 해당한다.지배^K 순서(R에서, x는 y가 지배한다고 하며, x가_i i = 1, … k에 대해 y보다_i 작으면 b가 b'의 상단 모서리를 지배한다면 b상자가 b'를 지배한다고 한다.게다가, 만약 두 박스 중 하나가 다른 박스들을 지배한다면, 우리는 그것들이 비슷하다고 말한다.그렇지 않으면 비할 데 없는 것이다.따라서 두 개의 사다리꼴은 해당 상자가 비교 가능한 경우 정확히 분리된다.박스 표현은 연관된 우위 순서를 통해 스위프 라인 알고리즘을 사용할 수 있기 때문에 유용하다.^[2]

비트랜스 그래프

비트랜스 그래프는 비트랜스 순서의 비교불가능성 그래프다.순서는 I과_x I의_y 중첩이_r t(x)와₁ t(y) 둘 다보다 적고_x I의 중심이_y I의 중심보다 작은 경우에만 x < y의 방법으로 각 꼭지점 x에 할당된 구간 I와_x 실수 t₁(x)와_r t(x)^[3]가 있는 경우에만 역행순이다.1993년에 랭글리는 경계된 비토란스 그래프가 사다리꼴 그래프의 등급과 동일하다는 것을 보여주었다.^[4]

다른 그래프 패밀리와의 관계

사다리꼴 그래프의 등급은 구간과 순열 그래프의 조합을 적절히 포함하며 구간 순서 차원이 최대 2개인 부분 순서의 비호환성 그래프와 동일하다.순열 그래프는 모든 사다리꼴에 0 영역이 있을 때 사다리꼴 그래프의 특별한 경우로 볼 수 있다.이는 상부 채널의 사다리꼴 포인트가 모두 동일한 위치에 있고 하부 채널의 포인트가 모두 동일한 위치에 있을 때 발생한다.

모든 비교가능성 그래프와 마찬가지로 사다리꼴 그래프는 완벽하다.

원 사다리꼴 그래프

서클 사다리꼴 그래프는 1993년 펠스너 등이 제안한 그래프의 한 종류다.사다리꼴 그래프 클래스의 슈퍼클래스이며, 원 그래프와 원형 아크 그래프도 포함하고 있다.원 사다리꼴은 두 개의 비교차 화음 사이에 놓여 있는 원 안의 영역이며 원 사다리꼴 그래프는 공통 원의 원 사다리꼴 패밀리를 교차 그래프로 나타낸 것이다.최대 가중 독립 집합 문제에 대한 $O{\displaystyle ({}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$) ${\displaystyle O(n^{2})$ 알고리즘과$$ 최대 가중 집합 문제에 대한 $O{\displaystyle ({}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle \log }$ ${\displaystyle n}$) ${\displaystyle {O}(n^{2}\log$ n$)$ 알고리즘이$$ 있다.

k-Trapezoid 그래프

k-Trapezoid 그래프는 사다리꼴 그래프를 더 높은 차원 순서로 확장한 것이다.그것들은 Felsner에 의해 처음 제안되었고, ${\displaystyle {}_{}}$은 포인트 x가 벡터$x1$,${\displaystyle }$…${\displaystyle }$, ${\displaystyle x_{}}$ k${\displaystyle {}_{}}$)로 표현되는 상위 차원으로 넘어가는 지배적인 박스의 정의에 의존한다$.$ ($x_{$1},\$dots$ ,$x_{k$ (k - 1)차원 범위 트리를 사용하여 좌표를 저장하고 쿼리한다.umber, maximum clique 및 maximum property set를 K-trapezoid 그래프에 $O{\displaystyle }$ (${\displaystyle n}$ ${\displaystyle {\log }^{}}$ ${\displaystyle k^{}}$- ${\displaystyle 1^{}}$ ${\displaystyle {}^{}n}$) ${\displaystyle {O}(n\log ^{k-1n)}$회$$ 단위로 적용할 수 있다${\displaystyle .}$

알고리즘

사다리꼴 그래프의 알고리즘은 일반 비교가능성 그래프의 알고리즘과 비교해야 한다.이 더 큰 등급의 그래프의 경우 최대 독립 집합과 최소 클라이크 커버 문제는 $O{\displaystyle ({n\mathrm{}}^{}}$ 2 ${\displaystyle \log }$ ${\displaystyle n}$) ${\displaystyle {O}(n^{2}\log$ n$)}$ 시간에$$ 해결할 수 있다.^[5]Dagan 외 연구진은 먼저 사다리꼴 그래프에 색칠을 위한 $O{\displaystyle (n}$ ${\displaystyle k}$)$${\$displaystyle {O}($nk$$$)$ 알고리즘을 제안했는데, 여기서 n은 노드 수, k는 그래프의 색도 수입니다.나중에 사다리꼴 그래프의 상자 표현을 사용하여 Felsner는 색수, 가중 독립 집합, 클릭 커버 및 최대 가중 클라이크에 대한 $O{\displaystyle (n}$ ${\displaystyle \log }$ ${\displaystyle n}$) ${\displaystyle {O}(n\log n)$ 알고리즘을$$ 발표했다.이러한 알고리즘에는 모두 $O{\displaystyle }$( ${\displaystyle n}$) ${\displaystyle {O}(n)}$개의$$ 공간이 필요하다.이러한 알고리즘은 스윕 라인 알고리즘을 사용할 수 있는 박스 표현의 관련 우위에 의존한다.Felsner는 $O{\displaystyle (\log }$ ${\displaystyle n}$) ${\displaystyle {O}(\log$ n$)}$ 시간에$$ 삽입, 삭제 및 쿼리 작업을 수행할 수 있는 균형 잡힌 트리를 사용할 것을 제안하며, 이 $경우{\displaystyle }$O(${\displaystyle n}$ log ${\displaystyle n}$ )$${\$displaystyle {O}(n\log$ n$)$ 알고리즘이$$ 생성된다.

인식

그래프 $G{\displaystyle }$ ${\$이(가) 사다리꼴 그래프인지 확인하려면 $G{\displaystyle }$ ${\$의 보완에서 전이$$ $방향{\displaystyle }$ F ${\$을(를) 검색하십시오$.$ 사다리꼴 그래프는 공동 비교성 그래프의 하위 집합이므로 $G{\displaystyle }$ ${\$이 사다리꼴 그래프라면 그 보완 G $complement{\displaystyle {}^{.}}$${\displaystyle{G'}}$은(는) 비교 가능한 그래프여야 한다$$.보완 $′{\$의 Transitive Orientation $F{\displaystyle }${\$displaystyle{F}$가 존재하지$$ 않는 경우 G ${\$는 사다리꼴 그래프가 아니다$$.$F{\displaystyle }$ ${\$이(가) 있는$$ 경우 $F{\displaystyle }$ ${\$이(가) 제공한 순서가 사다리꼴 순서인지$$ 테스트하십시오.사다리꼴 주문인식을 위한 가장 빠른 알고리즘은 1994년 McConnell과 Spinrad에 의해 제안되었으며, 실행 $시간$은 O${\displaystyle }$( ${\displaystyle {}^{}{2\mathrm{}}^{}}$ ) ${\displaystyle$ O$(n^{2$이 프로세스는 간격 치수 2 질문을 체인 그래프(유도 2K가₂ 없는 그래프)로 관련 초당적 그래프를 다루는 문제로 축소한다.^[6]정점 분할을 사용하여 사다리꼴 그래프의 인식 문제가 Mertzios와 Corneil에 의해 $O{\displaystyle (n}$(${\displaystyle n}$+ m${\displaystyle }$)${\displaystyle O(n(n+m)}$에 성공했으며, 여기서 $m{\displaystyle }$ ${\displaystym m}$은 가장자리 수를 나타낸다$$.이 프로세스에는 주어진 그래프 $G{\displaystyle }$ ${\$을$($를) 증강한 다음 원본 그래프의 정점을 각각 새로운 정점 쌍으로 교체하여 증강 그래프를 변환하는 작업이 포함된다.$이{\displaystyle }$ "분할 그래프"는 G ${\$가 사다리꼴 그래프인$$ 경우에만 특수 특성이 있는 순열 그래프다.^[7]

메모들

참조

• Golumbic, Martin Charles (1980). Algorithmic Graph Theory and Perfect Graphs. Academic Press. ISBN 0-444-51530-5. 제2판, 이산 수학 연보 57, 엘스비에, 2004.