추가 적립 안내

조합수학이 활발히 기여하고 있는 분야를 보면, 생물학에 있어서 유전자 배열분석(assembly,
alignment), 화학의 이성질체나 폴리머 등의 제조과정, 입자물리나 양자역학, 통신 프로토콜에
있어서 자료의 압축, 오류수정부호의 구현, 정수방정식과 소수문제에 대한 연구로 암호론의 기
반을 제공하며, 공장의 공정이나 컴퓨터 계산의 스케쥴링이나 효율적 분업의 설계 등을 다루는
최적화문제에 방법론을 제공하고 있다. 반면에 순수수학적 측면에서도 점으로 추상화된 유한집
합의 원소와 선으로 간주할 수 있는 정규화된 집합(block), 그리고 상호간의 인접관계(incidence
relation)를 다룬다는 점에서 집합론이나 기하학, 정수론의 수준에서 순수한 추상적 대상을 다
루고 있는 분야이기도 하다.
크게 조합수학의 세 가지 분야와 그 내용을 소개하면 다음과 같다.
1. 계수 조합론(Enumerative combinatorics): 계수의 과학(science of countings)
2. 조합구조의 존재성에 관한 분야(Existential combinatorics): 그래프, 디자인, 반순서집합,
유한기하 등, 조합구조(이산구조)의 주어진 변수에 대한 존재성을 판별하는 연구
3. 구현 조합론(Constructive combinatorics): 존재성이 밝혀진 특수 변수에 대한 이산구조
를 구현할 최적화 방법론 연구
이 책에서는 방대한 조합수학의 위의 주제 중 계수 조합론의 기초 부분을 개관한 후 이를
기초로 이산구조의 하나인 그래프(graph)에서 그 존재성과 구현 그리고 수학의 타 분야와의
관계성 대하여 집중적으로 알아보기로 한다. 이러한 책의 내용은 다음과 같이 요약된다.
먼저, 구조 위에서 기초가 되는 집합론, 정수론, 생성함수, 대수구조 등을 요약하여 다루고
난 후, 아래의 계수 조합론의 주요 방법론과 수열에 대하여 다룬다.
\포함배제의 원리(inclusion-exclusion)
\함수의 계수(counting various functions)
\집합의 분할 수(counting set-partitions)
\정수의 분할 수(integer partition number)
\제 2 스털링 수(the 2nd type of Stirling numbers)
\제 1 스털링 수(the 1st type of Stirling numbers)
\오일러의 수(Eulerian numbers)/카탈란 수(Catalan numbers)
\수열의 생성함수(generating function)
\특수한 치환군의 계수(counting special permutations)
다음으로, 이 책의 주요 주제인 그래프 이론을 다룰 것이다. 이 분야에서 수 세기 동안 치열
한 발전을 이루어 왔던 문제들에 대하여 소개하면 다음과 같다. 이들 대부분을 이 책을 통하여
접할 수 있도록 집필하게 되었다.
\비동형 그래프의 개수
\근수형도의 개수
\영업사원의 문제(traveling salesman’s problem)
\해밀턴 순환로(Hamiltonian cycles)와 오일러 회로(Euler circuit)
\램지 수(Ramsey number)와 램지 그래프
\그래프 채색문제(graph coloring; Chromatic numbers)
\그래프 괴리성-중앙성(graph eccentricity-centrality)
\그래프 최적화 문제(optimization: bandwidth, antibandwidth)
\수형도와 정수(Matula numbers)
\최소무게근수형도와 알고리즘(Kruskal Algorithm, Prim Algorithm)
\그래프 재구현문제(graph reconstruction)
\암호학:키관리-배분문제(Key-distribution problem)

1장｜집합과 정수
2장｜계수(counting)의 기초
3장｜거대수(Combinatorial Explosion)
4장｜여러 가지 조합론의 계수들
5장｜그래프 이론
6장｜부록: 대수구조