방향(그래프 이론)

Orientation (graph theory)

그래프 이론에서, 방향성이 없는 그래프의 방향은 각 가장자리에 방향을 할당하여 초기 그래프를 방향 그래프로 바꾸는 것이다.

방향 그래프

방향 그래프는 정점 쌍 중 어느 것도 두 개의 대칭 에지로 연결되지 않으면 방향 그래프라고 불린다.지시된 그래프 중에서 방향 그래프는 2 사이클이 없는 그래프(대부분 (x, y)와 (y, x) 중 하나일 수 있음)[1]이다.

토너먼트는 완전한 그래프의 방향이다.폴리 트리는 방향을 잡지 않은 나무의 방향이다.[2]섬너의 추측에 따르면 2n - 2정점을 가진 모든 토너먼트에는 정점을 가진 모든 폴리 트리가 포함되어 있다.[3]

정점이 n인 비이형 중심 그래프의 수(n = 1, 2, 3, …)는 다음과 같다.

1, 2, 7, 42, 582, 21480, 2142288, 575016219, 415939243032, … (OEIS의 경우 시퀀스 A001174).

토너먼트는 완전한 방향 그래프(각각 정점 쌍 사이에 한 방향 또는 양 방향에서 지시된 가장자리가 있는 그래프)와 일대일 일치한다.완전한 방향 그래프는 매 2 사이클을 제거하여 방향 그래프로 변환할 수 있으며, 반대로 방향 그래프는 에지의 끝점이 아닌 모든 정점 쌍 사이에 2 사이클을 추가함으로써 완전한 방향 그래프로 변환할 수 있다. 이러한 대응은 주관적이다.따라서 같은 수의 순서는 완전한 디그그래프에 대한 그래프 열거 문제도 해결한다.이 순서에는 숫자에 대한 명시적이기는 하지만 복잡한 공식이 있다.[4]

제한된 방향

강한 방향은 강하게 연결된 그래프를 만드는 방향이다.밀접하게 연관된 완전 주기 방향은 모든 가장자리가 적어도 하나의 단순한 주기에 속하는 방향이다.비방향 그래프 G의 방향은 G. 로빈스의 정리의 모든 연결된 구성요소의 강한 방향일 경우에만 그래프가 2-엣지 연결되었을 경우에만 강한 방향을 갖는다고 명시하는 경우 그리고 오직 분리된 그래프는 완전한 주기적 방향을 가질 수 있지만, 다리가 없는 경우에만 그렇다.[5]

반복 방향은 지시된 반복 그래프를 생성하는 방향이다.모든 그래프는 반복적인 방향을 가지고 있다. 모든 반복 방향은 정점을 시퀀스로 배치한 다음 시퀀스의 초기 끝점에서 후기 끝점으로 각 가장자리를 지시함으로써 얻을 수 있다.갈라이-하세-로이-비타버 정리는 그래프가 최대 k 색상으로 색칠할 수 있는 경우에만 가장 긴 경로가 최대 k 정점을 갖는 Acyclic 방향을 가지고 있다고 명시한다.[6]주기적 방향과 완전히 주기적인 방향은 평면적 이중성에 의해 서로 연관되어 있다.단일 선원과 단일 싱크대를 가진 순환 방향을 양극 방향이라고 한다.[7]

타전 방향은 결과 방향 그래프가 자체 타전적 폐쇄가 되는 방향이다.전이적 방향이 있는 그래프를 비교가능성 그래프라고 부른다. 비교가능성 그래프는 두 요소가 부분적인 순서로 비교될 때마다 인접하게 만들어 부분 순서 집합에서 정의할 수 있다.[8]전이 방향(transitive orientation)이 존재하는 경우 선형 시간에서 찾을 수 있다.[9]그러나 결과 방향(또는 주어진 방향)이 실제로 전이적인지 여부를 시험하는 것은 매트릭스 곱셈과 복잡성이 동일하기 때문에 더 많은 시간이 필요하다.

방향 지시되지 않은 그래프의 오일러 방향은 각 꼭지점이 도수와 도수가 동일한 방향이다.그리드 그래프의 오일러 방향은 얼음형 모델 이론의 통계적 역학에서 발생한다.[10]

Pafeian 방향은 그래프의 특정 짝수 길이 사이클이 사이클 주기의 두 방향 각각에 방향의 홀수 수를 갖는 특성을 가지고 있다.그것들은 항상 평면 그래프를 위해 존재하지만, 특정한 다른 그래프들을 위해서 존재하지는 않는다.그것들은 FKT 알고리즘에서 완벽한 짝을 세는 데 사용된다.[11]

참고 항목

참조

  1. ^ Diestel, Reinhard (2005), "1.10 Other notions of graphs", Graph Theory (PDF) (3rd ed.), Springer, ISBN 978-3-540-26182-7.
  2. ^ Rebane, George; Pearl, Judea (1987), "The recovery of causal poly-trees from statistical data", Proc. 3rd Annual Conference on Uncertainty in Artificial Intelligence (UAI 1987), Seattle, WA, USA, July 1987, pp. 222–228, arXiv:1304.2736.
  3. ^ 섬너의 유니버설 토너먼트 추측, 더글라스 B.웨스트, 2012-08-02를 회수했다.
  4. ^ Harary, Frank; Palmer, Edgar M. (1973), "Formula 5.4.13", Graphical Enumeration, New York: Academic Press, p. 133, MR 0357214.
  5. ^ Robbins, H. E. (1939), "A theorem on graphs, with an application to a problem of traffic control", The American Mathematical Monthly, 46 (5): 281–283, doi:10.2307/2303897, hdl:10338.dmlcz/101517, JSTOR 2303897.
  6. ^ Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), "Theorem 3.13", Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, vol. 28, Heidelberg: Springer, p. 42, doi:10.1007/978-3-642-27875-4, hdl:10338.dmlcz/143192, ISBN 978-3-642-27874-7, MR 2920058.
  7. ^ de Fraysseix, Hubert; Ossona de Mendez, Patrice; Rosenstiehl, Pierre (1995), "Bipolar orientations revisited", Discrete Applied Mathematics, 56 (2–3): 157–179, doi:10.1016/0166-218X(94)00085-R, MR 1318743.
  8. ^ Ghouila-Houri, Alain (1962), "Caractérisation des graphes non orientés dont on peut orienter les arrêtes de manière à obtenir le graphe d'une relation d'ordre", Les Comptes rendus de l'Académie des sciences, 254: 1370–1371, MR 0172275.
  9. ^ McConnell, R. M.; Spinrad, J. (1997), "Linear-time transitive orientation", 8th ACM-SIAM Symposium on Discrete Algorithms, pp. 19–25.
  10. ^ Mihail, M.; Winkler, P. (1996), "On the number of Eulerian orientations of a graph", Algorithmica, 16 (4–5): 402–414, doi:10.1007/s004539900057, MR 1407581.
  11. ^ Thomas, Robin (2006), "A survey of Pfaffian orientations of graphs" (PDF), International Congress of Mathematicians. Vol. III, Eur. Math. Soc., Zürich, pp. 963–984, doi:10.4171/022-3/47, ISBN 978-3-03719-022-7, MR 2275714

외부 링크