|
|
 |
| Авторизация |
|
|
|
| Поиск по указателям |
|
|
|
|
|
|
|
 |
|
|
|
| Gibbons A. — Algorithmic graph theory |
|
|
|
| Предметный указатель |
Adjacency list 17
Adjacency matrix 17
Adjacent 2
Admissible, G-admissible graph 86
Aho, A.V. 32 217 244
Amenities graph 93
Ancestor 7
Appel, K. 204 207 211
Approximation algorithm 178
Articulation point 5
Augmenting path, flow 98
Augmenting path, M- 127 136
Auxiliary graph 76
Back edge 20 23
Balanced digraph 6
Balanced tree 36
Basis for circuit-space 54
Basis for cut-set space 59
BDTS 246
Beineke, L.W. 74 92 93 184 204 211
Bell, A.G. 62 63
Bellmore, M. 184
Berge, C. 62 63 92 93 173 184 210 211
BFS 35
Binary tree 7
Bipartite graph 4
Birkhoff, G.D. 201 211
Block 5 24
Blossom 130
Bondy, J.A. 62 63 92 93 210 211
Booth, K.S. 86 92
Bottleneck edge 98
Bounded degree spanning tree problem 246
Branching 40 42
Branching, maximum 40 42
Branching, minimum 40 42 47
Breadth first index 35
BREADTH FIRST SEARCH 35
Breadth first tree 35
Brooks, R.L. 199 211
Busacker, R.G. 62 63 118 119 210 211
Capacity of a cut 97
Capacity of an edge 96
Cayley, A. 49 62 63
Cederbaum, I. 86 92
CGEC 239
Chang, S.K. 42 62
Cheriton, D. 42 62
Chiba, N. 207 211 214
Chinese postman problem 161
Chinese Postman problem for digraphs 165
Chinese Postman problem for graphs 163
Chord 54
Christofides, N. 184
Chromatic index, edge 195
Chromatic index, vertex 195
Chromatic polynomial 201
Church's thesis 216
Circuit 5 6
Circuit space 54
Circuit, Eulerian 153 156
Circuit, Hamiltonian 153 169 173 229 233
Circuit, simple 5 6
CLIQUE 192 229
Co-tree 54
Coffman, E.G. 148 150
Colouring 190 195
Colouring, edge 195 239
Colouring, face 204
Colouring, vertex 195 198 235
Complement graph 94
Complete bipartite graph 4
Complete graph 3
complexity 8
Component 5
Condensation of a digraph 34
Connected graph 5
Connected graph h-edge-connected 60
Connected graph h-vertex-connected 60
Connected graph, 2-connected 5
Connected vertices 5
Connectivity 106
Connectivity, edge 60
Connectivity, vertex 60
Connector problem 40 65
Cook's theorem 223
Cooke, S.A. 223 244
Covering, edge 147 151
Covering, edge, minimum cardinality 151
Critical path method 122
Cross-edge 24
Crossing number 71
Cubic graph 3
Cut edge 5
Cut of a network 97
Cut of a network, maximum 124
Cut of a network, minimum 100 124
Cut-set 57
Cut-set space 59
CYCLE see "Circuit"
Dantzig, G.B. 119
De Bruijn sequence 186
Decision problem 221
Decision problem, complementary 246
Degree majorised 193
Degree sequence 193
Degree, of a face 69
Degree, of a vertex 2
Demoucron, G. 86 92 93
Deo, N. 32 62 63
Depth, in a tree 7
Depth-first forest 20
Depth-first forest, index 20
Depth-first forest, search 20
Depth-first forest, search, for blocks 24
Depth-first forest, search, for strongly connected components 27
Depth-first forest, tree 20
Descendant 7
Deterministic Turing machine 218
DFS 20
DHC 233-
DHP 229
Digraph 5
Digraph, PERT 121
Dijkstra's algorithm 13 33 36
Dijkstra, E.W. 13 32 33 36 38
Dirac, G.A. 184
Directed edge 5
Directed graph see "Digraph"
Disconnected graph 5
Dominating set 189
Dominating set, minimum 189 245
Domination number 189
Dreyfus, S.E. 32
Dual graph 81
Dual graph, combinatorial 83
Dual graph, geometric 81
EDGE 1
Edge, capacity 96
Edge, colouring 195 239
Edge, connectivity 60
Edge, directed 5
Edge, parallel 2
Edge, weighted 7
Edge-disjoint paths 5
Edge-set 2
Edmonds, J. 32 42 62 64 101 119 128 136 147 148 184
Efficient algorithm 11
Ellipsoid method 252
Embedded graph 67
| End-points 2
Erdoes, R 193 211
Euler, S. 69 92 153
Eulerian circuits and paths 153 156
Eulerian circuits and paths, counting circuits 162
Eulers formula, non-planar graphs 72
Eulers formula, planar graphs 69
Even, S. 32 86 92 93 119 244
Excursion problem 121
Expected-time complexity 9
Exterior face 68
Face 68
Face colouring 204
Factors, 2-factors 182
Factors, K-factors 182
Fary, I. 93 94
Father 7
Filotti, I.S. 74 93
Finite graph 2
Five-colour Theorem 206
Flow augmenting path 98
Flow in a network 96
Floyd, R.W. 32
Ford, L.R. 99 100 111 118 119
Forest 7
Forward edge 24 98
Fujii, M. 148 150
Fulkerson, D.R. 99 100 111 118 119
Fundamental circuits 54
Fundamental cut-sets 58
G-admissible subgraph 86
Gabow, H. 144 148
Gale, D. 148 151
Garey, M.R. 201 210 211 241 243 244
Genus 71
Geometric dual 81
Gonzalez, T. 184
Gower, P.J. 118 119
Graham, R.L. 148 150 244
Graph 1
Graph, amenities 93
Graph, auxiliary 76
Graph, bipartite 4
Graph, complete 3
Graph, complete bipartite 4
Graph, cubic 3
Graph, directed 5
Graph, dual 81
Graph, finite 2
Graph, homeomorphic 76
Graph, induced 4
Graph, isomorphic 4
Graph, multi 3
Graph, Petersen 93 173 186
Graph, planar 67
Graph, separable 5
Graph, simple 2
Graph, sparse 17
Graph, sub 4
Graph, super 4
Graph, Tutte 215
Graph, weighted 7
Guess 220
Hadlock, F.O. 119 124 244
Haken, W. 204 207 211
Hall, P. 148 149
Hamilton, W.R. 153
Hamiltonian circuits and paths 153 169 173 229 233
Hamiltonian circuits and paths by matricial products 173
Hamiltonian circuits and paths, existence theorems 169
Harary, F. 62 63 92 93 210 211
HC 234
Heawood, P.J. 204 211
Holyer, I. 244
Homeomorphic graph 76
Hopcroft, J.E. 32 62 63 85 92 217 244
HP 233
Hungarian tree 130
In-degree 6
In-degree matrix 50
In-tree 7
Incident, from 6
Incident, to 6
Incompatible bridges 76
Independence number 189
Independent set 189
Independent set, maximum 189 229
Induced graph 4
Intractable problem 12
Iri, M. 118 119
IS 229
Isaacs, R. 211 213
Isolated vertex 2
Isomorphic graph 4
Isomorphic graph, 2-isomorphic 82 95
Itai, A. 244
Job assignment problem 149
Johnson, D.S. 201 210 211 241 243 244
Johnson, E.L. 136 148 184
Join 193
Karp, R.M. 62 101 119 124 244
Karzanov, A.V. 101 119
KC 235
Kempe, A.B. 195 204 211
Kempe-chain argument 195
Khachian, L.G. 252 253
Kirchoff matrix 50
Kirchoff, A. 57 62
Klee, V. 252 253
Knapsack problem 122
Knight’s tour 169
Knuth, D.E. 62 63
Koenigsberg bridge problem 185
Kruskal, J.B. 40 62 63 64 65
Kruskal’s algorithm 63
Kuan, M-K. 184
Kuhn, H.W. 136 148
Kuratowski, A. 77 92 93
Kuratowski’s Theorem 77
Latin square 212
Lawler, E. 118 119 148 199 211 244
Leaf 7
Lempel, A. 86 92
Length of a circuit, path 5 8
Leuker, G.S. 86 92
Level 7
Linear programming 249
Lipton, R.J. 72 92
Liu, C:L. 178 184
Longest path 15 246
Lovasz, L. 134 148
lp 246
M-augmenting path 127 136
Maheshwari, S.N. 119
Malgrange, Y. 86 93
Malhotra, V.M. 101 119
Marriage problems 149 150
Matching 125
Matching, maximum-cardinality 125 126
Matching, maximum-weight 126 136
Matching, minimum-weight perfect 164
Matching, perfect 125 134
Max-flow, min-cut Theorem 100
Maximum branching 40
Maximum cardinality matching 125 126
Maximum flow 98
Maximum independent set 189 229
Maximum length simple path 15 246
Maximum weight spanning tree 40
McCall, E.H. 252 253
|
|
|
| Реклама |
|
|
|
|
|
О проекте