Introduction to Graph Theory
Beschreibung
When you enroll for courses through Coursera you get to choose for a paid plan or for a free plan .
- Free plan: No certicification and/or audit only. You will have access to all course materials except graded items.
- Paid plan: Commit to earning a Certificate—it's a trusted, shareable way to showcase your new skills.
About this course: 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 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 …
Frequently asked questions
Es wurden noch keine FAQ hinterlegt. Falls Sie Fragen haben oder Unterstützung benötigen, kontaktieren Sie unseren Kundenservice. Wir helfen gerne weiter!
When you enroll for courses through Coursera you get to choose for a paid plan or for a free plan .
- Free plan: No certicification and/or audit only. You will have access to all course materials except graded items.
- Paid plan: Commit to earning a Certificate—it's a trusted, shareable way to showcase your new skills.
About this course: 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 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.
Created by: University of California, San Diego, Higher School of Economics-
Taught by: Alexander S. Kulikov, Visiting Professor
Department of Computer Science and Engineering
Each course is like an interactive textbook, featuring pre-recorded videos, quizzes and projects.
Help from your peersConnect with thousands of other learners and debate ideas, discuss course material, and get help mastering concepts.
CertificatesEarn official recognition for your work, and share your success with friends, colleagues, and employers.
University of California, San Diego UC San Diego is an academic powerhouse and economic engine, recognized as one of the top 10 public universities by U.S. News and World Report. Innovation is central to who we are and what we do. Here, students learn that knowledge isn't just acquired in the classroom—life is their laboratory. Higher School of Economics National Research University - Higher School of Economics (HSE) is one of the top research universities in Russia. Established in 1992 to promote new research and teaching in economics and related disciplines, it now offers programs at all levels of university education across an extraordinary range of fields of study including business, sociology, cultural studies, philosophy, political science, international relations, law, Asian studies, media and communications, IT, mathematics, engineering, and more. Learn more on www.hse.ruSyllabus
WEEK 1
What is a Graph?
What are graphs? What do we need them for? This week we'll see that a graph is a simple pictorial way to represent almost any relations between objects. We'll see that we use graph applications daily! We'll learn what graphs are, when and how to use them, how to draw graphs, and we'll also see the most important graph classes. We start off with two interactive puzzles. While they may be hard, they demonstrate the power of graph theory very well! If you don't find these puzzles easy, please see the videos and reading materials after them.
14 videos, 5 readings expand
- Video: Airlines Graph
- Video: Knight Transposition
- Video: Seven Bridges of Königsberg
- Reading: Slides
- Video: What is a Graph?
- Notebook: Graph Drawing Example
- Video: Graph Examples
- Video: Graph Applications
- Reading: Slides
- Video: Vertex Degree
- Video: Paths
- Video: Connectivity
- Video: Directed Graphs
- Video: Weighted Graphs
- Reading: Slides
- Video: Paths, Cycles and Complete Graphs
- Video: Trees
- Video: Bipartite Graphs
- Reading: Slides
- Reading: Glossary
Graded: Puzzle: Guarini's Puzzle
Graded: Puzzle: Bridges of Königsberg
Graded: Definitions
Graded: Puzzle: Make a Tree
Graded: Graph Types
WEEK 2
CYCLES
We’ll consider connected components of a graph and how they can be used to implement a simple program for solving the Guarini puzzle and for proving optimality of a certain protocol. We’ll see how to find a valid ordering of a to-do list or project dependency graph. Finally, we’ll figure out the dramatic difference between seemingly similar Eulerian cycles and Hamiltonian cycles, and we’ll see how they are used in genome assembly!
12 videos, 4 readings expand
- LTI Item: Puzzle: Connect Points by Segments
- Video: Handshaking Lemma
- Video: Total Degree
- Reading: Slides
- Video: Connected Components
- Notebook: Connected Components
- Video: Guarini Puzzle: Code
- Notebook: Guarini Puzzle Solver
- Video: Lower Bound
- Video: The Heaviest Stone
- Video: Directed Acyclic Graphs
- Notebook: Topological Sorting
- Video: Strongly Connected Components
- Notebook: Strongly Connected Components
- Reading: Slides
- Video: Eulerian Cycles
- Video: Eulerian Cycles: Criteria
- Notebook: Eulerian Cycles
- Video: Hamiltonian Cycles
- Video: Genome Assembly
- Reading: Slides
- Reading: Glossary
Graded: Computing the Number of Edges
Graded: Number of Connected Components
Graded: Number of Strongly Connected Components
Graded: Eulerian Cycles
Graded: Puzzle: Hamiltonian Cycle
WEEK 3
Graph Classes
This week we will study three main graph classes: trees, bipartite graphs, and planar graphs. We'll define minimum spanning trees, and then develop an algorithm which finds the cheapest way to connect arbitrary cities. We'll study matchings in bipartite graphs, and see when a set of jobs can be filled by applicants. We'll also learn what planar graphs are, and see when subway stations can be connected without intersections. Stay tuned for more interactive puzzles!
11 videos, 4 readings expand
- Video: Road Repair
- Video: Trees
- Video: Minimum Spanning Tree
- Notebook: Minimum Spanning Tree
- Reading: Slides
- Video: Job Assignment
- Video: Bipartite Graphs
- Video: Matchings
- Video: Hall's Theorem
- Notebook: Maximum Matching
- Reading: Slides
- Video: Subway Lines
- Video: Planar Graphs
- Video: Euler's Formula
- Video: Applications of Euler's Formula
- Reading: Slides
- Reading: Glossary
Graded: Puzzle: Road Repair
Graded: Trees
Graded: Puzzle: Job Assignment
Graded: Bipartite Graphs
Graded: Puzzle: Subway Lines
Graded: Planar Graphs
WEEK 4
Graph Parameters
We'll focus on the graph parameters and related problems. First, we'll define graph colorings, and see why political maps can be colored in just four colors. Then we will see how cliques and independent sets are related in graphs. Using these notions, we'll prove Ramsey Theorem which states that in a large system, complete disorder is impossible! Finally, we'll study vertex covers, and learn how to find the minimum number of computers which control all network connections.
14 videos, 5 readings expand
- Video: Map Coloring
- Video: Graph Coloring
- Video: Bounds on the Chromatic Number
- Video: Applications
- Reading: Slides
- Video: Graph Cliques
- Video: Cliques and Independent Sets
- Notebook: Maximum Clique
- Video: Connections to Coloring
- Video: Mantel's Theorem
- Reading: Slides
- Video: Balanced Graphs
- Video: Ramsey Numbers
- Video: Existence of Ramsey Numbers
- Reading: Slides
- Video: Antivirus System
- Video: Vertex Covers
- Video: König's Theorem
- Reading: Slides
- Reading: Glossary
Graded: Puzzle: Map Coloring
Graded: Graph Coloring
Graded: Puzzle: Graph Cliques
Graded: Cliques and Independent Sets
Graded: Puzzle: Balanced Graphs
Graded: Ramsey Numbers
Graded: Puzzle: Antivirus System
Graded: Vertex Covers
WEEK 5
Flows and Matchings
This week we'll develop an algorithm that finds the maximum amount of water which can be routed in a given water supply network. This algorithm is also used in practice for optimization of road traffic and airline scheduling. We'll see how flows in networks are related to matchings in bipartite graphs. We'll then develop an algorithm which finds stable matchings in bipartite graphs. This algorithm solves the problem of matching students with schools, doctors with hospitals, and organ donors with patients. By the end of this week, we'll implement an algorithm which won the Nobel Prize in Economics!
13 videos, 5 readings, 1 practice quiz expand
- Video: An Example
- Video: The Framework
- Video: Ford and Fulkerson: Proof
- Video: Hall's theorem
- Practice Quiz: Constant Degree Bipartite Graphs
- Video: What Else?
- Reading: Slides
- Video: Why Stable Matchings?
- Video: Mathematics and Real Life
- Video: Basic Examples
- Video: Looking For a Stable Matching
- Video: Gale-Shapley Algorithm
- Video: Correctness Proof
- Video: Why The Algorithm Is Unfair
- Video: Why the Algorithm is Very Unfair
- Reading: Slides
- Reading: Gale-Shapley Algorithm
- Reading: Project Description
- Reading: Glossary
Graded: Choose an Augmenting Path Carefully
Graded: Base Cases
Graded: Algorithm
Werden Sie über neue Bewertungen benachrichtigt
Schreiben Sie eine Bewertung
Haben Sie Erfahrung mit diesem Kurs? Schreiben Sie jetzt eine Bewertung und helfen Sie Anderen dabei die richtige Weiterbildung zu wählen. Als Dankeschön spenden wir € 1,00 an Stiftung Edukans.Es wurden noch keine FAQ hinterlegt. Falls Sie Fragen haben oder Unterstützung benötigen, kontaktieren Sie unseren Kundenservice. Wir helfen gerne weiter!