대기열 번호

수학에서 그래프의 대기열 번호는 마지막 선입선출(스택) 순서 대신 첫 번째 선입선출(큐) 순서를 사용하여 숫자(책 두께)를 쌓는 것과 유사하게 정의되지 않는 그래프다.

정의

주어진 그래프의 큐 레이아웃은 가장자리 파티션과 함께 그래프 정점의 총 순서에 의해 정의된다.각 대기열의 에지 집합은 적절히 중첩되는 에지를 피하려면 필요하다: ab와 cd가 동일한 대기열의 두 에지일 경우 정점 순서에 < c < d < b>를 가질 수 없어야 한다.그래프 G의 대기열 번호 Qn(G)은 대기열 레이아웃의 최소 대기열 수입니다.^[1]

마찬가지로, 큐 레이아웃에서는 주어진 순서의 정점을 고려하여 큐 데이터 구조를 사용하여 하나의 큐에 있는 가장자리를 처리할 수 있으며, 정점에 도달하면 두 번째 끝점이 되는 모든 가장자리를 디큐어링한 후 첫 번째 끝점이 되는 모든 가장자리를 디큐어링할 수 있다.내포 조건은 정점에 도달했을 때 두 번째 끝점이 되는 모든 가장자리가 디큐어링될 준비가 되었음을 보장한다.^[1]큐 레이아웃의 또 다른 동등한 정의는 주어진 그래프를 실린더에 내장하고, 정점이 실린더의 선에 배치되며, 각 가장자리는 실린더 주위를 한 바퀴 감싼다.동일한 대기열에 할당된 가장자리는 서로 교차할 수 없지만 다른 대기열에 속하는 가장자리 사이에 교차할 수 있다.^[2]

큐 레이아웃은 히스 & 로젠버그(1992)가 정의한 것으로, 큐 대신 스택을 사용하여 동일한 방식으로 정의할 수 있는 그래프의 책 내장화에 관한 이전 연구와 유사하다.그들이 관찰한 바와 같이, 이러한 레이아웃은 병렬 대기열의 시스템을 사용하여 순열 정렬에 관한 이전의 작업과도 관련이 있으며, VLSI 설계 및 분산 알고리즘에 대한 통신 관리에서의 응용에 의해 동기 부여될 수 있다.^[1]

경계 대기열 번호가 있는 그래프 클래스

모든 나무에는 1번 대기열이 있고, 첫 번째 너비 횡단에 의해 정점 순서가 주어진다.^[3]사이비 포리스트와 그리드 그래프에도 1번 대기열이 있다.^[4]외부 평면 그래프는 최대 2개의 대기열 번호를 가지고 있다; 3-선 그래프(각 가장자리가 삼각형으로 대체된 삼각형)는 대기열 번호가 정확히 2인 외부 평면 그래프의 예다.^[5]직렬-병렬 그래프는 최대 3개의 대기열 번호를 가지며 ^[6]평면 3-tree의 대기열 번호는 최대 5개다.^[7]

2진수 de Bruijn 그래프는 2번 대기열이 있다.^[8]그d-dimensional 하이퍼 큐브 그래프 대부분의 d에 − 큐 수⌊ 로그 2⁡ d⌋{\displaystyle d-\lfloor \log_{2}d\rfloor}완전한 그래프 Kn고 완전한 이분 그래프 Ka,b의 큐 숫자 정확히:잘 알려 져 있.[9]그들은⌊ n/2⌋{\displaystyle \lfloor n/2\rfloor}와 최소{⌈/2⌉, ⌈ b/2⌉}{\display다.스타일$\min$$\{\lceil a/2\rceil ,\lceil b/2\rceil$ ^[10]$\}}.$

모든 1-Queue 그래프는 평면 그래프로, 정점이 평행선(레벨)에 배치되고 각 가장자리는 두 개의 연속된 레벨의 정점을 연결하거나 이전 레벨에서 모든 루핑을 통해 동일한 레벨의 정점 두 개를 연결하는 아치를 형성한다.반대로, 모든 아치형 평면 그래프는 1-queue 레이아웃을 가지고 있다.^[11]1992년 히스, 레이튼 & 로젠버그(1992)는 모든 평면 그래프가 경계 대기열 번호를 가지고 있다고 추측했다.이러한 추측은 2019년 두모비치 외(2020년)가 평면 그래프를 보여주면서 긍정적으로 해결되었으며, 보다 일반적으로 모든 적절한 마이너 폐쇄 등급의 그래프는 대기열 번호를 경계로 지정했다.특히 듀모비치 외 연구진(2020년)은 평면 그래프의 대기열 수가 최대 49개로 베코스, 그로네만, 래포풀루(2021년)가 42개로 줄었다는 것을 증명했다.

강력한 대기열 번호라고 불리는 대기열 번호의 변형을 사용하면, 그래프 제품의 대기열 번호는 제품에 있는 인자의 대기열 번호와 강력한 대기열 번호의 함수로 제한될 수 있다.^[12]

관련 불변제

대기열 번호가 낮은 그래프는 희소성 그래프: 정점이 n인 1-queue 그래프에는 최대 2n - 3개의 가장자리가 있고,^[13] 대기열 번호 q의 그래프에는 최대 2qn - q(2q + 1)의 가장자리가 있다.^[14]이것은 이 그래프들이 또한 작은 색수를 가지고 있다는 것을 암시한다: 특히 1-Queue 그래프는 3 색상이 가능하고, 대기열 번호 q가 있는 그래프는 적어도 2q + 1과 최대 4q 색상이 필요할 수 있다.^[14]다른 방향에서, 가장자리 수에 대한 바운드는 대기열 번호에 훨씬 약한 바운드를 의미한다: 정점과 m 가장자리가 있는 그래프에는 최대 O(mm)의 대기열 번호가 있다.^[15]랜덤 d-규칙 그래프의 경우 대기열 번호가 높은 확률로 표시되기 때문에 이 경계는 거의 빠듯하다.

${\displaystyle \Oomega \left({\frac {\sqrt{dn}}{n^{1/d}}\오른쪽).}$^[16]

1번 큐가 있는 그래프는 책 두께가 최대 2개다.^[17]고정 정점 순서의 경우, 해당 순서에 대한 책 두께와 큐 번호의 곱은 적어도 그래프의 절단 너비를 최대도로 나눈 값만큼 크다.^[18]책 두께는 대기열 번호보다 훨씬 클 수 있다. 3차 해밍 그래프에는 로그 대기열 번호가 있지만 다항식적으로 큰 책 두께가^[18] 있고 4번째 대기열 그래프에는 임의로 큰 책 두께가 있다.^[17]히스, 레이튼 & 로젠버그(1992)는 큐 번호가 기껏해야 책 두께의 선형 함수라고 추측했지만, 이 방향의 기능 바인딩은 알려져 있지 않다.3페이지 분량의 책 임베딩이 포함된 모든 초당적 그래프에 경계선 번호가 있는 경우 경계선 책 두께가 있는 모든 그래프에는 경계선 번호가 있는 것으로 알려져 있다.^[19]

Ganley & Heath(2001)는 그래프의 대기열 번호가 트리 너비의 함수로 경계될 수 있는지 여부를 물었고, S. V. Pemmaraju의 미발표 박사논문을 답이 아니라는 증거로 인용했다: 평면 3-tree는 이 증거에서 무한 대기열 번호를 가진 것으로 나타났다.그러나, 대기열 번호는 이후 트리 너비의 (두 배로 지수적인) 함수에 의해 제한되는 것으로 나타났다.^[20]

계산 복잡성

주어진 그래프의 대기열 번호를 결정하거나, 심지어 이 숫자가 1인지 테스트하는 것도 NP 완료다.^[21]

그러나, 큐 레이아웃의 정점 순서가 입력의 일부로 주어진 경우, 레이아웃의 최적 대기열 수는 k-rainbow의 최대 에지 수와 같으며, 각 에지는 내포된 쌍을 형성한다.가장자리의 큐 분할은 i-rainbow의 바깥쪽 가장자리인 엣지 e(그리고 더 큰 무지개는 아님)를 i-h 큐에 할당함으로써 수행될 수 있다.입력 그래프의 정점 수를 나타내는 O(m log n) 시간 내에 최적의 레이아웃을 구성할 수 있으며, 여기서 n은 입력 그래프의 정점 수를 나타내고 m은 에지 수를 나타낸다.^[22]

경계 대기열 번호의 그래프도 경계 확장성을 가지는데, 이는 얕은 미성년자가 가장자리 대 정점 비율(또는 동등하게 퇴보성 또는 수목성)의 희소성 그래프라는 것을 의미하며, 이는 대기열 번호의 함수와 부차 깊이의 함수에 의해 경계된다.그 결과, 경계 크기 패턴 그래프의 서브그래프 이소모르프리즘을 포함한 몇몇 알고리즘 문제에는 이러한 그래프에 대한 선형 시간 알고리즘이 있다.^[23]보다 일반적으로, 경계 확장 때문에, 그래프의 1차 논리 중 어떤 문장이 경계 대기열 번호의 주어진 그래프에 선형 시간 내에 유효한지 확인할 수 있다.^[24]

그래프 도면의 적용

큐 레이아웃이 반드시 좋은 2차원 그래프 도면을 만드는 것은 아니지만, 3차원 그래프 도면에 사용되어 왔다.특히 그래프 클래스 X는 X의 모든 n-vertex 그래프 G에 대해 두 에지(직선으로 그릴 때)가 교차하지 않도록 치수 O(n) × O(1) × O(1) × O(1)의 3차원 그리드에 G의 정점을 배치할 수 있는 경우에만 경계 대기열 번호를 가지고 있다.^[25]따라서 예를 들어 de Bruijn 그래프, 경계 트리 너비 그래프, 평면 그래프 및 적절한 마이너 폐쇄 그래프 패밀리는 선형 볼륨의 3차원 내장형이다.^[26][27][28]

메모들

참조

외부 링크

• Stack and Queue Layouts, 2009년 여름에 제시된 문제, 대학원생을 위한 연구 경험, Douglas B.서쪽