Buy Now AED 274.99 + VAT

Monthly Subscription Starting at AED 99 + VAT

Introduction to Graph Theory
  • Level Foundation
  • Duration 21 hours
  • Course by University of California San Diego
  • Offered by

About

We invite you to a fascinating journey into Graph Theory " an area which connects the elegance of painting and the rigor of mathematics; is simple, but not unsophisticated. Graph Theory gives us, both an easy way to pictorially represent many major mathematical results, and insights into the deep theories behind them. In this online course, among other intriguing applications, we will see how GPS systems find shortest routes, how engineers design integrated circuits, how biologists assemble genomes, why a political map can always be colored using a few colors. We will study Ramsey Theory which proves that in a large system, complete disorder is impossible! By the end of the course, we will implement an algorithm which finds an optimal assignment of students to schools. This algorithm, developed by David Gale and Lloyd S. Shapley, was later recognized by the conferral of Nobel Prize in Economics. As prerequisites we assume only basic math (e.g., we expect you to know what is a square or how to add fractions), basic programming in python (functions, loops, recursion), common sense and curiosity. Our intended audience are all people that work or plan to work in IT, starting from motivated high school students.

Modules

Warm-up

    • 3 Videos
    • 1 Readings
    • 2 Assignment
Show info about module content

2 Assignment

  • Puzzle: Guarini's Puzzle
  • Puzzle: Bridges of Königsberg

3 Videos

  • Airlines Graph
  • Knight Transposition
  • Seven Bridges of Königsberg

1 Readings

  • Slides

Why Graphs?

    • 3 Videos
    • 1 Readings
    • 1 Lab
Show info about module content

1 Labs

  • Graph Drawing Example

3 Videos

  • What is a Graph?
  • Graph Examples
  • Graph Applications

1 Readings

  • Slides

Basic Definitions

    • 5 Videos
    • 1 Readings
    • 1 Assignment
Show info about module content

1 Assignment

  • Definitions

5 Videos

  • Vertex Degree
  • Paths
  • Connectivity
  • Directed Graphs
  • Weighted Graphs

1 Readings

  • Slides

Basic Graphs

    • 3 Videos
    • 3 Readings
    • 2 Assignment
Show info about module content

2 Assignment

  • Puzzle: Make a tree
  • Graph Types

3 Videos

  • Paths, Cycles and Complete Graphs
  • Trees
  • Bipartite Graphs

3 Readings

  • Slides
  • Glossary
  • Hint for Guarini's Puzzle

Handshaking Lemma

    • 2 Videos
    • 1 Readings
    • 2 Assignment
Show info about module content

2 Assignment

  • Puzzle: Connect Points by Segments
  • Computing the Number of Edges

2 Videos

  • Handshaking Lemma
  • Total Degree

1 Readings

  • Slides

Connected Components

    • 6 Videos
    • 1 Readings
    • 4 Lab
    • 2 Assignment
Show info about module content

2 Assignment

  • Number of Connected Components
  • Number of Strongly Connected Components

4 Labs

  • Connected Components
  • Guarini Puzzle Solver
  • Topological Sorting
  • Strongly Connected Components

6 Videos

  • Connected Components
  • Guarini Puzzle: Code
  • Lower Bound
  • The Heaviest Stone
  • Directed Acyclic Graphs
  • Strongly Connected Components

1 Readings

  • Slides

Eulerian and Hamiltonian Cycles

    • 4 Videos
    • 2 Readings
    • 1 Lab
    • 3 Assignment
Show info about module content

3 Assignment

  • Eulerian Cycles
  • Puzzle: Plow Truck
  • Puzzle: Hamiltonian Cycle

1 Labs

  • Eulerian Cycles

4 Videos

  • Eulerian Cycles
  • Eulerian Cycles: Criteria
  • Hamiltonian Cycles
  • Genome Assembly

2 Readings

  • Slides
  • Glossary

Trees

    • 3 Videos
    • 1 Readings
    • 1 Lab
    • 2 Assignment
Show info about module content

2 Assignment

  • Puzzle: Road Repair
  • Trees

1 Labs

  • Minimum Spanning Tree

3 Videos

  • Road Repair
  • Trees
  • Minimum Spanning Tree

1 Readings

  • Slides

Bipartite Graphs

    • 4 Videos
    • 1 Readings
    • 1 Lab
    • 2 Assignment
Show info about module content

2 Assignment

  • Puzzle: Job Assignment
  • Bipartite Graphs

1 Labs

  • Maximum Matching

4 Videos

  • Job Assignment
  • Bipartite Graphs
  • Matchings
  • Hall's Theorem

1 Readings

  • Slides

Planar Graphs

    • 4 Videos
    • 2 Readings
    • 2 Assignment
Show info about module content

2 Assignment

  • Puzzle: Subway Lines
  • Planar Graphs

4 Videos

  • Subway Lines
  • Planar Graphs
  • Euler's Formula
  • Applications of Euler's Formula

2 Readings

  • Slides
  • Glossary

Graph Coloring

    • 4 Videos
    • 1 Readings
    • 2 Assignment
Show info about module content

2 Assignment

  • Puzzle: Map Coloring
  • Graph Coloring

4 Videos

  • Map Coloring
  • Graph Coloring
  • Bounds on the Chromatic Number
  • Applications

1 Readings

  • Slides

Cliques and Independent Sets

    • 4 Videos
    • 1 Readings
    • 1 Lab
    • 2 Assignment
Show info about module content

2 Assignment

  • Puzzle: Graph Cliques
  • Cliques and Independent Sets

1 Labs

  • Maximum Clique

4 Videos

  • Graph Cliques
  • Cliques and Independent Sets
  • Connections to Coloring
  • Mantel's Theorem

1 Readings

  • Slides

Ramsey Numbers

    • 3 Videos
    • 1 Readings
    • 2 Assignment
Show info about module content

2 Assignment

  • Puzzle: Balanced Graphs
  • Ramsey Numbers

3 Videos

  • Balanced Graphs
  • Ramsey Numbers
  • Existence of Ramsey Numbers

1 Readings

  • Slides

Vertex Cover

    • 3 Videos
    • 2 Readings
    • 2 Assignment
Show info about module content

2 Assignment

  • Puzzle: Antivirus System
  • Vertex Covers

3 Videos

  • Antivirus System
  • Vertex Covers
  • König's Theorem

2 Readings

  • Slides
  • Glossary

Networks, Flows, and Cuts

    • 5 Videos
    • 1 Readings
    • 2 Assignment
Show info about module content

2 Assignment

  • Choose an Augmenting Path Carefully
  • Constant Degree Bipartite Graphs

5 Videos

  • An Example
  • The Framework
  • Ford and Fulkerson: Proof
  • Hall's theorem
  • What Else?

1 Readings

  • Slides

Stable Matchings

    • 8 Videos
    • 2 Readings
Show info about module content

8 Videos

  • Why Stable Matchings?
  • Mathematics and Real Life
  • Basic Examples
  • Looking For a Stable Matching
  • Gale-Shapley Algorithm
  • Correctness Proof
  • Why The Algorithm Is Unfair
  • Why the Algorithm is Very Unfair

2 Readings

  • Slides
  • The algorithm and its properties (alternative exposition)

The Project: Programming Gale-Shapley Algorithm

    • 3 Readings
    • 2 Assignment
Show info about module content

2 Assignment

  • Base Cases
  • Algorithm

3 Readings

  • Gale-Shapley Algorithm
  • Project Description
  • Glossary

Auto Summary

Explore the captivating world of Graph Theory with this foundational course from Coursera, led by expert instructors. Ideal for IT and Computer Science enthusiasts, it covers practical applications such as GPS routing, circuit design, and genome assembly. With a duration of 1260 minutes, the course requires basic math and Python knowledge. Subscription options include Starter, Professional, and Paid plans, making it accessible for motivated high school students and professionals alike.

Alexander S. Kulikov
Instructors

Alexander S. Kulikov

Владимир Подольский
Instructors

Владимир Подольский