Joyner D. Algorithmic Graph Theory and Sage 2013

Download this torrent!

Joyner D. Algorithmic Graph Theory and Sage 2013

Textbook in PDF format This contribution is an introduction to algorithmic graph theory with a practical focus on using the Sage mathematical software. It systematically covers fundamental concepts of graph theory, such as trees, connectivity, and distances, as well as graph algorithms, including shortest path searches and minimum spanning trees. Significant attention is given to structural aspects like graph data structures, vertex centrality, and optimal traversals. More specialized topics are also explored, including graph colorings, network flows, and elements of algebraic graph theory. The conclusion features an introduction to random graph theory and network models. The book combines theoretical foundations with the practical implementation of algorithms, making it a valuable resource for learning both the theory itself and the capabilities of the Sage computational system. Acknowledgments Introduction to graph theory Graphs and digraphs Subgraphs and other graph types Representing graphs in a computer Graph transformations Isomorphic graphs New graphs from old Problems Trees and forests Definitions and examples Properties of trees Minimum spanning trees Binary trees Huffman codes Tree traversals Problems Shortest paths algorithms Representing graphs in a computer Graph searching Weights and distances Dijkstra’s algorithm Bellman-Ford algorithm Floyd-Roy-Warshall algorithm Johnson’s algorithm Problems Graph data structures Priority queues Binary heaps Binomial heaps Binary search trees Problems Distance and connectivity Paths and distance Vertex and edge connectivity Menger’s theorem Whitney’s Theorem Centrality of a vertex Network reliability The spectrum of a graph Expander graphs and Ramanujan graphs Problems Centrality and prestige Vertex centrality Edge centrality Ranking web pages Hub and authority Problems Optimal graph traversals Eulerian graphs Hamiltonian graphs The Chinese Postman Problem The Traveling Salesman Problem Graph coloring Vertex coloring Edge coloring The chromatic polynomial Applications of graph coloring Network flows Flows and cuts Chip firing games Ford-Fulkerson theorem Edmonds and Karp’s algorithm Goldberg and Tarjan’s algorithm Algebraic graph theory Laplacian and adjacency matrices Eigenvalues and eigenvectors Algebraic connectivity Graph invariants Cycle and cut spaces Problems Random graphs Network statistics Binomial random graph model Erd˝os-R´enyi model Contents iii Small-world networks Scale-free networks Problems Asymptotic growth GNU Free Documentation License Bibliography Index