flyada的个人博客分享 http://blog.sciencenet.cn/u/flyada

博文

[转载]二分图(二部图) Bipartite Graph (一)

已有 8722 次阅读 2012-3-14 10:00 |个人分类:授业解惑|系统分类:科研笔记|关键词:二分图| 二分图 |文章来源:转载

设G=(V,E)是一个无向图。如顶点集V可分割为两个互不相交的子集V1,V2之并,并且图中每条边依附的两个顶点都分别属于这两个不同的子集。则称图G为二分图(Bipartite Graph)。

二分图也可记为G=(V1,V2,E)。例如:
                         

表示学生与课程之间关系的二分图SCG,其顶点集由学生集和课程集组成。


图的匹配可形式描述如下:

   给定一个图G=(V,E),若边集E的一个子集M中任意两条边都不依附图中同一顶点,则称M是图的一个匹配(matching),选择这样的边的最大子集称为图的最大匹配问题(maximal matching problem)。  

如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备或完美匹配。
 

反映教师与课程关系的二分图TCG及它的一个最大匹配。

 

 



http://blog.sciencenet.cn/blog-636598-547569.html

上一篇:[转载]史定华老师对一篇文章的评述
下一篇:[转载]【加整理】复杂网络相关参考文献(编年史--2000年)

0

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备14006957 )

GMT+8, 2019-9-23 15:35

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部