그래프 이론 속의 조합수학

김상목 지음

드림미디어 2024년 05월 20일 출간

작품소개

책소개

조합수학이 활발히 기여하고 있는 분야를 보면, 생물학에 있어서 유전자 배열분석(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)
\수형도와 수열(Cayley theorem: Trees and Pr䡆fer sequence)
\근수형도와 정수(Matula numbers)
\최소무게근수형도와 알고리즘(Kruskal Algorithm, Prim Algorithm)
\수형도의 응용(Applications of tree graphs)
이 밖의 여러 이산구조(디자인, 반순서집합, 사영기하 등등)에 대한 조합수학은 이후
기획 중인 저술로 미루기로 한다. 위의 주제들에 대하여 가급적 쉽고 친절한 해설과
많은 그림과 표를 이용한 직관적인 이해를 도모하였다. 기초적인 사항 중에 설명이
나 이해가 부족한 부분이 있다면 본 저자의 ‘이산수학’을 통하여 그 내용을 참조하
기 바란다. 마지막 장은 부록으로 대수구조에 대한 기초적인 내용으로 군(group)/환
(ring)/체(field)를 소개하여 앞의 내용에서 치환이나 정수론에 대해서 다룰 때, 참고
가 될 수 있도록 제시하여 대수학(Algebra)에 대한 배경지식이 없는 독자에게 도움
을 주고자 했다.

목차

1장 | 집합과 정수
1.1 명제와 논리 | 1
1.2 집합과 연산 | 7
1.3 관계와 함수(Relation and Function) | 11
1.4 자연수와 수학적 귀납법 | 17
1.5 정수와 인수분해 | 23
2장 | 계수(counting)의 기초
2.1 합의 법칙과 곱의 법칙 | 40
2.2 계승 유형의 계수(factorial kinds of counting) | 42
2.3 조합과 이항정리에 관한 필수 등식 | 46
2.4 다항계수 | 51
2.5 포함 배제의 원리 | 54
2.6 생성함수와 수열 | 60
3장 | 거대수(Combinatorial Explosion)
3.1 의 점근범위에 관한 스털링(Stirling) 정리 | 73
3.2 에 대한 스털링(Stirling) 정리의 증명 | 73
3.3 조합론적 거대수(Combinatorial Explosion) | 79
4장 | 여러 가지 조합론의 계수들
4.1 자연수의 분할수(partition number of integers) | 83
4.2 스털링 수(Stirling numbers) | 88
4.3 카탈란 수(Catalan Numbers) | 96
4.4 오일러의 수(Eulerian Numbers) | 102
4.5 분배와 점유(Distribution and Occupation) | 106
4.6 치환의 계수(Counting Permutations) | 109
5장 | 그래프 이론
5.1 그래프의 정의와 용어 | 117
5.2 그래프의 기본 계수(counting)정리 | 122
5.3 그래프의 길(walk) | 126
5.4 그래프의 동형 | 136
5.5 부분그래프와 그래프 연산자 | 145
5.6 특수 유형의 그래프 | 149
5.7 그래프의 연결성(graph connectivity) | 156
5.8 거리와 괴리성(distance, eccentricity) | 159
5.9 수형도(Tree) 그래프와 정수 | 163
5.10 그래프 채색문제 | 197
5.11 램지 수(Ramsey number) | 209
5.12 드브르인(de Bruijn) 수열과 오일러 회로(Euler circuit) | 214
6장 | 대수구조와 그래프

작가정보

저자(글) 김상목

(현) 광운대학교 자연과학대학 수학과 교수
서강대학교 수학과 졸업(이학사)
(미) 오리건대학교(University of Oregon) 대학원 수학
과, 이학석사(MS, 1989)
(영) 런던대학교(Royal Holloway, University of
London ) 대학원 수학과, 이학박사(PhD, 2001)