|
所在平台: Coursera |
课程主页: https://www.coursera.org/learn/graphs
课程评论：没有评论
课程名称：图论简介 概述：欢迎您踏上图论的迷人旅程——这一领域将绘画的优雅与数学的严谨相连接。图论不仅简单而且富有深度，提供了一种直观的方式来描绘许多重要的数学结果，并为它们背后的深刻理论提供了洞见。在这门在线课程中，我们将探索图论的诸多有趣应用，包括GPS系统如何寻找最短路径、工程师如何设计集成电路、以及生物学家如何组装基因组等。 课程大纲： 1. **什么是图？** 本周我们将探讨图的定义及其用途。图是一种简单的图形方式，能够表示对象之间的关系。我们每天都在使用图的应用！将学习图的基本概念、使用场景、绘制方法，以及最重要的图的类别。通过两个互动难题开始课程，这些难题虽然具有挑战性，但很好地展示了图论的强大。如果你发现这些难题难度较大，可以查看后续的视频和阅读材料。 2. **周期** 本周我们将考虑图的连通分量及其在解决Guarini难题和证明某一协议最优性方面的应用。我们将学习如何找到待办事项或项目依赖图的有效排序。最后，我们将揭示表面相似的欧拉循环和哈密尔顿循环之间的巨大差异，并探讨它们在基因组组装中的应用。 3. **图的类别** 本周我们将研究三种主要的图类别：树、二分图和平面图。我们将定义最小生成树，并发展一个算法来找到连接任意城市的最便宜方法。我们将研究二分图中的匹配，并探讨何时可以用申请者填补一组工作岗位。此外，我们将学习平面图，以及何时能够在不交叉的情况下连接地铁站。 4. **图的参数** 本周我们将专注于图参数及相关问题。首先，我们将定义图的着色，并探讨为何政治地图可以用四种颜色着色。接下来，我们将研究图中团体和独立集之间的关系，并证明拉姆齐定理，表明在大型系统中完全混乱是不可能的！最后，我们将学习顶点覆盖，了解如何找到控制所有网络连接的最小计算机数量。 5. **流与匹配** 本周我们将开发一个算法，寻找在给定水供应网络中可以传输的最大水量。这个算法在实际中同样适用于道路交通和航空调度的优化。我们将观察网络中的流与二分图中的匹配之间的关系，并制定一个算法，寻找二分图中的稳定匹配。该算法解决了学生与学校、医生与医院、器官捐赠者与患者之间的匹配问题。到本周结束时，我们将实现一个获得诺贝尔经济学奖的算法！ 这门课程将带领您深入图论的世界，探索其美妙的实际应用和理论基础。
Name:What is a Graph?
Description: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.
Name:Cycles
Description: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!
Name:Graph Classes
Description: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!
Name:Graph Parameters
Description: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.
Name:Flows and Matchings
Description: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!
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 ge
