Graph Theory, изд. 2

Автор(ы):Diestel Reinhard
06.10.2007
Год изд.:2000
Издание:2
Описание: Almost two decades have passed since the appearance of those graph theory texts that still set the agenda for most introductory courses taught today. The canon created by those books has helped to identify some main fields of study and research, and will doubtless continue to influence the development of the discipline for some time to come. Yet much has happened in those 20 years, in graph theory no less than elsewhere: deep new theorems have been found, seemingly disparate methods and results have become interrelated, entire new branches have arisen. To name just a few such developments, one may think of how the new notion of list colouring has bridged the gulf between invariants such as average degree and chromatic number, how probabilistic methods and the regularity lemma have pervaded extremal graph theory and Ramsey theory, or how the entirely new field of graph minors and tree-decompositions has brought standard methods of surface topology to bear on long-standing algorithmic graph problems. Clearly, then, the time has come for a reappraisal: what are, today, the essential areas, methods and results that should form the centre of an introductory graph theory course aiming to equip its audience for the most likely developments ahead?
Оглавление:
Graph Theory — обложка книги. Обложка книги.
Preface [vii]
1. The Basics [1]
  1.1. Graphs [2]
  1.2. The degree of a vertex [4]
  1.3. Paths and cycles [6]
  1.4. Connectivity [9]
  1.5. Trees and forests [12]
  1.6. Bipartite graphs [14]
  1.7. Contraction and minors [16]
  1.8. Euler tours [18]
  1.9. Some linear algebra [20]
  1.10. Other notions of graphs [25]
    Exercises [26]
    Notes [28]
2. Matching [29]
  2.1. Matching in bipartite graphs [29]
  2.2. Matching in general graphs [34]
  2.3. Path covers [39]
    Exercises [40]
    Notes [42]
3. Connectivity [43]
  3.1. 2-Connected graphs and subgraphs [43]
  3.2. The structure of 3-connected graphs [45]
  3.3. Menger's theorem [50]
  3.4. Mader's theorem [56]
  3.5. Edge-disjoint spanning trees [58]
  3.6. Paths between given pairs of vertices [61]
    Exercises [63]
    Notes [65]
4. Planar Graphs [67]
  4.1. Topological prerequisites [68]
  4.2. Plane graphs [70]
  4.3. Drawings [76]
  4.4. Planar graphs: Kuratowski's theorem [80]
  4.5. Algebraic planarity criteria [85]
  4.6. Plane duality [87]
    Exercises [89]
    Notes [92]
5. Colouring [95]
  5.1. Colouring maps and planar graphs [96]
  5.2. Colouring vertices [98]
  5.3. Colouring edges [103]
  5.4. List colouring [105]
  5.5. Perfect graphs [110]
    Exercises [117]
    Notes [120]
6. Flows [123]
  6.1. Circulations [124]
  6.2. Flows in networks [125]
  6.3. Group-valued flows [128]
  6.4. k-Flows for small k [133]
  6.5. Flow-colouring duality [136]
  6.6. Tutte's flow conjectures [140]
    Exercises [144]
    Notes [145]
7. Substructures in Dense Graphs [147]
  7.1. Subgraphs [148]
  7.2. Szemeredi's regularity lemma [153]
  7.3. Applying the regularity lemma [160]
    Exercises [165]
    Notes [166]
8. Substructures in Sparse Graphs [169]
  8.1. Topological minors [170]
  8.2. Minors [179]
  8.3. Hadwiger's conjecture [181]
    Exercises [184]
    Notes [186]
9. Ramsey Theory for Graphs [189]
  9.1. Ramsey's original theorems [190]
  9.2. Ramsey numbers [193]
  9.3. Induced Ramsey theorems [197]
  9.4. Ramsey properties and connectivity [207]
    Exercises [208]
    Notes [210]
10. Hamilton Cycles [213]
  10.1. Simple sufficient conditions [213]
  10.2. Hamilton cycles and degree sequences [216]
  10.3. Hamilton cycles in the square of a graph [218]
    Exercises [226]
    Notes [227]
11. Random Graphs [229]
  11.1. The notion of a random graph [230]
  11.2. The probabilistic method [235]
  11.3. Properties of almost all graphs [238]
  11.4. Threshold functions and second moments [242]
    Exercises [247]
    Notes [249]
12. Minors, Trees, and WQO [251]
  12.1. Well-quasi-ordering [251]
  12.2. The graph minor theorem for trees [253]
  12.3. Tree-decompositions [255]
  12.4. Tree-width and forbidden minors [263]
  12.5. The graph minor theorem [274]
    Exercises [277]
    Notes [280]
Hints for all the exercises [283]
Index [299]
Symbol index [311]
Формат: djvu
Размер:1572411 байт
Язык:ENG
Рейтинг: 116 Рейтинг
Открыть: Ссылка (RU)