# Introduction to Graph Theory

By: ProgrammerE

January 2, 2017

A company hires you to cut costs on their infrastructure. This requires you to know what devices are part of their infrastructure. From there, you determine where the new fiber optic cable should be installed to maximize the benefit to the organization. Finally, you discover that a router is underutilized, and recommend reconfiguring some of the users through that router. A job done well due to graph theory.

A graph G is a set of vertices V along with a set of edges E, which is the cross product of V with itself. The set of vertices may represent users, roles, devices, states, files, etc. The set of edges represents a relation between two vertices, such as coworkers, read access, a connection between two devices, a transition from one state to another, etc.A vertex v is said to be incident to an edge e if the exists some vertex x such that e = (v, x). In this scenario, we would say that nodes v and x are adjacent. Note that if there existed some edge f and some node y such that f = (y, v) or f = (x, y) then we would say that edges e and f are incidents  A graph may be represented in many ways. Two of the most common ways to represent a graph is using an adjacency list or an adjacency matrix. Let V = {A, B, C, D}, E = {(A, B), (B, A), (B, D), (D, D)}. The corresponding adjacency list is E = {A : <B>, B : <A, D>, C : <>, D : <D>}. The ith row and jth column of the adjacency matrix for a directed graph are 0 if there is no edge from the ith vertex to the jth vertex, and 1 if the edge from the ith vertex to the jth vertex exists. For our graph G, the adjacency matrix is
 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 1
A graph Is said to be undirected if for every edge e of E and for all nodes u and v of V, if e = (u,v), there exists an edge f in E such that f = (v, u). This is equivalent to saying that the transpose of our adjacency matrix is the adjacency matrix. Otherwise, the graph is said to be directed.A walk is a tuple of edges (e1, e2, …, en) such that for all 0 < i < n, ei = (u. v) implies e(i+1) = (v, w) (The destination of the ith edge becomes the source of the next edge). A cycle is a walk in which e1’s source and en’s destination are the same nodes. A graph is cyclic if the graph contains at least one cycle, and acyclic if it does not. Walks may or may not contain cycles. A path is a walk which does not contain any cycles. Two nodes are said to be connected if there exists a path between them. To find all the walks of length 2, I can multiply the adjacency matrix by itself. The resulting matrix is listed bellow.
 1 0 0 1 0 1 0 1 0 0 0 0 0 0 0 1

I can multiply the adjacency matrix by itself twice to final all walks of length 3.  The resulting matrix is listed bellow.

 0 1 0 1 1 0 0 2 0 0 0 0 0 0 0 1
Note that there are two walks of length 3 from B to D. They are ((B, D), (D, D), (D, D)) and ((B, A), (A, B), (B, D)). You can repeat this process of matrix multiplications to find walks of any length.To find walks of length at most 3, we need only add the walks of length 1, 2, and 3. The resulting matrix is listed bellow.
 1 2 0 2 2 1 0 4 0 0 0 0 0 0 0 3