Graph Theory
Course Outline
​
Course Description: This course introduces students to the fundamental principles of graph theory and its applications in computer science. Students will learn about graph types, graph algorithms, and problem-solving using graphs. The focus will be on understanding the principles, implementing graph algorithms, and their applications in computer science.
​
Introduction to Graphs
-
Definitions, representations, and examples of graphs
-
Special types of graphs: directed, undirected, weighted, unweighted, bipartite, trees, planar graphs, and multigraphs
-
Graph isomorphism
Basic Graph Algorithms
-
Depth-First Search (DFS)
-
Breadth-First Search (BFS)
-
Topological sorting
Path Algorithms
-
Dijkstra's algorithm
-
Bellman-Ford algorithm
-
Floyd-Warshall algorithm
Connectivity and Centrality
-
Articulation points, bridges, and biconnected components
-
Centrality measures: degree centrality, closeness centrality, betweenness centrality, and eigenvector centrality
Graph Coloring and Matching
-
Vertex and edge coloring
-
Graph coloring algorithms
-
Matching and maximum matching
-
Hungarian algorithm
Network Flow
-
Maximum flow and minimum cut
-
Ford-Fulkerson algorithm
-
Edmonds-Karp algorithm
Advanced Topics in Graph Theory
-
Random graphs
-
Graph drawing
-
Graphs in machine learning and data mining
Textbooks and Reference Materials:
-
"Introduction to Graph Theory" by Richard J. Trudeau
-
"Graph Theory with Applications" by John Adrian Bondy and U.S.R. Murty
Introduction to Graph Theory
In this course, we will venture into the fascinating world of graph theory, a branch of mathematics that studies relationships between entities. It's a field rich with elegance and intricate structures, with numerous applications in computer science, from data mining to software engineering, from network design to machine learning.
​
Graphs provide an incredibly versatile way of representing relationships and interactions among entities. A social network, for instance, can be represented as a graph, where individuals are nodes and their relationships are edges. Similarly, a computer network could be represented as a graph, with computers as nodes and connections as edges. In biology, a protein interaction network could be graphed, with proteins as nodes and their interactions as edges. The applications are as diverse as they are vast.
​
In the early weeks, we will learn the basics of graph theory, exploring different types of graphs, such as directed and undirected graphs, weighted and unweighted graphs, and special structures like trees and bipartite graphs. We will understand the concept of graph isomorphism, which allows us to identify when two seemingly different graphs are, in fact, the same.
​
As we move forward, we'll explore fundamental graph traversal algorithms like Depth-First Search (DFS) and Breadth-First Search (BFS). These foundational algorithms have a broad range of applications, from detecting cycles in a network to generating a maze.
​
Later, we will delve into pathfinding algorithms, including Dijkstra's and Bellman-Ford algorithms. These algorithms are the backbone of GPS navigation systems and internet routing protocols, helping to find the shortest path between two points.
​
Our exploration of graph theory will also cover essential concepts of graph connectivity and centrality, which help analyze social networks and web pages' relevance, among other applications.
We'll then journey into the domain of graph coloring and matching, exploring how to schedule tasks or allocate resources effectively. For instance, graph coloring techniques are used in assigning frequencies to radio stations, and matching algorithms can help create balanced teams or pairings.
​
Towards the end of the course, we'll explore network flows, which play a significant role in transport networks, job scheduling, and project management. Finally, we'll look at some advanced topics in graph theory, touching upon random graphs, graph drawing, and graph-based machine learning and data mining.