루트 그래프

Rooted graph

수학, 특히 그래프 이론에서 뿌리 그래프는 하나의 꼭지점이 뿌리로 구분된 그래프다.[1][2]루트 그래프의 지시된 버전과 리디렉션되지 않은 버전 모두 연구되었고, 여러 루트를 허용하는 변형 정의도 있다.

루트 그래프는 포인트 그래프 또는 흐름 그래프로도 알려져 있다(적용에 따라).이러한 그래프의 일부 적용에서는 전체 그래프가 루트 꼭지점에서 도달할 수 있어야 한다는 추가 요건이 있다.

변형

위상 그래프 이론에서, 뿌리 그래프의 개념은 여러 정점이나 다중 가장자리를 루트로 간주하기 위해 확장될 수 있다.전자를 이 맥락에서 가장자리에 뿌리를 둔 그래프와 구별하기 위해 정점근 그래프라고 부르기도 한다.[3]루트로 지정된 여러 노드가 있는 그래프는 무작위 그래프 영역에서도 조합에 어느 정도 관심이 있다.[4]이러한 그래프를 곱셈뿌리 그래프라고도 한다.[5]

root directed graph 또는 root digraph라는 용어는 또한 정의의 변화를 본다.분명한 이식은 특정 노드를 루트로 식별하여 뿌리를 내린 디그람을 고려하는 것이다.[6][7]그러나 컴퓨터 과학에서 이러한 용어는 일반적으로 좁은 개념을 가리키는데, 즉, 뿌리 방향 그래프는 r에서 r 이외의 노드로 향하는 방향 경로가 있을 정도로 노드가 구별되는 digraph이다.[8][9][10][11]좀 더 일반적인 정의를 제시하는 저자는 이를 연결된 뿌리가 있는 [6]디그라프 또는 접근 가능한 뿌리가 있는 그래프로 나타낼 수 있다(§ 세트 이론 참조).

컴퓨터 프로그래밍 기술은 뿌리가 있는 디그그래프를 조금 더 넓게 정의하는데, 즉 지시된 그래프는 다른 모든 노드에 도달할 수 있는 최소한 하나의 노드가 있으면 뿌리를 내린다고 한다; 크누스는 이렇게 정의한 개념이 강하게 연결된 디그그래프의 개념과 연결된 디그그래프의 개념들 사이의 일종의 중간이라고 언급한다.[12]

적용들

흐름 그래프

컴퓨터 과학에서는 뿌리가 다른 모든 정점에 도달할 수 있는 뿌리 그래프를 흐름 그래프 또는 흐름 그래프라고 부른다.[13]때로는 흐름 그래프에 단일 출구(싱크) 꼭지점이 있어야 한다는 추가적인 제한이 추가되기도 한다.[14]

흐름 그래프는 비구조적 요소(노드 내용 및 유형)가 제거된 상태로 흐름도의 추상화라고 볼 수 있다.[15][16]아마도 흐름 그래프의 가장 잘 알려진 하위 등급은 컴파일러와 프로그램 분석에 사용되는 제어 흐름 그래프일 것이다.임의의 흐름 그래프는 그 근원에서 유일한 송신 에지이고 그 목표물로 들어오는 유일한 에지인 모든 에지에서 에지 축소를 수행함으로써 제어 흐름 그래프로 변환될 수 있다.[17]일반적으로 사용되는 또 다른 유형의 흐름 그래프는 노드가 전체 서브루틴에 해당하는 통화 그래프다.[18]

flow graph의 일반적인 개념은 프로그램 graph라고 불렸으나,[19] 같은 용어가 control-flow graph만을 나타내는 데 사용되기도 했다.[20]플로우 그래프는 라벨이 없는 플로우그래프,[21] 적절한 플로우그래프라고도 불린다.[15]이러한 그래프는 소프트웨어 테스트에 가끔 사용된다.[15][18]

단일 출구가 필요한 경우 흐름 그래프에는 일반적으로 지시된 그래프와 공유되지 않는 두 가지 속성이 있다.흐름 그래프는 서브루틴 호출에 해당하는 내포될 수 있으며(통과 파라미터의 개념은 없지만), 흐름 그래프도 시퀀싱할 수 있으며, 이는 코드 두 조각의 순차 실행과 동일하다.[22]prime flow graph는 예를 들어 구조화된 프로그래밍의 원시 요소와 같이 선택된 서브그래프 패턴을 사용하여 내포나 시퀀싱을 통해 분해될 수 없는 흐름 그래프로 정의된다.[23]예를 들어, 선택된 그래프 세트가 주어진 주요 흐름 그래프의 비율을 결정하는 이론 연구가 수행되었다.[24]

세트 이론

Peter Aczel은 모든 노드가 (접근 가능한 뾰족한 그래프라고 부르는) 루트로부터 도달할 수 있도록 뿌리내린 그래프를 사용하여 근거 없는 집합 이론에서 Aczel의 반창고 공리를 공식화했다.이 맥락에서 접근 가능한 뾰족한 그래프의 각 꼭지점은 Aczel의 (근거가 없는) 집합 이론 내에서 설정된 (근거가 없는) a를 모델화하고, 꼭지점 v에서 꼭지점 w 모델까지 v가 w의 요소인 호를 모델화한다.Aczel의 반창고 공리는 모든 접근 가능한 뾰족한 그래프는 이러한 방식으로 (근거가 제대로 없는) 한 집단을 모형화한다고 말한다.[25]

콤비네이터 게임 이론

순전히 콤비네이터적인 게임이 주어지면, 정점이 게임 위치이고 가장자리가 움직이는 연관 루트 디렉티드 그래프가 있으며, 루트부터 시작되는 그래프 트래버설이 게임 트리를 만드는 데 사용된다.그래프에 지시된 사이클이 포함되어 있다면 게임 내 포지션은 무한히 여러 번 반복될 수 있으며, 일반적으로 게임이 무한정 지속되는 것을 막기 위한 규칙이 필요하다.그렇지 않으면 이 그래프는 지시된 악순환 그래프인데, 만약 그것이 뿌리깊은 나무가 아니라면, 그 게임은 전이가 되는 것이다.이 그래프와 그 위상은 게임 복잡성의 연구에서 중요한데, 여기서 상태 공간 복잡성은 그래프에서 정점의 수이고, 평균 게임 길이는 직접 후계자가 없는 정점의 수이며, 게임 트리의 평균 분기 계수는 g의 평균 초과 도이다.랩을 하다

콤비네이터 열거

1, 2, ... 노드에 대한 루트 비방향 그래프 수는 1, 2, 6, 20, 90, 544, ...(OEIS에서 시퀀스 A000666)이다.

관련개념

특별한 관심사로는 뿌리가 있는 나무, 뿌리가 뚜렷한 나무들이 있다.뿌리가 뿌리가 뿌리가 내린 방향 경로가 추가로 고유하도록 제한된다면, 그 개념은 뿌리 나무와 동등한 방향 그래프인 (뿌리) 수목의 개념이다.[7]루트 그래프는 전체 그래프가 루트로부터 도달할 수 있는 경우에만 동일한 루트의 목차를 포함하며, 컴퓨터 과학자들은 최적의 목차를 찾는 알고리즘 문제를 연구해왔다.[26]

루트 그래프는 그래프의 루트 산출물을 사용하여 결합할 수 있다.[27]

참고 항목

참조

  1. ^ Zwillinger, Daniel (2011), CRC Standard Mathematical Tables and Formulae, 32nd Edition, CRC Press, p. 150, ISBN 978-1-4398-3550-0
  2. ^ 454페이지를 보라Harary, Frank (1955), "The number of linear, directed, rooted, and connected graphs", Transactions of the American Mathematical Society, 78 (2): 445–463, doi:10.1090/S0002-9947-1955-0068198-2, MR 0068198.
  3. ^ Gross, Jonathan L.; Yellen, Jay; Zhang, Ping (2013), Handbook of Graph Theory (2nd ed.), CRC Press, pp. 764–765, ISBN 978-1-4398-8018-0
  4. ^ Spencer, Joel (2001), The Strange Logic of Random Graphs, Springer Science & Business Media, chapter 4, ISBN 978-3-540-41654-8
  5. ^ 하라리(1955, 페이지 455).
  6. ^ a b Björner, 안데르스, Ziegler귄터 M.(1992년),"greedoids에 8. 소개"(PDF), 화이트에, 닐(교육.), Matroid 응용, 백과 사전 수학과 그 응용의 40vol., 캠브리지:.만약 뿌리부터 모든 꼭지점에 통제된 길은 캠브리지 대학 출판부를 대신하여 서명함. 284–357, doi:10.1017/CBO9780511662041.009, 아이 에스비엔 0-521-38165-7, MR1165537, Zbl 0772.05026, 이런 맥락에서 뿌리 깊은 이중자 안 Δ)(V,E,r)연결되어(또는 1-connected)라고 불린다.특정 페이지의 주 307을 보세요.
  7. ^ a b Gordon, Gary; McMahon, Elizabeth (February 1989), "A greedoid polynomial which distinguishes rooted arborescences" (PDF), Proceedings of the American Mathematical Society, 107 (2): 287, CiteSeerX 10.1.1.308.2526, doi:10.1090/s0002-9939-1989-0967486-0, A rooted subdigraph F is a rooted arborescence if the root vertex ∗ is in F and, for every vertex v in F, there is a unique directed path in F from ∗ to v. Thus, rooted arborescences in digraphs correspond to rooted trees in undirected graphs.
  8. ^ 라마 찬드란, Vijaya(1988년)," 빠른 병렬 알고리즘 Reducible 유동 Graphs에", 동시 Computations:117–138, doi:10.1007/978-1-4684-5511-3_8, 아이 에스비엔 978-1-4684-5513-7, 한 뿌리 깊은 직접적인 그래프나 흐름 그래프 G=저명한 꼭지점 r이 G장조 r에서 V−의 모든 꼭지점 v에 통제된 경로에(V, A, r)은 통제된 그래프이다.r. 있습니다. 특정p. 122을 보세요.
  9. ^ 오카모토, 요시오, 나카무라, Masataka(2003년),"뿌리 깊은 digraphs의line-search antimatroids의 금지된 사소한 특성화"(PDF), 이산화 응용 수학, 131(2):523–533, doi:10.1016(02)00471-7, 한 뿌리 깊은 이중자 안은 트리플 G=(V,E,r)이(V∪{r}, E)은 이중자 안과 r은 지정된 꼭지점이라 불리는 두 뿌리가 씨푸드.Er에서 V의 모든 꼭지점에 경로의 존재.특정 페이지의 주 524을 보세요.
  10. ^ Jain, Abhinandan (2010), Robot and Multibody Dynamics: Analysis and Algorithms, Springer Science & Business Media, p. 136, ISBN 978-1-4419-7267-5, A rooted digraph is a connected digraph with a single root node that is the ancestor of every other node in the digraph.
  11. ^ 첸 Xujin(2004년),"효율적인 알고리즘 찾기 위해 최대 사이클 Packings Reducible에 Graphs"(PDF), 강의 노트 컴퓨터 과학으로, 3341:306–317, CiteSeerX 10.1.1.894.5261, doi:10.1007/978-3-540-30551-4_28, hdl:10722/48600, 아이 에스비엔 978-3-540-24131-7, 한 뿌리 깊은 직접적인 그래프나 흐름 그래프는digraph G는 저명한 꼭지점 r,. 자신의 뿌리가 G장조 r에서 G의 모든 꼭지점의 길은 호출됩니다.
  12. ^ Knuth, Donald (1997), "2.3.4.2. Oriented trees", The Art of Computer Programming, vol. 1 (3rd ed.), Pearson Education, p. 372, ISBN 0-201-89683-4, It is said to be rooted if there is at least one root, that is, at least one vertex R such that there is an oriented path from V to R for all V ≠ R.
  13. ^ 그로스, 옐런 & 장 (2013, 페이지 1372).
  14. ^ Fenton, Norman Elliott; Hill, Gillian A. (1993), Systems Construction and Analysis: A Mathematical and Logical Framework, McGraw-Hill, p. 319, ISBN 978-0-07-707431-9.
  15. ^ a b c Zuse, Horst (1998), A Framework of Software Measurement, Walter de Gruyter, pp. 32–33, ISBN 978-3-11-080730-1
  16. ^ Samaroo, Angelina; Thompson, Geoff; Williams, Peter (2010), Software Testing: An ISTQB-ISEB Foundation Guide, BCS, The Chartered Institute, p. 108, ISBN 978-1-906124-76-2
  17. ^ Tarr, Peri L.; Wolf, Alexander L. (2011), Engineering of Software: The Continuing Contributions of Leon J. Osterweil, Springer Science & Business Media, p. 58, ISBN 978-3-642-19823-6
  18. ^ a b Jalote, Pankaj (1997), An Integrated Approach to Software Engineering, Springer Science & Business Media, p. 372, ISBN 978-0-387-94899-7
  19. ^ Thulasiraman, K.; Swamy, M. N. S. (1992), Graphs: Theory and Algorithms, John Wiley & Sons, p. 361, ISBN 978-0-471-51356-8
  20. ^ Cechich, Alejandra; Piattini, Mario; Vallecillo, Antonio (2003), Component-Based Software Quality: Methods and Techniques, Springer Science & Business Media, p. 105, ISBN 978-3-540-40503-0
  21. ^ Beineke, Lowell W.; Wilson, Robin J. (1997), Graph Connections: Relationships Between Graph Theory and Other Areas of Mathematics, Clarendon Press, p. 237, ISBN 978-0-19-851497-8
  22. ^ 펜튼 앤 힐(1993, 페이지 323).
  23. ^ 펜튼 앤 힐(1993, 페이지 339).
  24. ^ Cooper, C. (2008), "Asymptotic Enumeration of Predicate-Junction Flowgraphs", Combinatorics, Probability and Computing, 5 (3): 215–226, doi:10.1017/S0963548300001991
  25. ^ Aczel, Peter (1988), Non-well-founded sets (PDF), CSLI Lecture Notes, vol. 14, Stanford, CA: Stanford University, Center for the Study of Language and Information, ISBN 0-937073-22-9, LCCN 87-17857, MR 0940014, archived from the original (PDF) on 2015-03-26
  26. ^ Drescher, Matthew; Vetta, Adrian (2010), "An Approximation Algorithm for the Maximum Leaf Spanning Arborescence Problem", ACM Trans. Algorithms, 6 (3): 46:1–46:18, doi:10.1145/1798596.1798599, S2CID 13987985.
  27. ^ Godsil, C. D.; McKay, B. D. (1978), "A new graph product and its spectrum" (PDF), Bull. Austral. Math. Soc., 18 (1): 21–28, doi:10.1017/S0004972700007760, MR 0494910

추가 읽기

  • McMahon, Elizabeth W. (1993), "On the greedoid polynomial for rooted graphs and rooted digraphs", Journal of Graph Theory, 17 (3): 433–442, doi:10.1002/jgt.3190170316
  • Gordon, Gary (2001), "A characteristic polynomial for rooted graphs and rooted digraphs", Discrete Mathematics, 232 (1–3): 19–33, doi:10.1016/S0012-365X(00)00186-2

외부 링크