Muutke küpsiste eelistusi

E-raamat: Game of Cops and Robbers on Graphs

  • Formaat - PDF+DRM
  • Hind: 63,65 €*
  • * hind on lõplik, st. muud allahindlused enam ei rakendu
  • Lisa ostukorvi
  • Lisa soovinimekirja
  • See e-raamat on mõeldud ainult isiklikuks kasutamiseks. E-raamatuid ei saa tagastada.

DRM piirangud

  • Kopeerimine (copy/paste):

    ei ole lubatud

  • Printimine:

    ei ole lubatud

  • Kasutamine:

    Digitaalõiguste kaitse (DRM)
    Kirjastus on väljastanud selle e-raamatu krüpteeritud kujul, mis tähendab, et selle lugemiseks peate installeerima spetsiaalse tarkvara. Samuti peate looma endale  Adobe ID Rohkem infot siin. E-raamatut saab lugeda 1 kasutaja ning alla laadida kuni 6'de seadmesse (kõik autoriseeritud sama Adobe ID-ga).

    Vajalik tarkvara
    Mobiilsetes seadmetes (telefon või tahvelarvuti) lugemiseks peate installeerima selle tasuta rakenduse: PocketBook Reader (iOS / Android)

    PC või Mac seadmes lugemiseks peate installima Adobe Digital Editionsi (Seeon tasuta rakendus spetsiaalselt e-raamatute lugemiseks. Seda ei tohi segamini ajada Adober Reader'iga, mis tõenäoliselt on juba teie arvutisse installeeritud )

    Seda e-raamatut ei saa lugeda Amazon Kindle's. 

This book is the first and only one of its kind on the topic of Cops and Robbers games, and more generally, on the field of vertex pursuit games on graphs. The book is written in a lively and highly readable fashion, which should appeal to both senior undergraduates and experts in the field (and everyone in between). One of the main goals of the book is to bring together the key results in the field; as such, it presents structural, probabilistic, and algorithmic results on Cops and Robbers games. Several recent and new results are discussed, along with a comprehensive set of references. The book is suitable for self-study or as a textbook, owing in part to the over 200 exercises. The reader will gain insight into all the main directions of research in the field and will be exposed to a number of open problems.

Arvustused

The authors do a wonderful job of keeping the exposition lively and engaging, while still covering some deep mathematics and introducing some fascinating ideas. The technical background required to read this book is relatively low, and the authors do a good job of introducing the relevant background as needed. For these reasons, as well as the fact that the subject is itself engaging, this is a book that I would happily hand to an undergraduate math major for an independent study, capstone project, or even just to read for fun! But it is also a book that I think any mathematician could pick up and quickly learn something new and interesting. And I cannot think of a higher compliment to give than that." - Darren Glass, MAA Online

"This is a textbook that presents the state of the art in the literature on Cops and Robbers games and, more generally, vertex pursuit games on graphs." - Giacomo Bonanno, Zentralblatt MATH

"[ This] book is well written, informative, and fun to read. It easily meets the goals of surveying the main directions in the area, and of providing a tool through which one could learn about games and graphs. Thus, it is useful both as an introduction and a reference." - Gary MacGillivray, MathSciNet

List of Figures
xi
Preface xv
Chapter 1 Introduction
1(28)
§1.1 The Game
1(4)
§1.2 Interlude on Notation
5(5)
§1.3 Lower Bounds
10(6)
§1.4 Upper Bounds
16(4)
§1.5 Cops, Robbers, and Retracts
20(9)
Exercises
23(6)
Chapter 2 Characterizations
29(24)
§2.1 Introduction
29(1)
§2.2 Characterizing Cop-win Graphs
30(9)
§2.3 Characterizing Graphs with Higher Cop Number
39(14)
Exercises
48(5)
Chapter 3 Meyniel's Conjecture
53(26)
§3.1 Introduction
53(3)
§3.2 An Improved Upper Bound for the Cop Number
56(6)
§3.3 How Close to n?
62(4)
§3.4 Meyniel's Conjecture in Graph Classes
66(13)
Exercises
73(6)
Chapter 4 Graph Products and Classes
79(30)
§4.1 Introduction
79(4)
§4.2 Cop Numbers and Corners in Products
83(3)
§4.3 Covering by Cop-win Graphs
86(6)
§4.4 Genus of a Graph
92(3)
§4.5 Outerplanar Graphs
95(3)
§4.6 Planar Graphs
98(11)
Exercises
105(4)
Chapter 5 Algorithms
109(24)
§5.1 Introduction
109(3)
§5.2 Background on Complexity
112(7)
§5.3 Polynomial Time with k Fixed
119(5)
§5.4 NP-hard with k Not Fixed
124(3)
§5.5 Open Problems
127(6)
Exercises
128(5)
Chapter 6 Random Graphs
133(32)
§6.1 Introduction
133(3)
§6.2 Constant p and log n Many Cops
136(3)
§6.3 Variable p and Bounds
139(10)
§6.4 The Zig-Zag Theorem
149(4)
§6.5 Cops and Robbers in the Web Graph
153(12)
Exercises
162(3)
Chapter 7 Infinite Graphs
165(26)
§7.1 Introduction
165(2)
§7.2 Introducing the Infinite Random Graph
167(5)
§7.3 Cop Density
172(6)
§7.4 Infinite Chordal Graphs
178(4)
§7.5 Vertex-transitive Cop-win Graphs
182(9)
Exercises
187(4)
Chapter 8 Variants of Cops and Robbers
191(30)
§8.1 Imperfect Information
192(7)
§8.2 Traps
199(4)
§8.3 Tandem-win
203(2)
§8.4 Playing on Different Edge Sets
205(4)
§8.5 Distance k Cops and Robbers
209(6)
§8.6 Capture Time
215(6)
Exercises
219(2)
Chapter 9 Good Guys Versus Bad Guys
221(38)
§9.1 Introduction
221(2)
§9.2 Firefighter
223(7)
§9.3 Seepage
230(3)
§9.4 Graph Searching
233(4)
§9.5 Helicopter Cops and Robbers and Marshals
237(2)
§9.6 Cleaning
239(13)
§9.7 Combinatorial Games
252(7)
Exercises
256(3)
Bibliography 259(14)
Index 273
Anthony Bonato, Ryerson University, Toronto, ON, Canada

Richard J. Nowakowski, Dalhousie University, Halifax, NS, Canada