# Network Connectivity, Graph Theory, and Reliable Network Design

Home » Webinars » Networking Fundamentals » Network Connectivity, Graph Theory, and Reliable Network Design

Last modified on 2022-05-20 (release notes)

## Network Connectivity, Graph Theory, and Reliable 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 |

## 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. |
||

## Trees |
||

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. |
||

## Using Graph Theory in Network Design |
||

Diptanshu Singh published numerous articles describing how to use graph properties to understand the behavior of your network design |
||

Network Centrality and Robustness | ||

Five Number Summary for Network Topologies | ||

Maximum Flow Problems |