Graphs and Networks

Оглавление

S. R. Kingan. Graphs and Networks

Table of Contents

List of Illustrations

Guide

Pages

Graphs and Networks

List of Figures

Preface

1 From Königsberg to Connectomes

1.1 Introduction

1.2 Isomorphism

1.3 Constructions and Minors

Exercises

Topics for Deeper Study

Notes

2 Fundamental Topics

2.1 Trees

2.2 Distance

2.3 Degree Sequences

2.4 Matrices

Exercises

Topics for Deeper Study

Notes

3 Similarity and Centrality

3.1 Similarity Measures

3.2 Centrality Measures

3.3 Eigenvector and Katz Centrality

3.4 PageRank

Exercises

Topics for Deeper Study

Notes

4 Types of Networks

4.1 Small‐World Networks

4.2 Scale‐Free Networks

4.3 Assortative Mixing

4.4 Covert Networks

Exercises

Topics for Deeper Study

Notes

5 Graph Algorithms

5.1 Traversal Algorithms

Algorithm 5.1.1. Depth‐First Search

Algorithm 5.1.2. Breadth‐First Search

5.2 Greedy Algorithms

Algorithm 5.2.1. Generic Minimum Spanning Tree Algorithm

Algorithm 5.2.4. Kruskal's Algorithm

Algorithm 5.2.5. Prim's Algorithm

5.3 Shortest Path Algorithms

Algorithm 5.3.1. Dijkstra's Algorithm

Exercises

Topics for Deeper Study

Notes

6 Structure, Coloring, Higher Connectivity

6.1 Eulerian Circuits

Algorithm 6.1.3. Hierholzer's Algorithm

6.2 Hamiltonian Cycles

6.3 Coloring

Algorithm 6.3.3. Greedy Coloring Algorithm

6.4 Higher Connectivity

6.5 Menger's Theorem

Exercises

Topics for Deeper Study

Notes

7 Planar Graphs

7.1 Properties of Planar Graphs

7.2 Euclid's Theorem on Regular Polyhedra

7.3 The Five Color Theorem

7.4 Invariants for Non‐planar Graphs

Exercises

Topics for Deeper Study

Notes

8 Flows and Matchings

8.1 Flows in Networks

Algorithm 8.1.5. Max‐Flow‐Min‐Cut Algorithm

8.2 Stable Sets, Matchings, Coverings

8.3 Min–Max Theorems

8.4 Maximum Matching Algorithm

Algorithm 8.4.2. Bipartite Maximum Matching Algorithm

Algorithm 8.4.3. Edmond's Blossom Algorithm

Exercises

Topics for Deeper Study

Notes

Appendix A Linear Algebra

Appendix B Probability and Statistics

Appendix C Complexity of Algorithms

Notes

Appendix D Stacks and Queues

Algorithm D.1. Non‐Recursive Depth‐First Search

Algorithm D.2. Breadth‐First Search (emphasizing queues)

Bibliography

Index

WILEY END USER LICENSE AGREEMENT

Отрывок из книги

S. R. Kingan

Brooklyn College and

.....

My husband Robert Kingan helped me with the algorithms, figures and references. This book would never have been completed without his encouragement and assistance. My sons Rohan, Arun, and Ravi cheered me on. My colleagues from the New York combinatorics group Kira Adaricheva, Deepak Bal, Nadia Benakli, Jonathan Cutler, Ezra Halleck, Joseph Malkevitch, Eric Rowland, Kerry Ojakian, Peter Winkler, and Mingxian Zhong gave valuable feedback. Many thanks to Noemi Halpern and Murray Hochberg for their long standing support and encouragement and the anonymous reviewers for their nice reviews of my original book proposal. My students helped me by finding typos and errors. I was able to refine explanations by teaching the same topics over and over again. Last, but not least, Susanne Filler, the original acquisitions editor for this book, the expert team at Wiley, Inc. Kimberly Hill, Kalli Schultea, and Gayathree Sekar have been patient and easy to work with. I am grateful to all noted here and to many others who helped in bringing this book to fruition.

My goal in writing this book will be accomplished if students find the material interesting; perhaps interesting enough to pursue research in it. I wrote the book so that chapters can be added ad infinitum. Is your favorite topic missing? Let me know and I'll write a chapter on it and post it online. This is a living and growing book. The book that you hold in your hands is the beginning of a never–ending story.

.....