Graph Theory and Algebraic Structures

Author: Dai Yiqi
Publisher:
Publish Date: 1995-08-01
Features: Discrete Mathematics is a fundamental mathematics course for computer science majors. Together with "Mathematical Logic and Set Theory," this book forms the textbook for the Discrete Mathematics course at Tsinghua University's Computer Science Department, with a total of 50 teaching hours. This book is based on the author's long-term teaching materials for "Graph Theory and Algebraic Structures." It consists of ten chapters, divided into two parts. The first six chapters cover graph theory. Chapter 1 introduces the basic concepts of graphs and their algebraic representation methods. Chapters 2 to 6 discuss in detail the main content of graphs, including paths and cycles, trees, planar graphs and graph coloring, matching and network flow, and graph connectivity, closely integrating them with computer applications. Numerous efficient graph algorithms are introduced, along with their correctness proofs and complexity analysis, to provide readers with better training and development in graph applications and algorithm design and analysis. Chapters 7 to 10 cover algebraic structures, focusing on groups, rings and fields, lattices, and Boolean algebra. These are fundamental topics in abstract algebra and important mathematical foundations for computer science. The book has a compact structure, concise content, rigorous proofs, and fluent language. To facilitate readers' understanding and mastery of basic theories, the book provides abundant examples, with a substantial number of exercises at the end of each chapter, appropriately challenging, along with a certain number of computer exercises to help readers familiarize themselves with and master graph programming techniques. This book can serve as a textbook or reference for computer science majors, as well as a reference for computer engineering professionals.