Network engineers are tasked with designing reliable networks while balancing business and physical concerns such as cost and available space. Reliable networks are designed to ensure packets can still reach required destinations even upon a node or router failure. At the design level, how do we ensure a network is “connected” enough to provide a required number of alternative paths from any node to any other node?

Mathematicians, electrical engineers, and early network engineers studied these problem using graph theory. We have a formal definition of the measure of connectivity of a graph or network that also allow us to determine the “weak points” whose failure would sever the network into 2 or more separated blocks. In this webinar, the attendee will be introduced to the terminology and study of graph theory in context with these engineering questions in order to develop a new perspective and skill set he/she can apply to his day-to-day work (no background in mathematics or graph theory is required).

We will begin with the definition of a graph, and other basic terminology such as the degree of a vertex, connected graphs, paths, and complete graphs. Next, we will move to a discussion of connectivity. The attendee will learn what a cut-vertex is, and several ways of finding them in a network. The notion of a nonseparable graph will be mentioned, and we will discuss how we can know if a given network is nonseparable. These fundamentals will enable us to understand what the connectivity measure of a graph is, its relation to the resilience and reliability of a network. We will also look at using powers of graphs to add edges to achieve a desired level of connectivity per given requirements.

Intro: Why we care about graph theory and connectivity

Graph Basics:

- What is a graph?
- What are the parts of a graph?
- How do we get around on graphs?
- What does it mean to say a graph is connected?
- What is the degree of a graph?
- What is a complete graph?

Connectivity:

- What is a cut-vertex? What does it mean if we have one in our network? How do we find these?
- Nonseparable graphs — How do we know if our network is nonseparable? Can we make a network nonseparable?
- Vertex connectivity and its relation to reliability and resilience of a network
- How do we determine the maximum connectivity graphs? (Intro to Harary graphs)
- Using powers of graphs to add edges to achieve connectivity requirements

The key takeaways for the attendees will be

- New familiarity with a mathematical topic highly applicable to his field (and partially developed as a result of questions posed in early network engineering)
- An understanding of what connectivity in networks means mathematically
- A new perspective on network design