توضیحات
From the reviews of the previous editions ‘…. The book is a first class textbook and seems to be indispensable for everybody who has to teach combinatorial optimization. It is very helpful for students, teachers, and researchers in this area. The author finds a striking synthesis of nice and interesting mathematical results and practical applications. … the author pays much attention to the inclusion of well-chosen exercises. The reader does not remain helpless; solutions or at least hints are given in the appendix. Except for some small basic mathematical and algorithmic knowledge the book is self-contained. …’ K.Engel, Mathematical Reviews 2002 The substantial development effort of this text, involving multiple editions and trailing in the context of various workshops, university courses and seminar series, clearly shows through in this new edition with its clear writing, good organisation, comprehensive coverage of essential theory, and well-chosen applications. The proofs of important results and the representation of key algorithms in a Pascal-like notation allow this book to be used in a high-level undergraduate or low-level graduate course on graph theory, combinatorial optimization or computer science algorithms. The well-worked solutions to exercises are a real bonus for self study by students. The book is highly recommended. P .B. Gibbons, Zentralblatt fr Mathematik 2005 Once again, the new edition has been thoroughly revised. In particular, some further material has been added: more on NP-completeness (especially on dominating sets), a section on the Gallai-Edmonds structure theory for matchings, and about a dozen additional exercises as always, with solutions. Moreover, the section on the 1-factor theorem has been completely rewritten: it now presents a short direct proof for the more general Berge-Tutte formula. Several recent research developments are discussed and quite a few references have been added.
Table of Contents
Cover
Graphs, Networks and Algorithms, Fourth Edition
ISBN 9783642322778 ISBN 9783642322785
Preface to the Fourth Edition
Preface to the Third Edition
Preface to the Second Edition
Preface to the First Edition
Contents
Chapter 1: Basic Graph Theory
1.1 Graphs, Subgraphs and Factors
1.2 Paths, Cycles, Connectedness, Trees
1.3 Euler Tours
1.4 Hamiltonian Cycles
1.5 Planar Graphs
1.6 Digraphs
1.7 An Application: Tournaments and Leagues
Chapter 2: Algorithms and Complexity
2.1 Algorithms
2.2 Representing Graphs
2.3 The Algorithm of Hierholzer
2.4 How to Write Down Algorithms
2.5 The Complexity of Algorithms
2.6 Directed Acyclic Graphs
2.7 An Introduction to NP-completeness
2.8 Five NP-complete Problems
Chapter 3: Shortest Paths
3.1 Shortest Paths
3.2 Finite Metric Spaces
3.3 Breadth First Search and Bipartite Graphs
3.4 Shortest Path Trees
3.5 Bellman’s Equations and Acyclic Networks
3.6 An Application: Scheduling Projects
3.7 The Algorithm of Dijkstra
3.8 An Application: Train Schedules
3.9 The Algorithm of Floyd and Warshall
3.10 Cycles of Negative Length
3.11 Path Algebras
Chapter 4: Spanning Trees
4.1 Trees and Forests
4.2 Incidence Matrices
4.3 Minimal Spanning Trees
4.4 The Algorithms of Prim, Kruskal and Boruvka
4.5 Maximal Spanning Trees
4.6 Steiner Trees
4.7 Spanning Trees with Restrictions
4.8 Arborescences and Directed Euler Tours
Chapter 5: The Greedy Algorithm
5.1 The Greedy Algorithm and Matroids
5.2 Characterizations of Matroids
5.3 Matroid Duality
5.4 The Greedy Algorithm as an Approximation Method
5.5 Minimization in Independence Systems
5.6 Accessible Set Systems
Chapter 6: Flows
6.1 The Theorems of Ford and Fulkerson
6.2 The Algorithm of Edmonds and Karp
6.3 Auxiliary Networks and Phases
6.4 Constructing Blocking Flows
6.5 Zero-One Flows
6.6 The Algorithm of Goldberg and Tarjan
6.7 Further Reading
Chapter 7: Combinatorial Applications
7.1 Disjoint Paths: Menger’s Theorem
7.2 Matchings: Knig’s Theorem
7.3 Partial Transversals: The Marriage Theorem
7.4 Combinatorics of Matrices
7.5 Dissections: Dilworth’s Theorem
7.6 Parallelisms: Baranyai’s Theorem
7.7 Supply and Demand: The Gale-Ryser Theorem
Chapter 8: Connectivity and Depth First Search
8.1 k-connected Graphs
8.2 Depth First Search
8.3 2-connected Graphs
8.4 Depth First Search for Digraphs
8.5 Strongly Connected Digraphs
8.6 Edge Connectivity
Chapter 9: Colorings
9.1 Vertex Colorings
9.2 Comparability Graphs and Interval Graphs
9.3 Edge Colorings
9.4 Cayley Graphs
9.5 The Five Color Theorem
Chapter 10: Circulations
10.1 Circulations and Flows
10.2 Feasible Circulations
10.3 Elementary Circulations
10.4 The Algorithm of Klein
10.5 The Algorithm of Busacker and Gowen
10.6 Potentials and epsilon-optimality
10.7 Optimal Circulations by Successive Approximation
10.8 A Polynomial Procedure REFINE
10.9 The Minimum Mean Cycle Cancelling Algorithm
10.10 Some Further Problems
10.11 An Application: Graphical Codes
Chapter 11: The Network Simplex Algorithm
11.1 The Minimum Cost Flow Problem
11.2 Tree Solutions
11.3 Constructing an Admissible Tree Structure
11.4 The Algorithm
Rule of the last blocking arc:
11.5 Efficient Implementations
Chapter 12: Synthesis of Networks
12.1 Symmetric Networks
12.2 Synthesis of Equivalent Flow Trees
12.3 Synthesizing Minimal Networks
12.4 Cut Trees
12.5 Increasing the Capacities
Chapter 13: Matchings
13.1 The Berge-Tutte Formula
13.2 Augmenting Paths
13.3 Alternating Trees and Blossoms
13.4 The Algorithm of Edmonds
13.5 The Gallai-Edmonds Structure Theorem
13.6 Matching Matroids
Chapter 14: Weighted Matchings
14.1 The Bipartite Case
14.2 The Hungarian Algorithm
14.3 Matchings, Linear Programs, and Polytopes
14.4 The General Case
14.5 The Chinese Postman
14.6 Matchings and Shortest Paths
14.7 Some Further Problems
14.8 An Application: Decoding Graphical Codes
Chapter 15: A Hard Problem: The TSP
15.1 Basic Definitions
15.2 Lower Bounds: Relaxations
The Assignment Relaxation
The MST Relaxation
The s-tree Relaxation
The LP Relaxation
15.3 Lower Bounds: Subgradient Optimization
15.4 Approximation Algorithms
15.5 Upper Bounds: Heuristics
15.6 Upper Bounds: Local Search
15.7 Exact Neighborhoods and Suboptimality
15.8 Optimal Solutions: Branch and Bound
15.9 Concluding Remarks
Appendix A: Some NP-Complete Problems
Appendix B: Solutions
B.1 Solutions for Chap. 1
B.2 Solutions for Chap. 2
B.3 Solutions for Chap. 3
B.4 Solutions for Chap. 4
B.5 Solutions for Chap. 5
B.6 Solutions for Chap. 6
B.7 Solutions for Chap. 7
B.8 Solutions for Chap. 8
B.9 Solutions for Chap. 9
B.10 Solutions for Chap. 10
B.11 Solutions for Chap. 11
B.12 Solutions for Chap. 12
B.13 Solutions for Chap. 13
B.14 Solutions for Chap. 14
B.15 Solutions for Chap. 15
Appendix C: List of Symbols
C.1 General Symbols
Sets
Mappings
Numbers
Matrices
Sets of numbers and algebraic structures
Miscellaneous
C.2 Special Symbols
Graphs and networks
Objects in graphs
Parameters for graphs
Mappings on graphs and networks
Matroids and independence systems
Matrices
Codes
Miscellaneous
References
Index
————————————————————–
ترجمه ماشینی :
از بررسی های نسخه های قبلی ‘…. این کتاب یک کتاب درسی درجه یک است و به نظر می رسد برای همه کسانی که باید بهینه سازی ترکیبی را آموزش دهند ضروری است. برای دانش آموزان، معلمان و محققان در این زمینه بسیار مفید است. نویسنده ترکیب قابل توجهی از نتایج ریاضی خوب و جالب و کاربردهای عملی پیدا می کند. … نویسنده توجه زیادی به گنجاندن تمرین های خوب انتخاب شده دارد. خواننده درمانده نمی ماند; راه حل ها یا حداقل نکات در پیوست آورده شده است. به جز برخی از دانش های کوچک ریاضی و الگوریتمی، این کتاب مستقل است. …’ K.Engel, Mathematical Reviews 2002 تلاش اساسی برای توسعه این متن، شامل ویرایش های متعدد و دنباله دار در زمینه کارگاه های مختلف، دوره های دانشگاهی و مجموعه سمینارها، در این ویرایش جدید با نگارش واضح و خوب به وضوح نشان می دهد. سازمان، پوشش جامع تئوری اساسی، و برنامه های کاربردی به خوبی انتخاب شده است. اثبات نتایج مهم و نمایش الگوریتمهای کلیدی در نماد پاسکال به این کتاب اجازه میدهد تا در دورههای کارشناسی ارشد یا مقطع کارشناسی ارشد سطح بالا در زمینه نظریه گراف، بهینهسازی ترکیبی یا الگوریتمهای علوم کامپیوتر استفاده شود. راه حل های خوب کار شده برای تمرین ها یک امتیاز واقعی برای مطالعه خود توسط دانش آموزان است. کتاب به شدت توصیه می شود. P .B. Gibbons، Zentralblatt fr Mathematik 2005 یک بار دیگر، نسخه جدید به طور کامل بازنگری شده است. به طور خاص، مطالب بیشتری اضافه شده است: موارد بیشتر در مورد کامل بودن NP (مخصوصاً در مورد ست های غالب)، بخشی در نظریه ساختار گالای-ادموندز برای تطبیق، و حدود ده ها تمرین اضافی مانند همیشه، با راه حل ها. علاوه بر این، بخش قضیه 1 عاملی کاملاً بازنویسی شده است: اکنون یک اثبات مستقیم کوتاه برای فرمول عمومی تر برگ-توته ارائه می کند. چندین پیشرفت تحقیقاتی اخیر مورد بحث قرار گرفته و تعداد کمی از منابع به آن اضافه شده است. \ فهرست مطالب \ جلد \ نمودارها، شبکهها و الگوریتمها، ویرایش چهارم ISBN 9783642322778 ISBN 9783642322785 مقدمه بر ویرایش چهارم پیشگفتار نسخه سوم پیشگفتار نسخه سوم پیشگفتار نسخه سوم ویرایش اول محتویات فصل 1: نظریه اصلی نمودار 1.1 نمودارها، زیرگرافها و عوامل 1.2 مسیرها، چرخه ها، اتصال، درختان 1.3 تورهای اویلر 1.4 چرخه هامیلتونی 1.5 نمودارهای مسطح یک نمودار \ 1.6. مسابقات و لیگها فصل 2: الگوریتمها و پیچیدگی \ 2.1 الگوریتمها 2.2 نمایش نمودارها 2.3 الگوریتم Hierholzer 2.4 نحوه نوشتن الگوریتمها 2.5 پیچیدگی الگوریتمها در 7-Atrophed. کامل بودن 2.8 پنج مسئله NP-complete فصل 3: کوتاهترین مسیرها 3.1 کوتاهترین مسیرها 3.2 فضاهای متریک محدود 3.3 پهنای جستجوی اول و نمودارهای دوبخشی 3.4 کوتاهترین درختان مسیر 3.5 معادلات Acyclic Bellman’s A: زمانبندی پروژهها 3.7 الگوریتم Dijkstra 3.8 یک کاربرد: برنامههای قطار 3.9 الگوریتم فلوید و وارشال 3.10 چرخههای طول منفی 3.11 جبرهای مسیر \ فصل 4: طول درختان بزرگ و 4.4. 4.3 حداقل درختان پوشا 4.4 الگوریتم های Prim، Kruskal و Boruvka 4.5 درختان پوشا حداکثر 4.6 درختان Steiner 4.7 درختان پوشا با محدودیت 4.8 Arborescences و کارگردانی Euler Greedyp Tours The Greedy Euler5. الگوریتم و Matroids 5.2 خصوصیات Matroids 5.3 Matroid Duality 5.4 الگوریتم حریص به عنوان یک روش تقریبی 5.5 به حدا
tag : دانلود کتاب نمودارها، شبکه ها و الگوریتم ها , Download نمودارها، شبکه ها و الگوریتم ها , دانلود نمودارها، شبکه ها و الگوریتم ها , Download Graphs, Networks and Algorithms Book , نمودارها، شبکه ها و الگوریتم ها دانلود , buy نمودارها، شبکه ها و الگوریتم ها , خرید کتاب نمودارها، شبکه ها و الگوریتم ها , دانلود کتاب Graphs, Networks and Algorithms , کتاب Graphs, Networks and Algorithms , دانلود Graphs, Networks and Algorithms , خرید Graphs, Networks and Algorithms , خرید کتاب Graphs, Networks and Algorithms ,
نقد و بررسیها
هنوز بررسیای ثبت نشده است.