이산수학과 그래프론

Course Information

교재: 이산수학 (박종안,이재진,이준열,서승현 지음) 경문사

수업: 수 14~15:50 (교1 302호) 목 13~14:03 (자 5 108호)

평가: 중간고사 (30%), 기말고사 (30%), 과제 및 출석 (40%)

교수 연락처 및 면담시간: sy2kang@kangwon.ac.kr; 수요일 13~14 (자5 222호)

조교: 최환혁 whchoi@kangwon.ac.kr (자5 218호 )

Announcement

• 휴강 4/13, 5/5, 6/2: (보강계획, 4/13->6/9, 나머지는 목요일 수업 각 13분 연장으로 보강)
• 기말고사 (6/9) 범위 2,3장
• 중간고사 (4/7 목) 범위 1장과 2.1절 (~P.139) 문제 4번 해답

Topics covered in class

• 1주 기본적인 세기 방법과 순열
• 2주 조합과 이항계수
• 3주 수의 분할
• 4주 집합의 분할, 포함배제의 원리
• 5주 비둘기집의 원리
• 6주 점화관계, 동차점화식
• 7주 비동차점화식
• 8주 일반생성함수
• 9주 지수생성함수, 그래프의 종류, 그래프의 동형
• 10주 오일러회로, 해밀턴 회로
• 11주 평면그래프, 수형도
• 12주 수형도
• 13주 색칠문제
• 6/1 행렬과 그래프

Homework Assignments

• Set 1 (Due 3/9) 연습문제 1.1 #5,11,18,19,20; 1.2 #22,23,24
• Set 2 (Due 3/16) 연습문제 1.3 #16,18,20,22; 1.4 #1,2,3,4,6,8
• Set 3 (Due 3/23) 연습문제 1.4 #9,12,16,17; 1.5 #5,7,9,12,13,14
• Set 4 (Due 3/30) 연습문제 1.6 #7,8,10,11,14; 1.7 #7,9,10,11,15
• Set 5 (Due 4/6) 연습문제 1.8 #9,19,20,21,23
• Set 6 (Due 4/27) 연습문제 2.1 #10(2)(3),11(2)(3),12; 2.2 #1(2)(4), 3(2),4,5,10
• Set 7 (Due 5/4) 연습문제 2.2 # 5,9,11; 3.1 #1,4(2),8,11; 3.2 #2,4,6
• Set 8 (Due 5/11) 연습문제 3.3 Petersen graph(p.244 #7 (2)의 그래프)에는 해밀턴회로가 없음을 증명하여라.
• Set 9 (Due 5/18) 연습문제 3.4 Petersen graph는 평면그래프가 아님을 쿠라토프스키 정리를 이용하여 보여라; 3.5 Petersen graph의 생성수형도를 깊이우선탐색과 너비우선탐색을 이용하여 각각 구하라.
• Set 10 (Due 5/26, 목요일) 연습문제 3.5# 2,4,6,8,10,11,15,17,18,19