Graphs and Networks: Using Graphs and Networks

Basics of Using Graphs and Networks

Graphs and networks are mathematical structures used to model pairwise relations between objects.
A graph is a collection of points, called vertices, connected by edges. An edge that connects a vertex to itself is a loop.
A network is a graph with numbers (weights) attached to the edges. These weights could represent distance, cost, etc.
A subgraph of a graph is a graph whose set of vertices and set of edges are subsets of the original graph.
A graph is connected if there is a path between every pair of vertices. In a connected graph, there are no unreachable vertices.

A path in a graph is a sequence of vertices where each pair of consecutive vertices is connected by an edge. A path is simple if it does not pass through the same vertex more than once.
A trail in a graph is a walk in which no edges are repeated.
A circuit is a trail that starts and ends at the same vertex. A circuit is simple if, apart from the start and end vertex, it does not pass through any vertex more than once.
The length of a path, trail, or circuit is the number of edges in it. In a network, the length is the sum of the weights of its edges.

A tree is a connected graph which has no circuits. Trees are incredibly important in network theory and computer science.
A spanning tree of a connected graph is a subgraph that is a tree and includes every vertex of the original graph.
A minimum spanning tree of a network is a spanning tree with the smallest possible total weight.
The shortest path between two vertices in a network is a path with the smallest possible length.

The Prim’s Algorithm and Kruskal’s Algorithm are two effective methods to find a minimum spanning tree in a network.
Dijkstra’s Algorithm is an algorithm used to determine the shortest path from one particular starting node to another node in a graph.
An algorithm to find a maximum flow in a network is Ford-Fulkerson algorithm.

Handshaking Lemma: The sum of the degrees of the vertices of a graph G is equal to twice the number of edges of G.
Euler’s Theorem: A connected graph has an Euler circuit if and only if every vertex has even degree.
Königsberg Bridge Problem: A necessary and sufficient condition to traverse each edge of a graph exactly once and return to the starting vertex is that the graph is connected and has exactly zero or two vertices of odd degree.
Hamilton’s Theorem: Every complete graph with n vertices, where n > 2, includes a Hamilton cycle - a cycle that passes through every vertex once and then returns to the start.