IB Mathematics AI AHL Graph theory Graphs, vertices, edges MAI Study Notes- New Syllabus

IB Mathematics AI AHL Graph theory Graphs, vertices, edges MAI Study Notes

LEARNING OBJECTIVE

Graph theory

Key Concepts:

Introduction to Graph Theory
Minimum Spanning Trees

MAI HL and SL Notes – All topics

A graph G [or a graph $G(V,E)$] consists of:

a set of vertices V
a set of edges between vertices E

For example, the graph G with:

$V=\{A,B,C,D,E\}$
$E=\{AB,AE,BC,BE, CD, CE, DE\}$ is the following:

The vertices A and B are adjacent (they are linked by edge AB).
The edges AB and BC are adjacent (they are linked by vertex B).
A and C are not adjacent. AB and EC are not adjacent.

Graph is simple if

It contains no loops (e.g. edge A to itself)
It contains no parallel edges (e.g., two edges from A to B)

Adjacency:

Two vertices are considered adjacent if they are directly connected by an edge.
Two edges are considered adjacent if they share a common vertex.

Degree of a Vertex: The degree of a vertex is the total number of edges connected to it. Equivalently, it’s the number of vertices adjacent to that vertex.

For each vertex we define:
$\text{degree of A = number of adjacent vertices}$

Example

Vertex:
Degree:

▶️Answer/Explanation

Solution:

Simple Graphs: A graph is called simple if it meets two conditions:

1. It has no loops (an edge connecting a vertex to itself).
2. It has no parallel edges (more than one edge connecting the same pair of vertices).

Relationships like friendship between different people are often modeled using simple graphs.

Complete Graphs:

A complete graph is a simple graph where every distinct pair of vertices is connected by an edge. A complete graph with $n$ vertices is denoted as $K_n$. It contains the maximum possible number of edges for a simple graph with $n$ vertices, which is $ \frac{n(n-1)}{2} $.

Example

How many edges does $K_5$ have?

▶️Answer/Explanation

Solution:

Look at $K_s$.
Every vertex is connected to the other 4 vertices:

$
5 \times 4=20
$

But every edge is counted twice. Thus, the total number of edges is

$
\frac{5 \times 4}{2}=10
$

In general, the complete simple graph $K_n$ contains

$
\frac{n(n-1)}{2} \text { edges }
$

Weighted Graphs:

In a weighted graph, each edge has an associated numerical value called its weight. This weight often represents a quantity like distance, cost, or capacity associated with the connection between the vertices. For example, a map showing cities (vertices) and driving distances (weights) between them can be represented as a weighted graph.

Example

we want to include the distances between 5 cities:

▶️Answer/Explanation

Solution:

The path ABCD has
length = 3 [as it contains 3 edges]
total weight = 27 [sum of weights 8+9+10=27]

Directed Graphs (Digraphs):

In a directed graph, edges have a direction associated with them, usually indicated by an arrow. An edge from vertex A to vertex B is distinct from an edge from B to A. These are useful for modeling relationships where the connection is not necessarily symmetric, like one-way streets or “following” relationships on social media.

Example

▶️Answer/Explanation

Solution:

$A$ “follows” $B$ but $B$ “does not follow” $A$.
$E$ and C” follow” each other!
There is no relation between $A$ and $C$, etc.
Finally, the person $A$
follows 1 person: we say that the vertex $A$ has out-degree 1, has 1 follower: we say that the vertex $A$ has in-degree 1.
Similarly, $E$ (which seems to be the most “sociable” person), has out-degree 4 and in-degree 2 .

Concepts for Directed Graphs

In-Degree and Out-Degree: For a vertex in a directed graph:
The in-degree is the number of edges pointing towards that vertex.
The out-degree is the number of edges pointing away from that vertex.

Graph Structures

Subgraphs:

A subgraph is a graph formed by taking a subset of the vertices and a subset of the edges (connecting those vertices) from a larger graph.

is a simple graph of 5 vertices and 7 edges.
It is a subgraph of $K_5$

Trees:

A tree is a specific type of graph characterized by being connected and having no cycles. Key properties of a tree with $n$ vertices include:

1. It is connected (there is a path between any two vertices).
2. It contains no cycles.
3. It has exactly n-1 edges.

If a graph satisfies any two of these three properties, it must also satisfy the third and is therefore a tree. Trees represent the most minimal way to connect a set of vertices. Adding any edge to a tree creates a cycle, while removing any edge disconnects it.

For 1 vertex, there is only 1 trivial tree: