The Max-flow/Min-cut Theorem is proved by the action of the Ford-Fulkerson algorithm which finds a feasible flow, and gives it a “certificate of optimality” by producing a cut whose capacity equals the value of that flow. Next we consider commodity Flow Networks. Dijkstra’s Algorithm grows a tree of shortest dipaths from a “single source”, and the Floyd-Warshall Algorithm solves the “all-pairs” shortest dipath problem.
#Discrete mathematics with graph theory 3rd edition worst book how to
Then we consider acyclic digraphs, showing how they may be “topologically sorted”, and how to use Dynamic Programming to count the number of dipaths from a to b, and find a shortest or a longest dipath from a to b. The first is an algorithm to orient the edges of an undirected graph to produce a strongly-connected digraph. This chapter gives a number of algorithms that apply to directed graphs, though many ideas and algorithms for undirected graphs apply to digraphs (and vice versa). Students embarking on the start of their studies of computer science will find this book to be an easy-to-understand and fun-to-read primer, ideal for use in a mathematics course taken concurrently with their first programming course. Topics and features: assumes no prior mathematical knowledge, and discusses concepts in programming as and when they are needed designed for both classroom use and self-study, presenting modular and self-contained chapters that follow ACM curriculum recommendations describes mathematical processes in an algorithmic manner, often supported by a walkthrough demonstrating how the algorithm performs the desired task includes an extensive set of exercises throughout the text, together with numerous examples, and shaded boxes highlighting key concepts selects examples that demonstrate a practical use for the concept in question. This updated and enhanced new edition also includes new material on directed graphs, and on drawing and coloring graphs, in addition to more than 100 new exercises (with solutions to selected exercises). Its motivational and interactive style provokes a conversation with the reader through a questioning commentary, and supplies detailed walkthroughs of several algorithms. The text empowers students to think critically, to be effective problem solvers, to integrate theory and practice, and to recognize the importance of abstraction. This clearly written textbook presents an accessible introduction to discrete mathematics for computer science students, offering the reader an enjoyable and stimulating path to improve their programming competence.