이 단원 목차
관계를 그래프로 나타내기
그래프 G=(V,E)는 정점과 간선으로 구조를 표현합니다. 방향 그래프의 간선 (u,v)는 u→v이며 반대 간선과 다릅니다. 실습은 V={0,1,2}, 자기 간선 없는 단순 방향 그래프입니다. 가능한 여섯 방향 간선을 비트로 켜고 끕니다.
bit 0,1,2,3,4,5는 각각 0→1,0→2,1→0,1→2,2→0,2→1입니다. 마스크 9=1+8이면 0→1→2라는 사슬입니다. 숫자 마스크의 차이가 그래프 사이의 의미 있는 거리를 나타내는 것은 아닙니다.
무방향 트리의 조건
유한 단순 무방향 그래프에서 트리는 연결되어 있고 순환이 없는 그래프입니다. n개 정점의 트리는 n−1개 간선을 가집니다. 연결된 그래프는 적어도 n−1개 간선이 필요하며, 순환 위의 간선을 제거해도 연결성이 유지됩니다. 이를 반복하면 연결 최소 구조인 트리가 남습니다.
따라서 연결과 간선 수 n−1을 함께 확인하면 트리임을 알 수 있습니다. 간선 수만 n−1이라고 충분하지는 않습니다. 네 정점 중 세 정점이 삼각형을 만들고 나머지 하나가 고립되면 간선은 세 개지만 트리가 아닙니다.
실습의 트리 표식은 방향을 지우고 왕복 간선을 하나로 합친 기저 단순 그래프에 적용됩니다. 방향 그래프 자체를 무방향 트리와 혼동하지 마세요.
DAG와 위상 순서
DAG는 방향 순환이 없는 방향 그래프입니다. 위상 순서는 모든 간선 u→v에서 u가 v보다 앞에 오는 정점의 나열입니다.
유한 DAG에는 진입차수 0인 정점이 적어도 하나 있습니다. 없다면 이전 정점을 계속 따라가다가 유한성 때문에 정점을 재방문하여 방향 순환이 생깁니다. 진입차수 0인 정점을 먼저 제거하고 남은 DAG에 같은 논증을 적용하면 위상 순서를 얻습니다.
반대로 위상 순서가 있으면 방향 순환은 불가능합니다. 순환을 따라 순서가 계속 엄격히 증가하다가 출발 정점으로 돌아와야 하기 때문입니다. 이로써 유한 그래프에서 다음 동치를 증명합니다.
트리와 DAG를 구분하는 반례
사슬 0→1→2는 DAG이고 기저 그래프도 트리입니다. 여기에 0→2를 더하면 여전히 DAG지만 기저 그래프는 삼각형이므로 트리가 아닙니다. 반대로 0↔1,1→2는 기저 그래프가 트리지만 방향 2-순환 때문에 DAG가 아닙니다.
모든 DAG가 트리인 것도, 기저 트리의 모든 방향 부여가 DAG인 것도 아닙니다. 다만 무방향 트리의 각 간선에 한 방향만 주면 방향 순환은 생기지 않습니다. 왕복 간선을 허용하는 실습에서는 이 추가 조건이 중요합니다.
위상 정렬을 직접 따라가기
- 모든 정점의 진입차수를 셉니다.
- 진입차수 0인 정점을 준비 목록에 넣습니다.
- 정점 하나를 꺼내 순서에 추가하고 나가는 간선을 제거합니다.
- 새로 진입차수가 0이 된 정점을 추가합니다.
- 전 정점을 출력하지 못하면 방향 순환이 남아 있습니다.
여러 정점이 동시에 준비되면 순서는 유일하지 않을 수 있습니다. 화면은 한 유효 순서만 보여 줍니다. —는 순환 때문에 완전한 위상 순서가 없다는 뜻입니다. 부분적으로 출력된 정점 목록을 완전한 순서처럼 제공하지 않습니다.
AI 계산 그래프의 의미
유한한 순전파 계산을 DAG로 표현하면 위상 순서대로 값을 계산할 수 있습니다. 역전파는 이 의존 관계를 거꾸로 따르며 공유 노드의 기여를 합칩니다. RNN의 모듈 그림은 순환을 갖지만 유한 단계로 펼친 계산 그래프는 DAG가 될 수 있습니다. 어떤 수준의 그래프를 말하는지 구분하세요.
그림의 노드 위치·간선 길이는 값이나 실행 시간을 나타내지 않습니다. 화살표와 간선 표를 기준으로 읽으세요.
정렬 비용과 결과 검증
인접 리스트를 쓰면 진입차수를 한 번 계산하고 각 정점과 간선을 한 번씩 처리하므로 Kahn 알고리즘은 O(|V|+|E|) 시간입니다. 매번 전체 인접행렬을 다시 훑는 구현은 같은 비용이 아닙니다. 결과 목록이 정점 전부를 정확히 한 번 포함하고 모든 간선 u→v에서 위치(u)<위치(v)인지 검사하면 위상 순서의 유효성을 독립적으로 검증할 수 있습니다.
유효 순서를 찾는 문제와 가능한 모든 순서를 세는 문제는 다릅니다. 0→2와 1→2만 있으면 (0,1,2)와 (1,0,2)가 모두 가능합니다. 하나의 출력 순서는 다른 순서가 없다는 증거가 아닙니다. 화면의 수치 표를 읽을 때 알고리즘이 선택한 순서와 그래프가 강제한 순서를 구분하세요.
확인 문제와 답
- 마스크 11의 기저 그래프와 방향 그래프는? 무방향 삼각형이며 DAG입니다.
- 마스크 13은? 기저 트리이나 방향 순환이 있습니다.
- 위상 순서가 하나라면 진입차수 0인 후보가 매 단계 몇 개였을까요? 매 단계 하나입니다.
추가 읽기: MIT Mathematics for Computer Science. 실습의 세 정점 완전 열거는 일반 동치의 증명과 별도입니다.
설명할 수 있나요?
실험 설정과 무관한 기준 예제를 묻습니다. 답을 고르고 설명을 확인해보세요.
선택한 답과 학습 표시는 이 브라우저에 저장됩니다. 다시 풀거나 표시를 해제할 수 있습니다.