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.