로빈스의 정리
Robbins' theorem그래프 이론에서, 허버트 로빈스(1939년)의 이름을 딴 로빈스의 정리에서는 방향성이 강한 그래프는 정확히 2개의 가장자리로 연결된 그래프라고 기술하고 있다.즉, G가 연결되어 있고 브리지가 없는 경우에만 모든 꼭지점에서 다른 모든 꼭지점까지의 경로를 갖는 방향 그래프로 전환하여 비방향 그래프 G의 각 가장자리에 대한 방향을 선택할 수 있다.
방향성 그래프
로빈스가 강한 방향성을 가진 그래프의 특성화는 이 작업을 위해 로빈스에 의해 도입된 도구인 귀 분해를 사용하여 증명될 수 있다.
그래프가 브리지가 있는 경우 브리지에 대해 어떤 방향을 선택하든 간에 브리지의 두 끝점 중 하나에서 다른 쪽 끝까지의 경로가 없을 것이다.
다른 방향에서, 모든 연결된 브리지리스 그래프는 강한 방향을 가질 수 있다는 것을 보여줄 필요가 있다.로빈스가 증명했듯이, 그러한 모든 그래프에는 "ears"라고 불리는 일련의 하위 그래프에 칸막이가 있는데, 이 그래프에서 첫 번째 하위 그래프는 사이클이고 각각의 후속 하위 그래프는 하나의 경로로, 두 경로 끝점은 모두 그 시퀀스의 이전 귀에 속한다.(두 경로 끝점이 같을 수 있으며, 이 경우 하위 그래프는 주기일 수 있다.)각 귀 내 가장자리의 방향을 지정하여 방향 사이클 또는 방향 경로를 형성하도록 하면 전체 그래프의 방향이 강하게 연결된다.[1]
관련결과
로빈스의 정리의 엇갈린 그래프에 보쉬 사장 및에 의해 연장, Tindell(1980년)만약 G는 그래프에 따르면, 일부 모서리와 다른 사람들 지도자 없는, G는 경로마다 다른 꼭지점에 모든 꼭지점에서 서서히 가장자리 방향을 존중한다는 G 아닌 다리를 연출한 changin지 않아도 될 수 있다는 것이다 어떤 지도자 없는 가장자리가 들어 있게 될 보여 준다.g흙G의 연결성특히 브리지리스(bridgeless) 비방향 그래프는 모든 꼭지점 쌍 사이의 경로의 존재를 보존하면서 한 번에 하나씩 가장자리를 지시하는 탐욕스러운 알고리즘에 의해 강하게 연결된 그래프로 만들어질 수 있는데, 그러한 알고리즘이 추가적인 방향 결정이 이루어지지 않는 상황에 고착되는 것은 불가능하다.
알고리즘 및 복잡성
주어진 브리지리스(bridgeless) 비방향 그래프의 강한 방향은 그래프의 깊이 첫 번째 검색을 수행하고, 깊이 첫 번째 검색 트리의 모든 가장자리를 트리 루트로부터 멀리 향하게 하고, 나머지 가장자리(심도 첫 번째 검색 트리에서 반드시 조상 및 후손을 연결해야 함)를 모든 가장자리에서 방향을 지정함으로써 선형 시간 내에 찾을 수 있다.그는 조상의 자손이다.[2]이 알고리즘은 병렬 컴퓨터에 적합하지 않지만, 깊이 우선 검색을 수행하기 어렵기 때문에 병렬 모델에서 문제를 효율적으로 해결하는 대체 알고리즘을 이용할 수 있다.[3]병렬 알고리즘은 혼합 그래프의 강하게 연결된 방향을 찾는 것으로도 알려져 있다.[4]
적용들
로빈스는 원래 도시의 일방통행 도로 설계에 응용함으로써 그의 작업에 동기를 부여했다.또 다른 적용은 그리드 브레이싱 이론의 구조적 강성에 발생한다.이 이론은 유연한 관절에 부착된 강체 봉으로 만들어진 사각 격자를 그리드의 대각선에 교차 브레이싱으로 더 많은 로드나 와이어를 추가하여 견고하게 만드는 문제를 다룬다.추가된 로드 세트는 관련 비방향 그래프가 연결되면 그리드를 견고하게 만들고, 브리지가 없는 경우 이중 브레이싱(가장자리를 제거하면 강성이 유지됨)한다.이와 유사하게, 연결된 지점 사이의 거리를 줄이기 위해 구부릴 수 있지만 확장할 수 없는 추가 와이어 집합은 관련 방향 그래프가 강하게 연결되면 그리드를 단단하게 만든다.[5]따라서 이 용도에 대한 로빈스의 정리를 재해석하여, 이중 브레이스 구조물은 정확히 단단하게 유지된 채 전선으로 로드를 교체할 수 있는 구조물이다.
메모들
- ^ 그로스 & 옐런(2006년).
- ^ 비슈킨(1985)은 이 관찰을 아탈라(1984년)에게, 발라크리슈난(1996)은 로버츠(1978년)에게 인정한다.그러나 Clark & Holton(1991)이 지적하는 바와 같이, 깊이 첫 번째 검색에 관한 Hopcroft & Tarjan(1973)의 초기 정론적인 작업에 (2-edge-connectivity가 아닌 2-vertex-connectivity를 가정하여) 같은 알고리즘이 이미 포함되어 있다.
- ^ 비슈킨(1985)
- ^ 소로커(1988)
- ^ 바글리보 & 그리버(1983년).
참조
- Atallah, Mikhail J. (1984), "Parallel strong orientation of an undirected graph", Information Processing Letters, 18 (1): 37–39, doi:10.1016/0020-0190(84)90072-3, MR 0742079.
- Baglivo, Jenny A.; Graver, Jack E. (1983), "3.10 Bracing structures", Incidence and Symmetry in Design and Architecture, Cambridge Urban and Architectural Studies, Cambridge, UK: Cambridge University Press, pp. 76–87, ISBN 9780521297844
- Balakrishnan, V. K. (1996), "4.6 Strong Orientation of Graphs", Introductory Discrete Mathematics, Mineola, NY: Dover Publications Inc., p. 135, ISBN 978-0-486-69115-2, MR 1402469.
- Boesch, Frank; Tindell, Ralph (1980), "Robbins's theorem for mixed multigraphs", The American Mathematical Monthly, 87 (9): 716–719, doi:10.2307/2321858, JSTOR 2321858, MR 0602828.
- Clark, John; Holton, Derek Allan (1991), "7.4 Traffic Flow", A first look at graph theory, Teaneck, NJ: World Scientific Publishing Co. Inc., pp. 254–260, ISBN 978-981-02-0489-1, MR 1119781.
- Gross, Jonathan L.; Yellen, Jay (2006), "Characterization of strongly orientable graphs", Graph Theory and its Applications, Discrete Mathematics and its Applications (2nd ed.), Boca Raton, FL: Chapman & Hall/CRC, pp. 498–499, ISBN 978-1-58488-505-4, MR 2181153.
- Hopcroft, John; Tarjan, Robert (1973), "Algorithm 447: efficient algorithms for graph manipulation", Communications of the ACM, 16 (6): 372–378, doi:10.1145/362248.362272, S2CID 14772567.
- Robbins, H. E. (1939), "A theorem on graphs, with an application to a problem on traffic control", American Mathematical Monthly, 46 (5): 281–283, doi:10.2307/2303897, JSTOR 2303897.
- Roberts, Fred S. (1978), "Chapter 2. The One-Way Street Problem", Graph Theory and its Applications to Problems of Society, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 29, Philadelphia, Pa.: Society for Industrial and Applied Mathematics (SIAM), pp. 7–14, ISBN 9780898710267, MR 0508050.
- Soroker, Danny (1988), "Fast parallel strong orientation of mixed graphs and related augmentation problems", Journal of Algorithms, 9 (2): 205–223, doi:10.1016/0196-6774(88)90038-7, MR 0936106.
- Vishkin, Uzi (1985), "On efficient parallel strong orientation", Information Processing Letters, 20 (5): 235–240, doi:10.1016/0020-0190(85)90025-0, MR 0801988.
