什么叫二部图

什么叫二部图

二部图又叫二分图，是图论中的一种特殊模型，是指顶点集可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。

判断二部图的常见方法是染色法：对任意一未染色的顶点染色，判断其相邻的顶点中，若未染色则将其染上和相邻顶点不同的颜色， 若已经染色且颜色和相邻顶点的颜色相同，则说明不是二部图，若颜色不同则继续判断，直到全部染上色。

请问离散数学中 相异性条件 t条件 有什么区别，该怎样判断？

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)，情况属实，我们会第一时间予以删除，并同时向您表示歉意,谢谢!