추가 적립 안내

영어로 Combinatorics라 불리는 조합수학은 가우스(Gauss, Carl Friedrich(1777~1855))에 의해서 명명된 것으로 알려져 있으나 실은 그 보다 이전 “Dissertatio de Arte Combinatoia”이란
문헌을 통해 라이프니치(Leibniz, Gottfied Wilhem(1646~1716))로부터 그 기원을 찾을 수 있다. 원래 의미는 수수께끼 같이 문제 자체는 이해하기 쉽고 재미있으나 해답은 쉽게 도출되지 않는
세기(counting)문제를 뜻하였고 많은 호사가나 귀족들이 즐기는 그들만의 지식게임의 성격을 지니고 근대까지 그 맥을 유지해오고 있었다.
현대에 들어서 수학이나 물리에서 주로 써 왔던 연속적이고 미적분학적 방법론에 의존한 아날로그적 사조는 한계를 드러내게 되었으며, 이에 따라 학문적/현실적 대체나 보완적 방법론이 요구되게 되었다. 특히 컴퓨터의 발달로 디지털 전자 통신의 발전에 발맞춰 인터넷을 통한 네트워크의 운용을 위한 폭팔적 수요가 배가되면서 조합수학은 20세기 중반부터 21세기 초에 이르기까지 지속적인 발전을 해 온 것이 사실이다.
조합수학이 활발히 기여하고 있는 분야를 보면, 생물학에 있어서 유전자 배열분석(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 2
nd type of Stirling numbers)
/제 1 스털링 수(the 1
st 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)
이 밖에도 여러 이산구조(디자인, 반순서집합, 사영기하 등등)에 대한 조합수학은 이후 계획중인
저술로 미루기로 한다. 위의 주제들에 대하여 가급적 쉽고 친절한 해설과 많은 그림과 표를 이용한 직관적인 이해를 도모하였다. 기초적인 사항 중에 설명이나 이해가 부족한 부분이 있다면 본
저자의 ‘이산수학’을 통하여 그 내용을 참조하기 바란다.