Introduction to Graph Theory

What is Graph Theory?

Graph Theory studies how things are connected, through a network of points and lines.

A graph looks like this:

An Example Graph

Yes, it is called a "graph"... but it is NOT this kind of graph:

They are both called "graphs". But they are different things. Just how it is.

This subject explores how these points and lines relate to each other, and how to best travel around them.

You can think of it as places and roads, or as stations and trains ... or as a map of friendships where each person is a node and each friendship is an edge.

There are many ways to think about graphs!

Graphs have applications in many areas such as computer science, biology, social sciences, transport and more.

Let's learn some special words:

A point is called a vertex (plural vertices)
A line is called an edge.
The whole diagram is called a graph.

The number of edges that lead to a vertex is called the degree.

A route around a graph that visits every vertex once is called a simple path.
A route around a graph that visits every edge once is called an Euler path.

A Simple Path is like finding a way to visit every friend's house exactly once.

An Euler Path is like a mail carrier's route that goes down every street once.

Some Examples:

This Graph has:

5 vertices: A, B, C, D and E
8 edges: AB, BC, CD, DA, AE, BE, AC and BD
Vertices A and B have degree 4
Vertices C and D have degree 3
Vertex E has degree 2

This Graph has:

6 vertices: A, B, C, D, E and F
10 edges: AB, BC, CD, DA, AF, BF, CF, DF, AE and BE
Vertices A, B and F have degree 4
Vertices C and D have degree 3
Vertex E has degree 2

Try the The Seven Bridges of Königsberg activity.

Real-World Uses

In the real world, we can find many situations that can be represented using graph theory:

Transportation networks: Vertices can represent stations, and edges can represent the routes connecting them.
Social networks: Vertices can be people, and edges can denote friendships or connections.
Internet: Web pages can be seen as vertices, and hyperlinks as edges connecting them.

Graph theory can help in planning the most efficient public transportation routes or managing network traffic on the internet.

Types

There are many types of graphs such as directed and undirected graphs, weighted graphs, and algorithms that can solve fascinating problems like finding the shortest path between two points.