二部图又叫二分图,是图论中的一种特殊模型,是指顶点集可分割为两个互不相交的子集,并且图中每条边依附的两个顶点都分属于这两个互不相交的子集,两个子集内的顶点不相邻。
判断二部图的常见方法是染色法:对任意一未染色的顶点染色,判断其相邻的顶点中,若未染色则将其染上和相邻顶点不同的颜色, 若已经染色且颜色和相邻顶点的颜色相同,则说明不是二部图,若颜色不同则继续判断,直到全部染上色。
1、匹配不同:V1中每个顶点至少关联t(t>0)条边,袭仔乱V2中每个顶点至多关联t条边,则G中存在V1到V2的完备匹配。
2、条件不同:Hall定理中的条件为相异性条件,满足t条件的二部图,一定满足相异性条件,事实上V1中k个顶点至少关联 kt条边,这 kt条边至少关联V2中的k个顶点,于是若G满足t条件,则G一定满拍档足相异性条件,但反之不真。
3、性质不同:若能将无向图G= 的顶点集V划分成两个子集 V1和V2(V1交V2为空集),使得G中任何一条边的两个端点一个属于V1,另一个属于V2,则称G为二部图(也称偶图),V1、V2称为互补顶点子集,此时可将G记成G= . 。
扩展资料:
注意事项:
离散数学不同于其它数学课程,不仅在研究对象和研究方法上与普通数学有较大差异,而且在内容结构上随计算机科学的发展而变化,不及连续数学课程完整与稳定,因而对已习惯于连续数学学习的师生而言戚明教学难度大,其中最大的问题是形散、神也散。
离散数学课程本身就是由多门数学分支组成,每个分支基本上可看成一门独立的研究领域,这些分支一方面相互独立,另一方面相互联系,但联系不及连续数学中的关系明显,教师没有从学生的认知规律出发,去挖掘教学内容、揭示知识内涵,课堂教学中缺乏知识点间联系的线条。
-离散数学
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=205;
int flag[N];
int map[N][N];
int match[N];
bool link[N];
int n,m;
int bfs()
{
int j;
memset(flag,-1,sizeof(flag));
for(j=1;j<=n;j++)
{
if(flag[j]!=-1) continue;
queue<int> q;
flag[j]=1;
q.push(j);
while(!q.empty())
{
int k=q.front();
q.pop();
for(int i=1;i<=n;i++)
{
if(map[k][i]&&flag[i]==flag[k])
{
return 0;
}
if(map[k][i]&&flag[i]==-1)
{
q.push(i);
flag[i]=1-flag[k];
型差}
}
}
}
return 1;
}
bool find(int x)
{
int i,k;
for(i=1;i<=n;i++)
{
if(map[x][i]==1)
{
k=i;
if(!link[k])
{
link[k]=true;
if(!match[k]||find(match[k]))
{
match[k]=x;
return 卜空皮true;
}
}
}
}
return false;
}
int main()
{
int a,b;
while(~scanf("%d%d",&n,&m))
{
memset(map,0,sizeof(map));
while(m--)
{
scanf("%d%d",&a,&b);
map[a][b]=1;
map[b][a]=1;
}
if(!bfs())
{
printf("No
");continue;
}
int count=0;
memset(match,0,sizeof(match));
for(int i=1;i<=n;i++)
{
memset(link,false,sizeof(link));
if(find(i))
{
count++;
}
}
printf("%d
",count/2);
}
return 0;
}
#include <stdio.h>
#include <string.h>
#include <vector>
#define maxn 305
using namespace std;
vector<int> G[maxn];
int vis[maxn];
bool dfs(int u,bool f)
{
if(vis[u]>=0)
{
if(vis[u]==f)
return true;
else
return false;
}
vis[u]=f;
for(int i=0;i<3;i++)
{
if(!dfs(G[u][i],f^1))
return false;
}
return true;
}
int main()
{
int v,x,y; //v是顶点数,x是一条边的起点,y是终点
printf(“请输入顶点数: “);
while(scanf("%d",&v)==1)//如果输入的个数不为1,跳出循环
{
if(!v)break;
for(int i=0;i<v;i++)
G[i].clear(); //设置了v个向量,并将全部容器清空
memset(vis,-1,sizeof(vis)); //将vis数组全部置为 -1
while(scanf("%d%d",&x,&y)==2)
{
if(!x&&!y)break;
x--;y--;
G[x].push_back(y); //在容器map[x]的尾部插入y,从而建立一个无向图
G[y].push_back(x); //在容器map[y]的尾部插入x,从而建立一个无向图
亏含 }
if(dfs(0,1)) //如果相邻的两点的颜色不相同,则是二分图
{
printf("输入的图是二分图
");
}
else
{
printf("输入的图不是二分图
");
}
}
return 0;
}
intwarshall(inta[N][N])
{
intcol =0;
intline =0;
inttemp =0;
for(col =0;col <N;col++){
for(line =0;line <N;line++){
if(a[line][col]!=0){
for(temp =0;temp <N;temp++){
a[line][temp]=a[line][temp]|a[col][temp];
}
}
}
}
return TRUE;
}
声明: 我们致力于保护作者版权,注重分享,被刊用文章因无法核实真实出处,未能及时与作者取得联系,或有版权异议的,请联系管理员,我们会立即处理,本站部分文字与图片资源来自于网络,转载是出于传递更多信息之目的,若有来源标注错误或侵犯了您的合法权益,请立即通知我们(管理员邮箱:daokedao3713@qq.com),情况属实,我们会第一时间予以删除,并同时向您表示歉意,谢谢!
本站内容仅供参考,不作为诊断及医疗依据,如有医疗需求,请务必前往正规医院就诊
祝由网所有文章及资料均为作者提供或网友推荐收集整理而来,仅供爱好者学习和研究使用,版权归原作者所有。
如本站内容有侵犯您的合法权益,请和我们取得联系,我们将立即改正或删除。
Copyright © 2022-2023 祝由师网 版权所有
邮箱:daokedao3713@qq.com