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 problemsolving 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

DepthFirst Search (DFS)

BreadthFirst Search (BFS)

Topological sorting
Path Algorithms

Dijkstra's algorithm

BellmanFord algorithm

FloydWarshall 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

FordFulkerson algorithm

EdmondsKarp 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 DepthFirst Search (DFS) and BreadthFirst 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 BellmanFord 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 graphbased machine learning and data mining.