离散数学是计算机科学的基础理论，离散结构的基础知识和逻辑思维的形式化是信息技术类学生的基本功，离散数学的基本概念是理科专业学生进行信息类课程学习的重要基础。 本课程介绍计算机科学和信息技术理论基础的概念和思想方法，介绍数理逻辑、集合论、图论、抽象代数和形式语言与自动机等各部分的基本概念，介绍离散数学基本概念和空间信息技术之间的联系与结合，培养学生理解和掌握离散数学基本概念，采用形式化方法分析问题，并能自觉运用逻辑分析、结构层次分析和同构类比等思想方法解决问题的能力。
66-二分图
Loading...
Do curso por Peking University
离散数学概论 Discrete Mathematics Generality
137 ratings
Conheça os instrutores
陈斌副教授
北京大学
[音乐] 嗨，欢迎回来。
下面我们来讨论几种特殊图。
首先呢是所谓的二分图，那么二分图呢从字面上看来，
我们可以想象它是长成什么样子的，可能是一个图一分为二，是吧，是这样子的。
我们来看看它具体的这个定义。
二分图呢是满足这些条件的一个无向图。
G等于V，E，那么这个无向图呢是这样， 它这个V的这个顶点集合能够被分成两部分，
这个X，Y，这个X，Y呢首先是非空，第二呢X，Y的并集等于V，
第三呢X交Y等于空，那么这个概念是我们很熟悉的概念，
就是非空，不空，不漏，不交，那这个是什么概念呢？
就是X，Y呢是对V的一个划分，是吧，X是
一个划分单元，Y呢也是一个划分单元，就是说对于这个顶点V做了一个划分，分成
两个这个划分单元。
划分完了以后，那么我们再来看E，它的边都有什么样的性质。
那么对于这个每条边，Vi到Vj这个每条边，
都有这样的一个性质，就是Vi属于X，Vj属于Y，或者呢Vi属于Y，
并且Vj属于X，那么这个总 的话来说呢，就是说所有的边，它的两个端点，
都在这个X，Y，都在不同的这个划分单元里， 就是每条边，它的端点都落在不同的这个划分单元里头。
这种呢就叫做二分图，那么所以呢我们可以再回头补充一下刚才我们的想象，
那么二分图呢就是把这个V分成了X，Y，就是
上面有一排的顶点，下面有一排的顶点，然后呢所有的边呢就好像
搭桥一样，在这个两端的两排顶点之间拉这个边， 对，这就是二分图啦。
那么因为二分图呢有X，Y这样的一个划分，所以呢
我们可以用一种特殊的这种形式来表示二分图，就是X，E，Y，这就代表说
一部分的顶点在X，一部分的顶点在Y，然后呢E呢是在连接 这个X，Y之间的顶点的这些边，所以呢可以这么来表示一个二分图。
那么进一步地，如果说这个X，Y 这个集合当中，任意两个顶点
之间都存在边，我们就把它称之为完全的二分图，
这跟完全图的定义是不一样的，虽然它相近，就是说任意两个顶点都有边，
但是呢完全二分图是说X，Y之间，它任意两个顶点之间都有边，
这就是完全二分图，那么完全二分图可以记成Kmn，这个m呢就是
这个X的基数，n呢就是Y的基数，所以呢如果是K22，那么就是一个
两个顶点，下面两个顶点，然后它们之间有，所有的，有四条边，这样的就叫Kmn。
那么我们来看看几个，这个二分图的例子，
当然，这个典型的二分图，就是刚才我们想象的那样，是右上角这张，上面有两个顶点，下面- 有三个顶点，
然后呢所有的边都在上下这个两群顶点之间进行
连接，当然这个呢是属于叫做K23，它是一个完全二分图，
当然并不是所有的二分图都应该画成像右上角这个样子，
它也可以有别的不同的样子，比如说左边，左边这个图， 它是一个3和3
的，就是X的基数是3个顶点，然后Y呢也是3个顶点， 这么一个二分图，但是呢它画成却完全不像右上角那样的，
但是我们也可以把它提取出来，一种颜色 蓝色的就是X，比如说黑色的就是Y，所以呢所有的边都在
都只在这个蓝色顶点和黑色顶点之间才有边， 那么同色的顶点之间是没有边的，所以它也可以画成这个样子，
所以就是这种同构性我们需要观察清楚，并不是所有的
这个二分图都应该画成右上角的那个样子，当然我们为了帮助理解可以画成那样，但是我们
也需要说去识别出一些特殊画法的这种二分图。
当然像右下角这个图呢，它就不是一个二分图，因为它
它这个边呢，是在每个，任意两个顶点之间之间都有边，所以它不是一个二分图。
那么二分图呢有一个等价的判定条件，
就是一个图G，如果它是一个二分图的话，那么当且仅当G
首先至少要有两个顶点，其次呢，G当中所有的回路的长度都应该是偶数，
长度都是偶数，这个我们粗粗的理解来说呢，就是说做一个回路，从X出发，
那么到Y，它只能到Y，那么如果要回路的话它必须要回来， 那么一去一回，它就是一对，就是一个偶数对吧，再一去再一回，
就不管你有多少次，那么有去呢就必须要有回， 从X这个集合出发，那么就必须要回到X的话，那么
就要有去有回，那这样自然它的这个回路的长度都是偶数了。
当然，我们要来进行证明，首先这个是必要性，
必要性也就是说，如果一个图G是二分图的话，那么它首先至少要有两个顶点，那肯定
你如果只有一个顶点，那就不够分的，所以至少要有两个顶点，而且呢，所有的
回路的长度都是偶数，那么你如果已经是一个二分图了，那么有去有回呢，
这个长度肯定是一个偶数，我们需要证明的呢是它的充分性， 也就是一个图如果它至少有两个顶点，而且呢在
这个图当中，所有的回路的长度都是偶数的话，那么它一定会是一个二分图。
那么这种充分性的证明我们可以通过构造X，Y两个集合来进行证明。
首先呢我们进行构造，然后再进行证明，构造怎么构造，我们在
G的V当中任意取一个顶点，小v，那么我们这个
构造一个v1，这个v1呢就是所有跟v的距离为偶数的这些顶点
vi全部都收集在一起，称之为一个v1，然后呢v2呢就等于v减去v1
剩下的那些顶点，那这样呢我们就有了v的一个划分，有一个v的划分。
我们接下来就来证明说，这样的一个划分呢就正好是它的二分图的这个X，Y
我们就要证明说V1，V2的内部的顶点之间没有边。
就是所有的边呢，它都不可能说两个端点同时落在V1，或者同时落在V2里面。
我们用反证法来证明它，那么假设呢它内部顶点之间存在边，
那么也就是说有一个vi，vj这条边，那么vi，vj呢都是属于
V1的，当然这个属于V1或者属于V2这个没有什么太大 的区别，我们就不妨设它是属于V1的，都在V1里边。
那么这样呢，我们从这个任意选取的这个顶点v开始，
然后出发，到vi，到vj，它都有这个 路径，都有路径，那么这个通路呢，是说
因为构造这个v1的时候，它的条件就是它的距离都是偶数， 所有的距离都是偶数，那么这样呢，
v到vi，v到vj，两个呢，长度都是偶数， 那么再加上vi到vj假设有边的话，那么它的长度为1，
那么这样呢从v出发，先到vi，再到vj，再从vj回到v，那么这是一个回路，
那么这个回路的长度呢就是偶数加1再加偶数， 那么显然两个偶数的和是偶数，再加上1就变成奇数了，
那么这样呢就存在了一个回路的长度是奇数，那这个跟我们 需要的条件，我们刚才，我们证明所设定的这个条件
就是所有的回路都是长度，长度都是偶数这么一个条件是相矛盾的， 那么这个矛盾的发生就是因为我们假设说
V1，V2这个内部顶点之间是有边的，所以呢这个假设是不成立的，
所以呢我说G呢它一定是一个二分图， 也就是它的划分，V1，V2这样的划分，
变成了X，Y，所以这个，构造出一个二分图来。
那么二分图呢有什么样的一些应用？当然首先呢我们来看看一个很小的
趣味的应用，称之为分组交谈。
分组交谈它的应用背景是这样，就是出席这个国际会议的成员有6个人， a，b，c，d，e，f六个人，然后他们每个人所掌握的语言
的情况是这样的，比如说a他会用汉语，用法语，也会用日语，
然后呢b呢会用德语，用日语，会用俄语，那这样的话实际上a和b之间他就可以
直接交谈，而不需要通过翻译，对吧，可以直接交谈， 那么像c，像d，像e，像f，
那么这样呢我们就可以，他们在两个成员之间如果可以直接交谈的话，
那么就给他画一条边，那么就形成了右边这样的一个图，这样的一个图，
那么现在呢，说能不能说，有没有可能，这六个人可以被分成两组，
然后在组内之间，这任意两个人之间呢都不能够直接交谈，
那么这个呢就是一个典型的一个二分图的问题。
那么我们当然说，如果说这么一个图， 它能够被划分，所谓的六个人被划分成两个集合，
然后所有的边都存在于两个集合之间，而集合内部没有边的话，
那么它就是组内的成员就不能够直接交谈，而判定的这个条件，就刚才，我们刚刚证明
了这个定理，如果所有的回路，长度都是偶数，那么它就一定是一个二分图，就一定会存在- 这么一个
划分，所以呢，我们来观察这个图，我们发现呢，它的所有的这个回路的长度，
都是偶数，那么所以呢它是一定是一个二分图，那么既然是二分图，我们就可以迅速地找出
这个划分，比如说任意的，从b出发，我们距离b
路径的长度是偶数的有c，有d，所以呢b，c，d被划分成一组，
所以呢在b，c，d当中，b，c，d这三个人之间是不能够直接交谈的， 那么a，e，f这三个人之间也不能够直接交谈，所有的直接
交谈都发生在组和组之间。
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
