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.
Consider a social network where people are represented by vertices and friendships by edges. For instance, a simple graph with three people (A, B, C) might look like:
V = {A, B, C} E = {{A, B}, {B, C}}
This represents that A is friends with B, and B is friends with C.
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.
The concept of adjacency is crucial in many graph algorithms and applications, such as finding shortest paths or analyzing network connectivity.
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).
In the social network example above:
- Degree of A: 1
- Degree of B: 2
- Degree of C: 1
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.
$K_4$ is a complete graph with 4 vertices and 6 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.
In a transportation network, edges might represent roads with weights indicating travel times:
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
- Out-degree: The number of edges going out from the vertex
In a web graph where vertices represent web pages and edges represent hyperlinks:
- A page with many incoming links but few outgoing links would have a high in-degree and low out-degree.
- Search engines often use these metrics to rank the importance of web pages.
Planar Graphs
A graph is planar if it can be drawn on a plane without edges crossing. Planar graphs obey Euler’s formula:
$$V - E + F = 2$$
where $V$ is vertices, $E$ is edges, and $F$ is faces (regions divided by edges, including the outer region).
ExampleApplications of planar graphs include circuit design and geographical mapping to avoid unnecessary crossings.
Bipartite Graphs
A graph is bipartite if its vertices can be divided into two disjoint sets, such that no two vertices within the same set are adjacent.
ExampleBipartite graphs are crucial in matching problems (e.g., job assignments, social networks) and network flow algorithms.
HintAny graph that contains an odd-length cycle cannot be bipartite.
Subgraphs and Trees
- A subgraph is a graph whose vertices and edges are subsets of another graph.
- A tree is a connected acyclic graph, meaning it has no cycles and all vertices are reachable from any other vertex.
Trees are particularly important in computer science for organizing hierarchical data structures and in algorithms like depth-first search.
