분야
zip관련연구
추이적 폐쇄 알고리즘
바르샬 알고리즘
정의
예제
비교
알고리즘의 확장 및 응용
결론
그래프에서 모든 꼭지점 사이의 경로의 존재
도달가능행렬을 찾는 문제
가정(제약)
인접행렬로 표현된 유향 그래프
가중치가 없는 경로 (연결 혹은 비연결)
관련연구 – 추이적 폐쇄
이산수학 “제3장 관계와 함수”의 추이관계를 생각해 봅시다.
추이관계
모든 x,y,x∈A에 대하여, xRy and yRz ⇒ xRz
그래프의 경로는 두 꼭지점간의 관계를 나타내는 순서쌍으로 표현할 수 있다.
관련연구 – 추이적 폐쇄(계속)
추이관계 = 꼭지점을 거쳐서 갈 수 있는 경로
결국 도달 가능한 모든 경로를 찾는 문제는 길이가 1인 경로부터 최대의 경로까지의 경로를 모두 찾으면 된다.
길이가 1인 경로 = 꼭지점과 꼭지점 직접연결
길이가 2인 경로 = 사이에 중간 꼭지점이 1개
길이가 n인 경로 = 사이에 거쳐야 하는 꼭지점이 n-1 n개의 꼭지점을 가지는 그래프의 최대 경로 : 하나의 사이클인 경우
test_data.exe
warshall.c
warshall.exe
