Ready to Start Your Career?

By: ProgrammerE

January 2, 2017

# 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 is0 | 1 | 0 | 0 |

1 | 0 | 0 | 1 |

0 | 0 | 0 | 0 |

0 | 0 | 0 | 1 |

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 |

1 | 2 | 0 | 2 |

2 | 1 | 0 | 4 |

0 | 0 | 0 | 0 |

0 | 0 | 0 | 3 |