IB Mathematics Applications & Interpretation AHL 3.14—graph Theory Notes

Graph Theory in Mathematics AI

• Graph theory is a fascinating branch of mathematics that has found extensive applications in computer science, network analysis, and artificial intelligence.
• In the context of Math AI, graph theory provides powerful tools for modeling complex relationships and solving various computational problems.

Fundamental Concepts

Graphs, Vertices, and Edges

• A graph is a mathematical structure consisting of a set of vertices (also called nodes) and a set of edges that connect pairs of vertices.
• Formally, a graph $G$ is defined as an ordered pair $(V, E)$, where $V$ is the set of vertices and $E$ is the set of edges.

Adjacent Vertices and Edges

• Two vertices are considered adjacent if they are connected by an edge.
• Similarly, two edges are adjacent if they share a common vertex.

Degree of a Vertex

• The degree of a vertex is the number of edges connected to it.
• For an undirected graph, this is simply the count of edges incident to the vertex.
• In a directed graph, we distinguish between in-degree (number of incoming edges) and out-degree (number of outgoing edges).

Types of Graphs

Simple Graphs

• A simple graph is an undirected graph that does not allow multiple edges between the same pair of vertices (no parallel edges) and does not allow edges that connect a vertex to itself (no self-loops).

Complete Graphs

• A complete graph is a simple graph in which every pair of distinct vertices is connected by a unique edge.
• A complete graph with $n$ vertices is denoted as $K_n$ and has $\frac{n(n-1)}{2}$ edges.

Weighted Graphs

• A weighted graph is a graph in which each edge is assigned a numerical value, called a weight.
• These weights can represent various quantities such as distances, costs, or capacities.

Directed Graphs

• A directed graph, or digraph, is a graph where edges have a direction associated with them.
• Each edge is represented by an ordered pair of vertices $(u, v)$, indicating that the edge goes from $u$ to $v$.

In-degree and Out-degree

For a vertex in a directed graph:

• In-degree: The number of edges coming into the vertex