Graphs and Networks

Birla Institute Of Technology And Science–Pilani (BITS–Pilani) via Coursera

Go to class Write review

Details

Go to class

Provider

Coursera
Pricing

Paid Course
Languages

English
Certificate

Paid Certificate Available
Duration & workload

1 day 19 hours 43 minutes
Sessions

On-Demand
Subtitles

English

Found in

Overview

Coursera Flash Sale

40% Off Coursera Plus for 3 Months!

Grab it

Master the mathematical and computational foundations of graph theory and network analysis in this comprehensive course for problem-solvers and analytical thinkers. Explore how graphs model real-world systems—such as social networks, transportation grids, communication systems, and biological pathways. Begin with core concepts like graph properties, connectivity, and planarity, then advance to topics like graph coloring, matching algorithms, network flows, and optimization. Learn to design efficient algorithms, analyze centrality measures, compute maximum flows, and solve minimal cost flow problems. Through mathematical rigor and practical application, you’ll develop both theoretical insight and hands-on problem-solving skills. Applications span scheduling, frequency assignment, image processing, artificial intelligence, and machine learning. Ideal for aspiring researchers, data scientists, and network engineers, this course equips you with essential tools to analyze, optimize, and visualize interconnected systems across diverse domains.

Syllabus

Introduction to Graphs & Networks

In this module, you will get a comprehensive introduction to graph theory, emphasizing both the practical importance of graphs in real-world scenarios and the fundamental mathematical concepts underpinning them. The module consists of two lessons: the first addresses why graphs are essential tools for understanding and solving complex problems across diverse fields. The second lesson delves into the formal definitions of graphs, introducing students to key graph-theoretical terms and concepts such as vertices, edges, adjacency, incidences, degree sequences, directed graphs, isomorphism, and graph representations.

Connectivity and Reachability

In this module, you will learn about the critical concepts of connectivity and reachability within both undirected and directed graphs, which are fundamental for understanding how vertices are connected. The module consists of two lessons: the first addresses the concepts related to undirected graph connectivity, like vertex connectivity, edge connectivity, and the relation between them. It also gives an alternate view of connectivity through disjoint paths and local connectivity. The second lesson addresses the concepts related to directed graph connectivity, like weak and strong connectivity, oriented graphs, and strong tournaments.

Planar Graphs

In this module, you will learn about an important graph class, namely planar graphs. The module consists of two lessons: the first introduces and discusses planar graphs, planar drawings, and planar embeddings, their characterisation and properties, and various classes of planar graphs, like maximal plane graphs and outerplanar graphs. The second lesson addresses concepts and properties of dual graphs, a graph associated with any plane graph, like the relation between graph elements of primal and dual graphs, self-dual graphs, and the relationship between bipartite graphs and their dual.

Graph Parameters

In this module, you will learn about several important graph parameters, namely colouring, independent set, clique, matching, and domination. The module consists of two lessons: the first introduces the famous problem of map colouring and how it relates to vertex colouring of a planar graph. Furthermore, it introduces independent sets and cliques of a graph and how they relate to vertex colouring, as well as discusses various bounds and relationships among these parameters. The second lesson introduces matching and domination and discusses a few of their properties.

Real World Networks

In this module, you’ll learn about representing real-world scenarios using networks, delving into their applications across diverse domains. You’ll explore the fundamental differences between graphs and networks, understand how networks capture complex relationships, and examine examples like social networks, transportation systems, and biological networks. Additionally, you’ll study the mathematical models that describe their structure and behavior, providing a foundation for analyzing real-world connectivity and interactions.

Network Analysis Measures

In this module, you’ll explore key measures and properties used to analyze and understand networks. Learn how to assess the degree of connectivity between nodes and apply various classes of measures to uncover meaningful insights tailored to different network applications.

Network Flows

This module explores network flow concepts and optimization algorithms, including the min-max principle. You’ll gain practical skills in modeling transport networks, optimizing node-to-node connections, and applying effective matching strategies in flow networks.

Minimal Cost Flow in a Network

This module delves into techniques for solving minimal cost flow problems in networks. You’ll learn key algorithms such as the Successive Shortest Path and Cycle-Cancelling methods, and explore practical examples of their application. The module also introduces the Network Simplex Algorithm and demonstrates the use of linear programming solvers for optimizing network flows.

Matchings in Graphs & Networks

This module focuses on matchings within graphs and networks, providing insights into their structure and functionality. You’ll learn to model graphs, identify matchings, and apply optimal node-to-node correspondence strategies. The module also covers advanced techniques for implementing matching strategies in flow networks.

Applications of Graphs & Networks

In this module, you will learn about various applications and a few advanced topics of graphs and networks. The module consists of two lessons: the first addresses applications of graphs and networks to various topics and fields like Image Processing, Pattern Recognition, Economics, Biological Networks, AI, and ML. The second lesson introduces a few advanced topics and gives an insight into these topics by giving a few examples of the type of questions researchers study in these area.