Graph Theory FUNdamentals

Co-authorship network map of 8,500 doctors and scientists publishing on hepatitis C between 2008 and 2012 and the almost 60,000 co-authorship relationships between them. Photo via Andy Lamb

Graph Theory is the study of graphs that concerns the relationship between edges and vertices. In computer science, graphs are used to represent networks of communication, data organization, computational devices, and the flow of computation.

Applications of Graph Theory in Computer Science

  1. Modeling Networks — Used to analyze network connections.
  2. Social computing — Recommending mutual friends.

Other applications of Graph Theory

  1. Science — Used in molecular structure, DNA structure of organisms.
  2. Electrical Engineering — Used in the design of circuit connections.
  3. Airplanes — Used in scheduling departures and arrivals

Graph Theory Terminology

Point + Line

A point is an exact position on a plane surface, usually denoted by a letter.

A point represented by letter A

A line is one-dimensional, and can be the connection between two points.

This is an example of what a line isn’t

Vertex

A vertex, also called a node, is where multiple lines meet.

Edge

An edge is a line that connects two vertices.

Graph

A graph can be defined as G = (V, E), where V is the set of all vertices and E is the set of all edges.

This is an example of a tree graph where, G = (6, 5)

Loop

A loop occurs when an edge is drawn from a vertex to itself.

Types of Graphs

Simple Graph:

A graph with no loops and no parallel edges. The maximum number of edges possible in a simple graph with ’n’ vertices, is given by n^C2 where n^C2 = n(n–1)/2. To calculate the number of simple graphs possible with ’n’ vertices, 2^nc2 = 2^n(n-1)/2. For example, if n = 5, the maximum number of edges for that graph would be:

n^C2 = n(n–1)/2
= 5(5–1)/2
= 20/2
= 10 edges
--------------------------------------------------------------------
2^nC2 = 2^n(n-1)/2
= 2^5(5-1)/2
= 2^10
= 1024

Bipartite Graph:

A simple graph (G=(V,E)) with vertex partition where V= {V1, V2} and every edge of E connects a vertex in V1 to a vertex in V2.

Cyclic vs Acyclic Graphs:

Cyclic: Contains at least one cycle.

Acyclic: Contains no cycles.

Tree Graph:

Graphs which don’t contain cycles, which makes them acyclic. In computer science, trees are a data structures that connects vertices (nodes) in a parent-child relationship.

The edges of a tree are known as branches. Elements of trees are called their nodes. The nodes without child nodes are called leaf nodes.

Depth-first Search vs. Breadth-first Search

In a depth-first search, start at the root of the tree, and follow a branch until the vertex (node) you are looking for is reached, or until a leaf node is reached.

In a breadth-first search, start at the root of the tree, and find all the nodes that are one branch away from the root, then find all the nodes that are two branches away, and so on.

       A
/ \
B C
/ / \
D E F
DFS approach -> A, B, D, C, E, F
BFS approach -> A, B, C, D, E, F

Applications

Depth-first search is often used in simulations of games. Think of DFS as a game of chess, where your starting point leads to a series of moves played by your opponent, and vice versa.

Breadth-first search is mainly used to find the shortest path, that’s why it’s often used in GPS systems to find nearby locations. It’s even used in social networking sites to find people based on location or schools. Another example of BFS is the “six degrees of Kevin Bacon” game, where players try to find the shortest chain of actors/actresses who are connected to Kevin Bacon. You can play the game at https://oracleofbacon.org/.