양방향 그래프
Bidirected graph
그래프 이론의 수학적 영역에서, 양방향 그래프(Edmonds & Johnson 1970에 소개됨)[1]는 각 가장자리의 각 끝에 독립적인 방향(또는 방향 또는 화살표)이 주어지는 그래프다.따라서, 세 가지 방향 가장자리가 있다: 화살표가 바깥쪽을 향하고, 정점을 향해, 양쪽 끝에서 정점을 향해, 안쪽으로 향하며, 양쪽 화살표가 정점을 벗어나고, 반대쪽 끝에서 한 화살표가 정점을 향하고, 다른 화살표가 첫 번째 화살표와 같은 방향을 가리키고, 다른 화살표가 정점을 벗어나고 있다.그는 반대쪽 끝과 정점을 향해 있다.
이 세 가지 유형의 가장자리는 각각 외향적, 내향적 및 지시적이라 불릴 수 있다."방향" 가장자리는 지시된 그래프에서 일반 방향 가장자리와 동일하므로 지시된 그래프는 특별한 종류의 간접 그래프다.
때때로 한쪽 끝(반쪽 끝)만 있는 가장자리를 갖는 것이 바람직하다. 가장자리는 한 개의 화살표만 받는다.끝이 없는 가장자리(느슨한 가장자리)에는 화살표가 없다.반이나 느슨한 가장자리가 아닌 가장자리를 보통 가장자리라고 할 수 있다.
스큐 대칭 그래프는 양방향 그래프의 이중 커버 그래프다.
기타의미
대칭 방향 그래프(즉, 모든 가장자리의 역이 역시 가장자리인 방향 그래프)를 "비디렉티드 그래프"[2]라고도 한다.
참고 항목
참조
- ^ 에드먼즈, 잭 존슨, 엘리스 L.(1970년),"Matching:선형적인 프로그램well-solved 클래스", 것이 Combinatorial구조물과 전자:캘거리 심포지엄 6월 1969년, 뉴욕:고든과 균열의 회보.조합 최적화 — 유레카에 Reprinted!,. 27–30, doi:10.1007/3-540-36478-1_3 Springer-Verlag, 강의 노트 컴퓨터 과학 2570,2003,를 대신하여 서명함 Shrink.
- ^ Mehlhorn, Kurt; Sanders, Peter (2008), Algorithms and Data Structures: The Basic Toolbox, Springer Science & Business Media, pp. 49 and 170–171, ISBN 978-3-540-77978-0
.svg){kind=small}
