Network Connectivity, Graph Theory, and Reliable Network Design

Home » Webinars » Internetworking » Network Connectivity, Graph Theory, and Reliable Network Design

This webinar will give you basic familiarity with graph theory, an understanding of what connectivity in networks means mathematically, and a new perspective on network design.

17:02 Introduction

Introduction 5:16 2018-12-28
Graph Basics 11:46 2018-12-28

37:36 Graph Connectivity

Edge Connectivity 9:35 2018-12-28
Vertex Connectivity 15:52 2018-12-28
Maximizing Connectivity 12:09 2018-12-28

Slide Deck

Graph Theory - Connectivity and Network Reliability 520K 2018-10-02

Recommended Reading

Want to know more? Rachel Traylor prepared not only a long list of books you might want to read if you're interested in graph theory, but also a detailed explanation of why you might want to read them.

Introductory Graph Theory

Chartrand, Zhang: A First Course in Graph Theory
I think this is the best introductory text in graph theory I’ve seen that focuses on graph theory. Other treatments will occur in discrete math texts at the collegiate level and include combinatorics, etc, but this one is my preference. It does contain proofs (the simpler ones), and I encourage readers to really spend some time on them. It covers most major topics in graph theory at an introductory level, but there are some significant practical omissions. This is meant for undergraduate math majors, so very little on algorithms are discussed. It also discusses embeddings/colorings, etc at a pretty theoretical perspective, which may not be useful to a practicing network engineer. Nonetheless, I recommend at least the first 5 chapters.
Chartrand: Introductory Graph Theory
This text has more applications of graph theory (besides just network engineering), and is written a bit more casually. That said, I think the treatment is a bit rushed, and the examples tend to focus too much on recreational mathematics, but I’ll at least list it here for people to check out.
Harari: Graph Theory
Widely considered the first true text on graph theory, this one is a bit more advanced, and quite abstract. It’s meant for mathematicians, but it is the most widely cited.

Applied Graph Theory and Algorithms

Gondran: Graphs and Algorithms
This text is quite thorough, and though the coding is done in FORTRAN, the premises are not outdated. It's a bit heavy on the linear algebra/matroid theory, so that’s a fair warning. It does cover shortest-path-algorithms and flow networks, both topics of which are useful to a network engineer, but a solid mathematical background is required. What I do like about this book is its discussion of path algebras, though you would need to understand some concepts in linear/abstract algebra before diving into this general way of looking at path algorithms.
Minieka: Optimization Algorithms for Networks and Graphs
This text is algorithm focused, and written at a more accessible level. The focus is on industrial engineering applications, but the algorithms certainly apply to networking. Spanning tree, path, and flow algorithms are covered in chapters 2,3, and 4 respectively.
You started this section on %started% Mark completed