Discrete Mathematics For AIML - Chapter 4 Graph Theory & Trees

Chapter 4 — Graph Theory & Trees

This chapter explores graphs, trees, and graph algorithms. Graph theory is widely used in AI & ML for network modeling, search algorithms, and hierarchical structures.

4.1 Graph Definitions

A graph G = (V, E) consists of vertices (nodes) V and edges E connecting them.

Vertices: Represent entities or points.
Edges: Represent relationships or connections.
Directed Graph: Edges have direction (from u → v).
Undirected Graph: Edges have no direction.

AI/ML Context: Nodes can represent users, features, or data points; edges represent relationships, similarities, or interactions.

4.2 Types of Graphs

Weighted Graphs: Edges carry weights (distance, similarity).
Bipartite Graphs: Nodes divided into two sets with edges only between sets.
Cyclic / Acyclic: Cycles exist or not; DAGs (Directed Acyclic Graphs) are important in ML pipelines.

4.3 Graph Representations

Adjacency Matrix: 2D matrix where matrix[i][j] = 1 or weight if edge exists.
Adjacency List: List of neighbors for each vertex; memory-efficient for sparse graphs.

4.4 Trees

Trees are connected, acyclic graphs.

Binary Trees: Each node has ≤ 2 children.
Spanning Trees: Subset of edges connecting all vertices without cycles.
Tree Traversal Algorithms: BFS (level-order), DFS (preorder, inorder, postorder).

4.5 Graph Algorithms

Breadth-First Search (BFS): Explore neighbors level by level; used in shortest path on unweighted graphs.
Depth-First Search (DFS): Explore deeper nodes first; used in connectivity and topological sorting.
Shortest Path Algorithms: Dijkstra’s, Bellman-Ford for weighted graphs.

AI/ML Context: Social network analysis, recommendation systems, knowledge graphs, hierarchical clustering, and graph neural networks.

4.6 Practical Python Examples

import networkx as nx

# Create a directed graph
G = nx.DiGraph()
G.add_edges_from([(1,2),(1,3),(2,4),(3,4)])

# BFS and DFS traversal
bfs_nodes = list(nx.bfs_tree(G, source=1))
dfs_nodes = list(nx.dfs_preorder_nodes(G, source=1))

print("BFS traversal:", bfs_nodes)
print("DFS traversal:", dfs_nodes)

# Shortest path
path = nx.shortest_path(G, source=1, target=4, weight=None)
print("Shortest path from 1 to 4:", path)

4.7 Why Graph Theory & Trees Matter in AI/ML

Modeling relationships between data points (knowledge graphs, social networks)
Optimizing search and traversal for recommendation systems
Hierarchical clustering and tree-based ML models (decision trees, random forests)

4.8 Exercises

Create a weighted graph representing feature similarities and find shortest paths.
Implement BFS and DFS traversals on a sample dataset graph.
Construct a binary tree and perform inorder, preorder, and postorder traversals.

Hints / Solutions

Use networkx for graph creation and traversal.
Use nx.bfs_tree() and nx.dfs_preorder_nodes().
Binary tree traversal can be implemented recursively or iteratively.

4.9 Further Reading & Videos

“Introduction to Graph Theory” by Douglas B. West
NetworkX documentation – Python library for graph algorithms
YouTube – WilliamFiset: Graph Theory tutorials
Decision Trees & Random Forests – scikit-learn documentation

Next Chapter: Boolean Algebra & Logic Circuits — representing logical functions, Boolean simplification, and circuit design in AI & ML applications.

IndianTechnoEra