

소개
조합수학이 활발히 기여하고 있는 분야를 보면, 생물학에 있어서 유전자 배열분석(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)



