# Graphs and Networks: Using graphs and networks

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