This book aims to explain the basics of graph theory that are needed at an introductory level for students in computer or information sciences. To motivate students and to show that even these basic notions can be extremely useful, the book also aims to provide an introduction to the modern field of network science.Mathematics is often unnecessarily difficult for students, at times even intimidating. For this reason, explicit attention is paid in the first chapters to mathematical notations and proof techniques, emphasizing that the notations form the biggest obstacle, not the mathematical concepts themselves. This approach allows to gradually prepare students for using tools that are necessary to put graph theory to work: complex networks.In the second part of the book the student learns about random networks, small worlds, the structure of the Internet and the Web, peer-to-peer systems, and social networks. Again, everything is discussed at an elementary level, but such that in the end students indeed have the feeling that they:1.Have learned how to read and understand the basic mathematics related to graph theory.2.Understand how basic graph theory can be applied to optimization problems such as routing in communication networks.3.Know a bit more about this sometimes mystical field of small worlds and random networks.There is an accompanying web site www.distributed-systems.net/gtcn from where supplementary material can be obtained, including exercises, Mathematica notebooks, data for analyzing graphs, and generators for various complex networks.
About the Author: Maarten van Steen is full professor at the Computer Science department of VU University Amsterdam, The Netherlands. He mainly teaches in the field of distributed systems, computer networks, and operating systems. Together with Andrew Tanenbaum he has co-authored a well-known textbook on distributed systems. Confronted with the difficulties that undergraduates in computer science have with mathematics, he set out to design a course on graph theory and complex networks that for most students would be less intimidating and much more fun than regular mathematics courses. His research concentrates on extreme distributed computer systems: very large systems consisting of thousands to hundreds of thousands of computers, be they connected through wired or wireless networks. Graph theory and complexity are topics that coincide naturally with his research. Maarten van Steen considers himself an experimental computer scientist, meaning that ideas and designs are validated by real-world experiments and systems prototyping. This approach has widely shaped his attitude toward theoretical work, which he believes obtains true value if it can be tied to real-world systems.