Coursera
Lista de cursos
  • Navegar
  • Pesquisar
  • For Enterprise
  • Entrar
  • Criar conta

Introduction to Graph Theory

Visão geralProgramaPerguntas frequentesDesenvolvedoresCustoClassificações e avaliações

Página inicialCiência da ComputaçãoAlgoritmos

Introduction to Graph Theory

Universidade da Califórnia, San Diego, National Research University Higher School of Economics

Informações sobre o curso: 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.


Desenvolvido por:  Universidade da Califórnia, San Diego, National Research University Higher School of Economics
Universidade da Califórnia, San DiegoNational Research University Higher School of Economics

  • Alexander S. Kulikov

    Ministrado por:  Alexander S. Kulikov, Visiting Professor

    Department of Computer Science and Engineering
Informações básicas
Curso 3 de 5 no Introduction to Discrete Mathematics for Computer Science Specialization
NívelBeginner
Compromisso5 weeks, 3-5 hours/week
Idioma
English
Como ser aprovadoSeja aprovado em todas as tarefas para concluir o curso.
Classificação do usuário
4.7 estrelas
Classificação média do usuário 4.7Veja o que os aprendizes disseram
Programa
SEMANA 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 vídeos, 5 leituras
  1. Vídeo: Airlines Graph
  2. Vídeo: Knight Transposition
  3. Vídeo: Seven Bridges of Königsberg
  4. Reading: Slides
  5. Vídeo: What is a Graph?
  6. Notebook: Graph Drawing Example
  7. Vídeo: Graph Examples
  8. Vídeo: Graph Applications
  9. Reading: Slides
  10. Vídeo: Vertex Degree
  11. Vídeo: Paths
  12. Vídeo: Connectivity
  13. Vídeo: Directed Graphs
  14. Vídeo: Weighted Graphs
  15. Reading: Slides
  16. Vídeo: Paths, Cycles and Complete Graphs
  17. Vídeo: Trees
  18. Vídeo: Bipartite Graphs
  19. Reading: Slides
  20. Reading: Glossary
Nota atribuída: Puzzle: Guarini's Puzzle
Nota atribuída: Puzzle: Bridges of Königsberg
Nota atribuída: Definitions
Nota atribuída: Puzzle: Make a Tree
Nota atribuída: Graph Types
SEMANA 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 vídeos, 4 leituras
  1. LTI Item: Puzzle: Connect Points by Segments
  2. Vídeo: Handshaking Lemma
  3. Vídeo: Total Degree
  4. Reading: Slides
  5. Vídeo: Connected Components
  6. Notebook: Connected Components
  7. Vídeo: Guarini Puzzle: Code
  8. Notebook: Guarini Puzzle Solver
  9. Vídeo: Lower Bound
  10. Vídeo: The Heaviest Stone
  11. Vídeo: Directed Acyclic Graphs
  12. Notebook: Topological Sorting
  13. Vídeo: Strongly Connected Components
  14. Notebook: Strongly Connected Components
  15. Reading: Slides
  16. Vídeo: Eulerian Cycles
  17. Vídeo: Eulerian Cycles: Criteria
  18. Notebook: Eulerian Cycles
  19. Vídeo: Hamiltonian Cycles
  20. Vídeo: Genome Assembly
  21. Reading: Slides
  22. Reading: Glossary
Nota atribuída: Computing the Number of Edges
Nota atribuída: Number of Connected Components
Nota atribuída: Number of Strongly Connected Components
Nota atribuída: Eulerian Cycles
Nota atribuída: Puzzle: Hamiltonian Cycle
SEMANA 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 vídeos, 4 leituras
  1. Vídeo: Road Repair
  2. Vídeo: Trees
  3. Vídeo: Minimum Spanning Tree
  4. Notebook: Minimum Spanning Tree
  5. Reading: Slides
  6. Vídeo: Job Assignment
  7. Vídeo: Bipartite Graphs
  8. Vídeo: Matchings
  9. Vídeo: Hall's Theorem
  10. Notebook: Maximum Matching
  11. Reading: Slides
  12. Vídeo: Subway Lines
  13. Vídeo: Planar Graphs
  14. Vídeo: Euler's Formula
  15. Vídeo: Applications of Euler's Formula
  16. Reading: Slides
  17. Reading: Glossary
Nota atribuída: Puzzle: Road Repair
Nota atribuída: Trees
Nota atribuída: Puzzle: Job Assignment
Nota atribuída: Bipartite Graphs
Nota atribuída: Puzzle: Subway Lines
Nota atribuída: Planar Graphs
SEMANA 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 vídeos, 5 leituras
  1. Vídeo: Map Coloring
  2. Vídeo: Graph Coloring
  3. Vídeo: Bounds on the Chromatic Number
  4. Vídeo: Applications
  5. Reading: Slides
  6. Vídeo: Graph Cliques
  7. Vídeo: Cliques and Independent Sets
  8. Notebook: Maximum Clique
  9. Vídeo: Connections to Coloring
  10. Vídeo: Mantel's Theorem
  11. Reading: Slides
  12. Vídeo: Balanced Graphs
  13. Vídeo: Ramsey Numbers
  14. Vídeo: Existence of Ramsey Numbers
  15. Reading: Slides
  16. Vídeo: Antivirus System
  17. Vídeo: Vertex Covers
  18. Vídeo: König's Theorem
  19. Reading: Slides
  20. Reading: Glossary
Nota atribuída: Puzzle: Map Coloring
Nota atribuída: Graph Coloring
Nota atribuída: Puzzle: Graph Cliques
Nota atribuída: Cliques and Independent Sets
Nota atribuída: Puzzle: Balanced Graphs
Nota atribuída: Ramsey Numbers
Nota atribuída: Puzzle: Antivirus System
Nota atribuída: Vertex Covers
SEMANA 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 vídeos, 6 leituras, 1 questionário de prática
  1. Vídeo: An Example
  2. Vídeo: The Framework
  3. Vídeo: Ford and Fulkerson: Proof
  4. Vídeo: Hall's theorem
  5. Practice Quiz: Constant Degree Bipartite Graphs
  6. Vídeo: What Else?
  7. Reading: Slides
  8. Vídeo: Why Stable Matchings?
  9. Vídeo: Mathematics and Real Life
  10. Vídeo: Basic Examples
  11. Vídeo: Looking For a Stable Matching
  12. Vídeo: Gale-Shapley Algorithm
  13. Vídeo: Correctness Proof
  14. Vídeo: Why The Algorithm Is Unfair
  15. Vídeo: Why the Algorithm is Very Unfair
  16. Reading: Slides
  17. Reading: The algorithm and its properties (alternative exposition)
  18. Reading: Gale-Shapley Algorithm
  19. Reading: Project Description
  20. Reading: Glossary
Nota atribuída: Choose an Augmenting Path Carefully
Nota atribuída: Base Cases
Nota atribuída: Algorithm

Perguntas frequentes
Como funciona
Coursework
Coursework

Each course is like an interactive textbook, featuring pre-recorded videos, quizzes and projects.

Help from Your Peers
Help from Your Peers

Connect with thousands of other learners and debate ideas, discuss course material, and get help mastering concepts.

Certificates
Certificates

Earn official recognition for your work, and share your success with friends, colleagues, and employers.

Desenvolvedores
Universidade da Califórnia, 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.
National Research University 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.ru
Custo
Comprar curso
Acesso aos materiais do curso

Disponível

Acesso a materiais valendo nota

Disponível

Receba uma nota final

Disponível

Obtenha um Certificado de Curso compartilhável

Disponível

Classificações e avaliações
Avaliado em 4.7 de 5 decorrente de 62 avaliações

徐

很好,很清楚

Edward Patrick vogel

I have been reading and buying books on Graph Theory in the hopes of finding some interesting insights I could bring to my after school students. None of them had Guarini's Puzzle which really is a beautiful and succinct example of Graph Theory in action. Hoping we can use what I am learning here to develop some rigorous graph methods for finding the solutions to tiling polyominoes and packing the SOMA cube. We like to make build physical objects as a starting off point for study. (leonardosbasement.org).

I am enjoying the "try this" before "we explain everything" approach also. Solving problems in python notebook is also great.

T

This course is interesting, and it is a good introduction. I like the first four weeks' courses, while I feel the last week's course is not clear presented, which changes the instructor.

lt

A good course with proper explanation. The mathematical proof of this course is generally easy to understand although a small part of them are vague



Talvez você também goste de
Universidade da Califórnia, San Diego, National Research University Higher School of Economics
Number Theory and Cryptography
1 curso
Universidade da Califórnia, San Diego, National Research University Higher School of Economics
Number Theory and Cryptography
Visualizar curso
Universidade da Califórnia, San Diego, National Research University Higher School of Economics
Combinatorics and Probability
1 curso
Universidade da Califórnia, San Diego, National Research University Higher School of Economics
Combinatorics and Probability
Visualizar curso
Universidade da Califórnia, San Diego, National Research University Higher School of Economics
Delivery Problem
1 curso
Universidade da Califórnia, San Diego, National Research University Higher School of Economics
Delivery Problem
Visualizar curso
University of Colorado System
Symmetric Cryptography
1 curso
University of Colorado System
Symmetric Cryptography
Visualizar curso
University of Colorado System
Asymmetric Cryptography and Key Management
1 curso
University of Colorado System
Asymmetric Cryptography and Key Management
Visualizar curso
Coursera
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
Baixar na App StoreBaixar no Google Play
  • Coursera
  • Sobre
  • Liderança
  • Carreiras
  • Lista de cursos
  • Certificados
  • Notas
  • Para negócios
  • For Government
  • Comunidade
  • parceiros
  • Orientadores
  • Tradutores
  • Desenvolvedores
  • Testadores beta
  • Conectar
  • Blog
  • Facebook
  • LinkedIn
  • Twitter
  • Google+
  • Tech Blog
  • Mais
  • Termos
  • Privacidade
  • Ajuda
  • Acessibilidade
  • Imprensa
  • Contato
  • Diretório
  • Afiliados