이산수학

Course Information

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

수업: 자5 108호 (월 15~16:03, 수 10~11:50 )

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

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

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

Announcement

• 휴강 4/13, 5/30, 6/6: (보강계획, 4/13->6/8, 나머지는월요일 수업 각 13분 연장으로 보강)
• 사각형의 색채 다항식은 뭘까요? 색채다항식으로 부터 사각형의 색채수는 2임을 알 수 있나요? 오각형은 어떻습니까? 역시 ck(G)=ck(G-e)-ck(G/e)를 써야겠지요!
• 기말고사 (6/8 수) 범위 2,3 장
• 중간고사 (4/11 월) 범위 1장과 2.1절 (~p.139)

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