上节回顾 ▣内容1:Dijkstra算法 口内容2:Floyd-Warshall算法 ▣内容3:旅行商问题(TSP) ▣内容4:最大流问题
内容1:Dijkstra算法 内容2:Floyd-Warshall算法 内容3:旅行商问题(TSP) 内容4:最大流问题* 上节回顾
二部图(bipartite graph,偶图) 二部图:顶点集划分为2个类别(不相交),边的端点 在不同类别中。 口完全二部图:来自不同类别的两个顶点均有边。 G K23 K33
二部图(bipartite graph,偶图) 二部图:顶点集划分为2个类别(不相交),边的端点 在不同类别中。 完全二部图:来自不同类别的两个顶点均有边。 K2,3 G K3,3
图中的匹配 匹配(边独立集):互不相邻的边的集合 口M-饱和点:匹配M中各边的端点 匹配数 匹配数 B1=3 β=4 极大匹配 完美匹配 最大匹配 M饱和点 ●M-饱和点
匹配(边独立集):互不相邻的边的集合 M-饱和点:匹配M中各边的端点 匹配数 1=3 匹配数 1=4 极大匹配 最大匹配 完美匹配 M-饱和点 M-饱和点 图中的匹配
本节提要 口问题1:什么是二部图及其匹配? 口两个无内部边的顶点集;互不相邻的边的集合 口问题2:二部图中的有哪些匹配?
问题1:什么是二部图及其匹配? 两个无内部边的顶点集;互不相邻的边的集合 问题2:二部图中的有哪些匹配? 本节提要