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

## Paths and Trails in Graphs and Networks

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

## Special Types of Paths and Networks

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

## Graph and Network Algorithms

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

## Graph Theory Theorems

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