공통수학1
+ 정보과학
심화
이공
그래프 채색과 자원 배정
그래프 채색 정리
탐구 방법
[시간표 채색 프로젝트] 과목 간 수강생 충돌 관계를 그래프로 구성하여 탐욕 채색 알고리즘을 파이썬으로 구현하고, 정점 정렬 순서(차수 내림차순 등)를 바꿔가며 필요한 시험 시간대(색) 수를 비교 최적화
확장 연결
채색 문제가 NP-난해임을 이해하고, 탐욕 알고리즘으로 근사해를 구하는 휴리스틱의 한계와 정점 정렬 순서가 결과에 미치는 영향을 탐구
추천 탐구 주제
4색 정리와 평면 그래프의 채색
이분 그래프와 매칭 문제(할당 최적화)
스케줄링 문제와 그래프 모델링