用图形解释10种图形算法( 三 ) 快速介绍

图的色数是为图着色所需的最少颜色数。
图9显示了使用4种颜色的示例图的顶点着色。
演算法· 使用广度优先搜索或深度优先搜索的算法
· 贪婪的着色
应用领域· 用于安排时间表。
· 用于分配移动无线电频率。
· 用于建模和求解数独游戏。
· 用于检查图是否为二部图。
· 用于为相邻国家或地区具有不同颜色的国家或州的地理地图着色。
文章插图
> Image by TheAndrasBarta from Pixabay
9.最大流量
文章插图
> Fig 10. Determining the maximum flow (Image by Author)
我们可以将图建模为以边权重为流量的流量网络。在最大流量问题中，我们必须找到一条可以获得最大可能流量的流路。
图10显示了确定网络的最大流量并确定最终流量值的动画示例。
演算法· 福特-福克森算法
· Edmonds–Karp算法
· Dinic的算法
应用领域· 用于航空公司调度以调度飞行人员。
· 用于图像分割以查找图像中的背景和前景。
· 用于淘汰无法赢得足够比赛来赶上其所在部门的领先者的棒球队。
10.匹配
文章插图
> Fig 11. Matching of a bipartite graph (Image by Author)
图中的匹配项是一组没有共同顶点的边（即，没有两个边共享共同的顶点）。如果匹配包含尽可能多的与尽可能多的顶点匹配的边，则该匹配称为最大匹配。
图11显示了获得二部图与橙色和蓝色表示的两组顶点的完全匹配的动画。
演算法· Hopcroft-Karp算法
· 匈牙利算法
· 开花算法
应用领域· 用于对接会以匹配新娘和新郎（稳定的婚姻问题）。
· 用于确定顶点覆盖率。
· 在运输理论中用于解决资源分配和出行优化中的问题。
最后的想法我希望您觉得这篇文章对图形算法进行简单而概括的介绍很有用。我很想听听您的想法。
非常感谢您的阅读。
干杯!
【用图形解释10种图形算法】(本文翻译自Vijini Mallawaarachchi的文章《10 Graph Algorithms Visually Explained》，参考：)