다음 그래프에 대한 설명 중 옳은 것만을 모두 고르면?ㄱ. 가장 긴 단… | [7급 국가직 자료구조론] 24년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 24년 1회차
다음 그래프에 대한 설명 중 옳은 것만을 모두 고르면?ㄱ. 가장 긴 단순 경로의 길이는 4이다.
ㄴ. 진입차수가 진출차수보다 큰 정점은 1개이다.
ㄷ. 완전 그래프가 되기 위해 추가로 필요한 간선의 수는 10개이다.
ㄹ. 간선 <A, B>를 제거한 후 위상정렬을 수행하면 B, D, A, E, C, F 또는 B, D, A, C, E, F순으로 정점이 나열된다.
1
ㄱ, ㄹ
2
ㄴ, ㄷ
3
ㄱ, ㄴ, ㄹ
4
ㄴ, ㄷ, ㄹ
해설
옳은 것은 ㄱ, ㄹ이다.
그래프의 간선은 A→B, A→C, A→E, B→D, D→A, D→E, D→F, C→F, E→F의 9개이다.
- ㄱ(옳음): B→D→A→E→F처럼 길이 4인 단순 경로가 있다. C와 E는 모두 F로만 나가므로 두 정점을 한 경로에 함께 담을 수 없어 길이 5(정점 6개)는 불가능하다.
- ㄴ(틀림): 진입차수가 진출차수보다 큰 정점은 E(진입 2, 진출 1)와 F(진입 3, 진출 0)의 2개이다.
- ㄷ(틀림): 정점 6개의 완전 방향 그래프는 간선 30개로 21개를 더해야 하고, 무방향으로 보아도 15개 중 9쌍이 이미 연결되어 있어 6개가 필요하다. 어느 쪽도 10개가 아니다.
- ㄹ(옳음): A→B를 지우면 진입차수 0인 B부터 B, D, A 순으로 나오고, 그다음 C와 E가 동시에 진입차수 0이 되어 어느 쪽을 먼저 놓아도 되며 마지막이 F이다.
오류나 개정된 내용이 보이면 알려주세요