Network Connectivity, Graph Theory, and Reliable Network Design

Home » Webinars » Networking Fundamentals » 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.

Last modified on 2019-03-08 (release notes)


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

1:13:09 Trees and Spanning Trees

Basics and Properties 9:09 2019-04-18
Spanning Trees 10:33 2019-04-18
Minimum Spanning Tree 11:29 2019-04-18
Counting Spanning Trees 17:19 2019-04-18
Generating Spanning Trees 7:04 2019-04-18
STP Protocol and Implementation Considerations 8:42 2019-04-18
Conclusions 8:53 2019-03-08

Slide Deck

Graph Theory - Connectivity and Network Reliability 520K 2018-10-02
Graph Theory - Trees 555K 2019-03-07

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.


Optimization Algorithms for Networks and Graphs, E. Minieka
I consider this book pretty widely accessible. The focus is on algorithms and implementation, so if the reader is not comfortable with graph basics, he should accompany this book with another focused on graph theory principles (like Chartrand’s “A First Course in Graph Theory”). The work covers tree algorithms (spanning tree and maximum branching), path algorithms (shortest path, all shortest path, and k-th shortest path), flow algorithms (ma/min flow, dynamic, gains), matching, and location. The author wrote with an operations researcher in mind, but these algorithms are just as applicable to computer networks.
Graph Theory with Applications to Engineering and Computer Science, N. Deo
I included this one for those wanting to look deeper into cyclic interchange and other topics. This book also has a nice chapter on algorithms on graphs, including some routines in FORTRAN, but these can be adapted to other languages as desired. I wouldn’t recommend this one for basics, but it does cover some interesting topics and applications, particularly for electrical networks. Chapter 3 on trees discusses cyclic interchange. The level of this book is intermediate.
Graphs and Algorithms, M. Gondran
This one also has an OR focus, but is nonetheless worthwhile as a read. This one is significantly more advanced than the first one, but is good for those inclined to theoretical CS and programming in addition to network engineering.
Graphs and Networks, B. Carre
Another advanced algorithms book for those interested in concepts behind these algorithms from a more theoretical perspective. The focus tends to be more on path problems, but this makes another nice extension of (1).
A First Course in Graph Theory, G. Chartrand and P. Zhang
I really can’t recommend this one highly enough as a companion to any of the others and as a great introduction to the space. The survey of topics is fantastic. This one does discuss isomorphism, trees, connectivity, traversability, digraphs, planarity, and distance among other topics in a very readable way, with plenty of motivating examples.
You started this section on %started% Mark completed