1 二部图与匹配
二部图与匹配 1
上节回顾 ▣内容1：Dijkstra算法 口内容2：Floyd-Warshall算法 ▣内容3：旅行商问题(TSP) ▣内容4：最大流问题
内容1：Dijkstra算法 内容2：Floyd-Warshall算法 内容3：旅行商问题（TSP） 内容4：最大流问题* 上节回顾
本节提要 口问题1：什么是二部图及其匹配？ 口问题2：二部图中的有哪些匹配？
问题1：什么是二部图及其匹配？ 问题2：二部图中的有哪些匹配？ 本节提要
二部图(bipartite graph,偶图) 二部图：顶点集划分为2个类别（不相交），边的端点 在不同类别中。 口完全二部图：来自不同类别的两个顶点均有边。 G K23 K33
二部图(bipartite graph，偶图) 二部图：顶点集划分为2个类别(不相交)，边的端点 在不同类别中。 完全二部图：来自不同类别的两个顶点均有边。 K2,3 G K3,3
二部图的判定 口C6是否是二部图？ ·二种颜色对顶点着色，相邻顶点赋以不同颜色 二部图？
二部图的判定 C6是否是二部图？ ⚫ 二种颜色对顶点着色，相邻顶点赋以不同颜色 二部图？