This book is a by-product of my experience in teaching and research in the general field of algorithmic combinatorics during the years 1967-1971. I felt the need of a suitable textbook for teaching this subject. My first set of notes, on graph theory, was written while I visited Harvard University during 1967 to 1969. This was a one-semester course for graduate students in computer science, and it was taught twice. In 1969-1970, I taught a combinatorics course at the Feinberg Graduate School of The Weizmann Institute of Science. This was a full-year course and was again directed toward the special needs of the graduate students in computer science. I added sections on permutations, combinations, partitions, and so on. The course notes were mimeographed for the students’ convenience. This book is an advanced version of the notes used in 1970-1971.
Author(s): Shimon Even
Publisher: Macmillan
Year: 1973
Language: English
Pages: 273
Tags: Математика;Дискретная математика;Комбинаторика;
ALGORITHMIC COMBINATORICS 1 ......Page 1
Copyright 5......Page 5
Preface 6 ......Page 6
CONTENTS 9......Page 9
1.1 Introduction 13......Page 13
1.2 Generation of all permutations by adjacent transpositions 14......Page 14
1.3 A method for speeding up Algorithm 1.1 19......Page 19
1.4 Nets for performing permutations through transpositions 23......Page 23
1.5 Remarks on other results 31......Page 31
References 32......Page 32
2.1 Binomial coefficients 35......Page 35
2.2 Combinations with repetitions 40......Page 40
2.3 An algorithm for generating all combinations in lexicographic order 44......Page 44
2.4 A loop-free algorithm for generating all combinations 49......Page 49
Exercises 55......Page 55
References 57......Page 57
3.1 The fundamental formula of inclusion and exclusion 59......Page 59
3.2 An application of the sieve formula in number theory 61......Page 61
3.3 Mobius inversion and circular words 63......Page 63
3.4 Derangements 67......Page 67
3.5 Partitions 68......Page 68
3.6 An algorithm for generating partitions 77......Page 77
Exercises 81......Page 81
References 84......Page 84
4.1 Introduction to graph theory 85......Page 85
4.2 Euler graphs 87......Page 87
4.3 De Bruijn sequences 89......Page 89
4.4 Shortest-path algorithms 92......Page 92
4.5 Traversal of labyrinths 97......Page 97
Exercises 100......Page 100
References 102......Page 102
5.1 Tree definitions 103......Page 103
5.2 The minimum spanning tree problem 106......Page 106
5.3 The number of spanning trees 110......Page 110
Exercises 119......Page 119
References 120......Page 120
6.1 Directed tree definitions 121......Page 121
6.2 The infinity lemma 124......Page 124
6.3 The number of directed spanning trees 126......Page 126
6.4 Directed trees and Euler circuits 130......Page 130
6.5 Scanning a graph by depth-first search 133......Page 133
Exercises 135......Page 135
References 136......Page 136
7.1 Introduction 139......Page 139
7.2 The Huffman tree 144......Page 144
7.3 Application of the Huffman tree to sort-by־merge techniques 150......Page 150
7.4 The number of full binary ordered trees with n vertices 152......Page 152
Exercises 157......Page 157
References 158......Page 158
8.1 Cliques and their number 159......Page 159
8.2 An algorithm for generating all cliques of a given graph 167......Page 167
8.3 The set-covering algorithm 170......Page 170
8.4 Dominating sets and graph coloration 174......Page 174
Exercises 175......Page 175
References 177......Page 177
9.1 Maximum cliques and minimum coloration of\ttransitive graphs 179......Page 179
9.2 Transitive orientation of undirected graphs 183......Page 183
9.3 Permutation graphs 191......Page 191
9.4 Examples of applications 198......Page 198
Exercises 204......Page 204
References 205......Page 205
10.1 Graphs with a source, a sink, and upper bounds on the flow in the edges 207......Page 207
10.2 Improvement of the algorithm with a bound on the number of steps in the computation 214......Page 214
10.3 Graphs with upper and lower bounds on the flow in the edges 219......Page 219
10.4 Minimum flow in graphs with a source, a sink, and lower bounds on the flow in the edges 226......Page 226
Exercises 228......Page 228
References 231......Page 231
11.1 PERT graphs 233......Page 233
11.2 Connectivity in graphs 236......Page 236
11.3 Matching 242......Page 242
Exercises 246......Page 246
References 248......Page 248
12.1 Live and safe markings 251......Page 251
12.2 Relations between markings 255......Page 255
12.3 The maximum marking 262......Page 262
Exercises 265......Page 265
References 266......Page 266
INDEX 269......Page 269
