스큐 대칭 그래프

자동화에 의해 정의된 그래프 패밀리
거리 변환의	→	거리 규칙의	←	매우 규칙적인.
↓
대칭(대칭 변환)	←	t-변환, t ≥ 2		꼬불꼬불한
↓
(연결된 경우) 정점 및 에지 변환	→	가장자리-변환적이고 규칙적인	→	가장자리-변환성
↓		↓		↓
정점 변환의	→	정칙의	→	(양립할 경우) 복엽의
↑
케이리 그래프	←	무궤도적		비대칭의

수학의 한 분야인 그래프 이론에서, 스큐 대칭 그래프는 고정된 점 없이 비자발적인 이형성 하에서 가장자리를 모두 뒤집어서 형성된 그래프인 자신의 전치 그래프와 이형성을 갖는 방향화된 그래프다.스큐 대칭 그래프는 양방향 그래프의 이중 커버 그래프와 동일하다.

스큐 대칭 그래프는 투테(1967년)가 반대칭 디그그래프라는 이름으로 처음 도입했고, 이후에는 젤린카의 극성 그래프의 이중 커버 그래프(1976b)로 도입됐으며, 여전히 자슬라프스키(1991)가 양방향 그래프의 이중 커버 그래프로 도입됐다.그것들은 그래프에서 일치점을 찾기 위한 알고리즘의 교대 경로와 교대 사이클 검색을 모델링하고, 콘웨이의 삶의 게임에서 정물 패턴을 그래프 그리기에서, 그리고 2-만족도 문제를 효율적으로 해결하기 위해 사용되는 시사 그래프에서 더 단순한 구성요소로 분할할 수 있는지 여부를 테스트하는 데 있다.

정의

정의된 바와 같이, 예를 들어 골드버그 & 카르자노프(1996)에 의해, 스큐 대칭 그래프 G는 지시된 그래프로서, G의 다른 정점에 대한 G의 정점 함수 mapping 매핑과 함께 다음과 같은 속성을 만족한다.

1. 모든 꼭지점 v, σ(v) ≠ v에 대해,
2. 모든 꼭지점 v에 대해 σ(σ)(v) = v,
3. 모든 에지(u,v), (σ(v),σ(u)에 대해서도 에지가 되어야 한다.

하나는 G의 가장자리에 있는 방향 반전 함수로 function을 확장하기 위해 세 번째 특성을 사용할 수 있다.

G의 전치 그래프는 G의 모든 가장자리를 역전시켜 형성된 그래프로, σ은 G에서 전치까지의 그래프 이형성을 정의한다.그러나, 스큐 대칭 그래프에서는, 정점을 이형성에 의해 스스로 매핑하거나 이형성의 사이클에서 두 정점 이상을 그룹화하는 것이 아니라, 이형동성이 각 정점을 다른 정점과 쌍을 이루도록 하는 것이 추가로 필요하다.

스큐 대칭 그래프의 경로나 사이클은 경로나 사이클의 각 정점 v에 대해 해당 정점 σ(v)이 경로나 사이클의 일부가 아닌 경우 규칙적이라고 한다.

예

정점 수가 짝수인 모든 방향 경로 그래프는 경로의 양쪽 끝을 교환하는 대칭을 통해 스큐 대칭이다.그러나 정점 수가 홀수인 경로 그래프는 스큐 대칭이 아니다. 왜냐하면 이러한 그래프의 방향 반전 대칭은 경로의 중심 정점을 그 자체로 매핑하기 때문이다. 이는 스큐 대칭 그래프에는 허용되지 않는 것이다.

마찬가지로 방향 사이클 그래프는 정점 수가 짝수인 경우에만 스큐 대칭이다.이 경우 그래프의 스큐 대칭을 실현하는 다른 매핑 σ의 수는 사이클 길이의 절반과 같다.

극/스위치 그래프, 이중 포함 그래프 및 양방향 그래프

스큐 대칭 그래프는 극 그래프 또는 스위치 그래프의 이중 커버 그래프로 동등하게 정의될 수 있으며,^[1] 이는 각 정점에 입사하는 가장자리가 두 개의 하위 집합으로 분할되는 비방향 그래프다.극 그래프의 각 꼭지점은 스큐 대칭 그래프의 두 정점에 해당하며 극 그래프의 각 가장자리는 스큐 대칭 그래프의 두 가장자리에 해당한다.이 동등성은 골드버그와 카르자노프(1996)가 스큐 대칭 그래프의 측면에서 일치 문제를 모형화하기 위해 사용한 것이다. 이 응용에서 각 정점 에지의 두 부분 집합은 일치하지 않는 가장자리와 일치된 가장자리다.젤린카(F. Zitek에 이은)와 쿡은 한 방향에서 들어오는 선로를 통해 기차가 스위치로 진입하면 다른 방향의 선로를 통해 빠져 나가야 하는 선로로서 극성 그래프의 정점을 시각화한다.열차 선로에서 주어진 지점들 사이에 스스로 교차하는 매끄러운 곡선을 찾는 문제는 특정한 종류의 그래프 도면이 유효한지 시험하는 데 있다.^[2]스큐-큐브릭 그래프의 정규 경로 검색으로 모델링할 수 있다.

밀접하게 관련된 개념은 양방향 그래프 또는 편광 그래프로,^[3] 각 가장자리의 양쪽 끝이 다른 끝과 독립적으로 머리 또는 꼬리일 수 있는 그래프다.양방향 그래프는 각 정점에 있는 가장자리 부분을 머리와 꼬리로 분할하여 결정하도록 함으로써 극성 그래프로 해석할 수 있지만, 단일 정점에서 머리와 꼬리의 역할을 스와핑("정점 전환")하면 다른 양방향 그래프가 생성되지만 동일한 극성 그래프가 생성된다.^[4]

극지방 그래프 G에서 이중 커버 그래프(즉, 해당 스큐 대칭 그래프)를 구성하려면 G의 각 꼭지점 v와₀ v의₁ 정점 v에 대해 생성하고, G의 각 에지 e = (u_i,v) = v. 각 에지 e = (u,v)에_{1 − i} 대해 커버 그래프에서 u에서 u에서 u로 방향의 두 개의 방향 에지를 생성하십시오.e가 v에서 가장자리의 첫 번째 부분 집합에 있는 경우 이 두 개의 가장자리는 u에서₀ v로₀₁, e가 두 번째 부분 집합에 있는 경우 u에서₀ v로₁, v에서₀ u로₁₁ 각각이다.다른 방향에서, 스큐 대칭 그래프 G가 주어진 경우, G의 모든 해당 정점 쌍에 대해 하나의 꼭지점, G의 모든 해당 가장자리 쌍에 대해 하나의 비방향 가장자리가 있는 극성 그래프를 형성할 수 있다.극성 그래프의 각 꼭지점에 있는 비방향 가장자리는 극성 그래프의 꼭지점에 따라 두 개의 부분 집합으로 분할될 수 있다.

스큐 대칭 그래프의 정규 경로 또는 주기는 극 그래프의 각 정점에 있는 에지의 부분 집합에서 최대 하나의 에지를 사용하는 경로 또는 주기에 해당한다.

매칭

비방향 그래프로 일치를 구성할 때, 경로의 홀수 위치의 에지가 주어진 부분 일치의 일부가 아니며 경로의 짝수 위치의 에지가 일치의 일부인 정점으로부터 시작하고 끝나는 정점의 경로인 교대 경로를 찾는 것이 중요하다.이러한 경로의 일치된 가장자리를 일치에서 제거하고 일치하지 않는 가장자리를 추가하면 일치의 크기를 늘릴 수 있다.마찬가지로, 일치된 가장자리와 일치하지 않는 가장자리의 교대 주기는 가중 일치 문제에서 중요하다.비방향 그래프의 교대 경로 또는 사이클은 스큐 대칭 지시 그래프에서 정규 경로 또는 사이클로 모델링할 수 있다.^[5]지정된 일치 M을 사용하여 비방향 그래프 G에서 스큐 대칭 그래프를 생성하려면 각 정점의 가장자리가 일치하고 일치하지 않는 가장자리로 분할되는 스위치 그래프로 G를 보십시오. G의 교대 경로는 이 스위치 그래프에서 정규 경로가 되고 G의 교대 사이클은 스위치 그래프에서 정규 사이클이 된다.

Goldberg & Karzanov(1996)는 스큐 대칭 그래프의 두 꼭지점 사이에 정규 경로의 존재를 선형 시간 내에 시험할 수 있음을 보여주기 위해 교대 경로 알고리즘을 일반화했다.어떤 에지 e와 σ(e)에 동일한 길이를 할당하는 그래프 가장자리에 음이 아닌 길이 함수를 추가로 부여하면, m 에지와 정점이 있는 스큐 대칭 그래프에서 주어진 노드 쌍을 연결하는 최단 정규 경로는 O(m log n) 시간에 테스트할 수 있다.길이 함수가 음의 길이를 가질 수 있는 경우, 음의 정규 주기의 존재를 다항 시간에서 시험할 수 있다.

일치에서 발생하는 경로 문제와 함께 최대 흐름 최소 절단 정리의 스큐 대칭 일반화도 연구되었다.^[6]

정물론

쿡(2003)은 관련 스위치 그래프가 정기적인 주기를 포함하는 경우에만 콘웨이 생명의 게임에서 정물 패턴을 두 개의 더 작은 정물로 분할할 수 있다는 것을 보여준다.그가 보여주듯이, 정점당 가장자리가 최대 3개인 스위치 그래프의 경우, 이러한 단순화가 더 이상 수행되지 않을 때까지 모든 가장자리가 단일 파티션에 속하는 정점과 브리지(그래프의 연결을 끊는 부분 제거)를 반복적으로 제거하여 다항 시간 내에 테스트할 수 있다.결과가 빈 그래프일 경우 정기적인 주기가 없고, 그렇지 않을 경우 남아 있는 브리지가 없는 구성 요소에서 정기적인 주기가 발견될 수 있다.이 알고리즘의 브리지 반복 검색은 Thorup(2000)의 동적 그래프 알고리즘을 사용하여 효율적으로 수행될 수 있다.

일치의 맥락에서 유사한 교량 제거 기술은 가보우, 카플란 & 타르잔(1999년)에 의해 이전에 검토되었다.

만족도

2-만족성 문제의 예, 즉, 두 개의 변수나 각 절에 대한 변수의 부정이 있는 결합 정상 형태의 부울식 표현은 두 개의 함축적 의미$({\displaystyle }$ ${\displaystyle \mathrm{\neg }}$ ${\displaystyle u}$) ${\displaystyle \Rightarrow }$ v ${\displaystyle \{}$ v { v { v ${$ ${\displaystyle v}$ $v{\displaystyle }$ \ \ v \ \ \ v$$$\script$ $style$ $u$u u v {\\\lor v$}$을 대체함으로써 시사 그래프로 변형될 수 있다.$yle (\lnot u)\$${\displaystyle \mathrm{Rightarrow}}$ $v}$ 및$$${\displaystyle }$( ${\displaystyle \mathrm{\neg }}$ v${\displaystyle }$)${\displaystyle u}$ ${\$ v$)\Rightarrow u}$.이 그래프는 각 변수 또는 부정 변수에 대한 정점과 각 함축에 대한 방향 에지를 가지고 있다. 즉, 구성에 의해, 각 변수를 부정에 매핑하는 대응 σ을 갖는 것이다.Aspvall, Plass & Tarjan(1979)이 보여주었듯이, 2-만족성 인스턴스에 대한 만족스러운 할당은 이 시사 그래프를 S와 σ(S)의 두 부분 집합으로 분할하는 것과 동등하다. 즉, 에지가 S에서 시작되지 않고 σ(S)로 끝나는 것이다.그러한 파티션이 존재하는 경우, S의 모든 변수에 참 값을 할당하고 σ(S)의 모든 변수에 거짓 값을 할당함으로써 만족스러운 할당이 형성될 수 있다.이것은 그래프의 일부 정점 v와 그 보완 정점 σ(v) 모두를 포함하는 그래프의 강하게 연결된 구성요소가 없는 경우에만 수행될 수 있다.두 꼭지점이 동일한 강하게 연결된 구성요소에 속할 경우, 해당 변수 또는 부정 변수는 2만족도 인스턴스의 만족스러운 할당에서 서로 동일하도록 제약을 받는다.강력한 연결을 테스트하고 시사 그래프의 파티션을 찾기 위한 총 시간은 주어진 2-CNF 식 크기에서 선형이다.

인식

랄론드(1981)의 결과, 초당적 그래프에서 색반사 비자발성을 찾아내는 것이 NP 완성으로, 주어진 지시 그래프가 스큐 대칭인지 여부를 확인하는 것이 NP-완전이다.이러한 비자발성은 각 가장자리를 한 색상 등급에서 다른 색상 등급으로 방향 지정하여 주어진 방향 그래프가 스큐 대칭인 경우에만 존재하므로 이 방향 그래프의 스큐 대칭성을 시험하는 것은 어렵다.이러한 복잡성은 스큐 대칭 그래프의 경로 탐색 알고리즘에 영향을 미치지 않는데, 이 알고리즘들은 스큐 대칭 구조가 그래프에서만 유추하도록 요구하기 보다는 알고리즘에 대한 입력의 일부로 제공된다고 가정하기 때문이다.

메모들

참조

• Aspvall, Bengt; Plass, Michael F.; Tarjan, Robert E. (1979), "A linear-time algorithm for testing the truth of certain quantified boolean formulas", Information Processing Letters, 8 (3): 121–123, doi:10.1016/0020-0190(79)90002-4.
• Babenko, Maxim A. (2006), "Acyclic bidirected and skew-symmetric graphs: algorithms and structure", Computer Science – Theory and Applications, Lecture Notes in Computer Science, vol. 3967, Springer-Verlag, pp. 23–34, arXiv:math/0607547, doi:10.1007/11753728_6, ISBN 978-3-540-34166-6.
• Biggs, Norman (1974), Algebraic Graph Theory, London: Cambridge University Press.
• Cook, Matthew (2003), "Still life theory", New Constructions in Cellular Automata, Santa Fe Institute Studies in the Sciences of Complexity, Oxford University Press, pp. 93–118.
• 에드먼즈, 잭 존슨, 엘리스 L.(1970년),"Matching:선형적인 프로그램well-solved 클래스", 것이 Combinatorial구조물과 전자:캘거리 심포지엄 6월 1969년, 뉴욕:고든과 균열의 회보.조합 최적화 — 유레카에 Reprinted!,. 27–30, doi:10.1007/3-540-36478-1_3 Springer-Verlag, 강의 노트 컴퓨터 과학 2570,2003,를 대신하여 서명함 Shrink.
• Gabow, Harold N.; Kaplan, Haim; Tarjan, Robert E. (1999), "Unique maximum matching algorithms", Proc. 31st ACM Symp. Theory of Computing (STOC), pp. 70–78, doi:10.1145/301250.301273, ISBN 1-58113-067-8.
• Goldberg, Andrew V.; Karzanov, Alexander V. (1996), "Path problems in skew-symmetric graphs", Combinatorica, 16 (3): 353–382, doi:10.1007/BF01261321.
• Goldberg, Andrew V.; Karzanov, Alexander V. (2004), "Maximum skew-symmetric flows and matchings", Mathematical Programming, 100 (3): 537–568, arXiv:math/0304290, doi:10.1007/s10107-004-0505-z.
• Hui, Peter; Schaefer, Marcus; Štefankovič, Daniel (2004), "Train tracks and confluent drawings", Proc. 12th Int. Symp. Graph Drawing, Lecture Notes in Computer Science, vol. 3383, Springer-Verlag, pp. 318–328.
• Lalonde, François (1981), "Le problème d'étoiles pour graphes est NP-complet", Discrete Mathematics, 33 (3): 271–280, doi:10.1016/0012-365X(81)90271-5, MR 0602044.
• Thorup, Mikkel (2000), "Near-optimal fully-dynamic graph connectivity", Proc. 32nd ACM Symposium on Theory of Computing, pp. 343–350, doi:10.1145/335305.335345, ISBN 1-58113-184-4.
• Tutte, W. T. (1967), "Antisymmetrical digraphs", Canadian Journal of Mathematics, 19: 1101–1117, doi:10.4153/CJM-1967-101-8.
• Zaslavsky, Thomas (1982), "Signed graphs", Discrete Applied Mathematics, 4: 47–74, doi:10.1016/0166-218X(82)90033-6, hdl:10338.dmlcz/127957.
• Zaslavsky, Thomas (1991), "Orientation of signed graphs", European Journal of Combinatorics, 12 (4): 361–375, doi:10.1016/s0195-6698(13)80118-7.
• Zelinka, Bohdan (1974), "Polar graphs and railway traffic", Aplikace Matematiky, 19: 169–176.
• Zelinka, Bohdan (1976a), "Isomorphisms of polar and polarized graphs", Czechoslovak Mathematical Journal, 26: 339–351.
• Zelinka, Bohdan (1976b), "Analoga of Menger's theorem for polar and polarized graphs", Czechoslovak Mathematical Journal, 26: 352–360.