二分图又叫作二部图是图伦中的一种特殊模型，简而言之，就是顶点集v可分割为两个互不相交的子集，并且图中每两条边依附的两个顶点都分属于这两个互不相交的子集。区别二分图，关键的是看点集是否能分成两个独立的点集
k正则二部图：设|X|=n1，|Y|=n2。
假设 n1≠n2，不妨设 n1>n2，由于是K正则的，故由X点集引出的边有n1×k条，同时连向 Y 这个点集的边数亦为n1×k条（亦即由Y点集引出的边数为n1×k）。
由于是正则的二分图，故Y点集的每个点的度数为 n1×k/n2，而n1/n2>1，故Y中点的度数>k，这与G是一个k正则图矛盾，从而必有X，Y的模相等。
简介
正则表达式是对字符串（包括普通字符（例如，a 到 z 之间的字母）和特殊字符（称为“元字符”））操作的一种逻辑公式，就是用事先定义好的一些特定字符、及这些特定字符的组合，组成一个“规则字符串”，这个“规则字符串”用来表达对字符串的一种过滤逻辑。正则表达式是一种文本模式，该模式描述在搜索文本时要匹配的一个或多个字符串。
#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;
qpush(j);
while(!qempty())
{
int k=qfront();
qpop();
for(int i=1;i<=n;i++)
{
if(map[k][i]&&flag[i]==flag[k])
{
return 0;
}
if(map[k][i]&&flag[i]==-1)
{
qpush(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\n");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\n",count/2);
}
return 0;
}
#include <stdioh>
#include <stringh>
#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("输入的图是二分图\n");
}
else
{
printf("输入的图不是二分图\n");
}
}
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;
}
二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二部图
完全图二部图k3，4有3×4=12条边
欧拉回路的充要条件是所有顶点的度数都是偶数
K(n,n)中,所有顶点度数都是n,所以只要n是偶数即可
Hamilton图
只要n>1即可
比如左边的n个点是A1、A2、、An,右边的n个点是B1、B2、、Bn
只要顺着这个回路走,就是Hamilton回路：A1-B1-A2-B2-A3-B3--An-Bn-A1
以上就是关于二部图是简单图吗全部的内容，包括:二部图是简单图吗、什么是k正则二部图、判断一个图是否为二部图的程序等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！
