조합론

서인석

지은이:송용진
  

지은이:김석진
  

지은이:오병권
  

지은이:서인석
  

1단원조합적사고의기초-1
1.1경우의수의기초이론·2
(1)순열과조합·4
(2)이항정리와조합등식·18
(3)포함배제의원리·22
-연습문제·28

1.2경우의수의심화이론·33
(1)전단사를이용한증명·34
(2)이중세기의기본원리·48
(3)이중세기의활용·56
-연습문제·67

2단원생성함수와수의알고리즘-77
2.1점화식과생성함수·78
(1)점화식과그활용·78
(2)생성함수·96
-연습문제·107
2.2수와알고리즘·113
(1)수와규칙성·113
(2)이진법의활용·126
-연습문제·131

3단원그래프이론의기초-135
3.1그래프이론의기본개념·138
(1)점의차수·138
(2)그래프의경로와회로·142
(3)여러가지그래프·145
-연습문제·154
3.2연결그래프와수형도·155
(1)연결그래프·155
(2)수형도와회로가없는그래프·158
-연습문제·166
3.3이분그래프와길이가홀수인회로·170
(1)여러가지이분그래프·170
(2)이분그래프와길이가홀수인회로·173
-연습문제·180
3.4극단그래프이론의기초·182
(1)튜란의정리·183
(2)여러가지극단그래프이론의문제들·190
(3)완전매칭과결혼정리·198
-연습문제·210

4단원그래프이론의응용-215
4.1램지이론과그활용·216
(1)램지문제·216
(2)램지문제의일반화·223
(3)램지유형의문제·228
-연습문제·233
4.2오일러회로와해밀턴회로·235
(1)오일러회로,오일러경로와한붓그리기·235
(2)해밀턴회로·242
-연습문제·250
4.3평면그래프와채색문제·251
(1)평면그래프의성질·251
(2)채색수와채색문제·259
-연습문제·267
4.4유향그래프·270
(1)유향그래프의기초·270
(2)토너먼트의성질·279
-연습문제·285

참고문헌·289
찾아보기·290

본교재는대한수학회에서집필하는한국수학올림피아드(KMO)교재시리즈중첫번째로출간되는교재이다.본교재는비단수학올림피아드를준비하는독자들만을대상으로집필한것이아니라수학을전공하는대학생들,심화수학을공부하고자하는과학고,과학영재고학생등다양한독자들을위한표준적인조합론교재로개발되었다.본교재는많은사전지식이없이도조합론분야를공부하고자하는독자들이가능한한쉽게접근할수있도록초보적인내용부터시작하고있고,경우의수,생성함수,수과알고리즘,그래프이론등조합론을이루는핵심적이고기초적인내용들만을주로담고있다.본교재의가장큰특징은상대적으로많은예제와다양한수준의연습문제들을담고있는것이라할수있다.