什么叫做连通图

连通图：是指在图论中，连通图基于连通的概念。
在一个无向图G中，若从顶点到顶点有路径相连（当然从到也一定有路径），则称和是连通的。如果G是有向图，那么连接和的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。图的连通性是图的基本性质。

扩展资料：

连通图性质
一个无向图G=
(V,E)是连通的，那么边的数目大于等于顶点的数目减一：
，而反之不成立。
如果G=
(V,E)是有向图，那么它是强连通图的必要条件是边的数目大于等于顶点的数目：
，而反之不成立。
没有回路的无向图是连通的当且仅当它是树，即等价于：
参考资料来源：百度百科-连通图

历史：1736年 19世纪
应用：计算机科学、化学、运筹学、经济学、语言学等
内容：图的基本概念、包括 路径和环,欧拉回路，哈密尔顿回路/货郎担问题，图同构、平面图等。

①定义中的结点对可以是有序的，也可以是无序的，若边e所对应的结点对e i =<v i1 ,v i2 >是有序的，则称e i 是有向边，若边e所对应的结点e i =<v i1 ,v i2 >，i=1,2,…,n是无序的，则称e i 是无向边。

②有向边简称弧,v i1 称为弧e i 的始点, v i2 ,称为弧e i 的终点,统称为e i 的端点无向边简称棱。

① 有限图: V,E 均为有限集。
② n 阶图: IVl=n其中,IVI指的是结点集合V的结点的个数。
③ 零图: E=∅即图中没有边,只有孤立点。
④ 平凡图: E=∅且IVI=1即只有一个孤立点构成的图。
⑤ 多重图: 含平行边的图。
⑥ 简单图: 既不含平行边也不含环的图。
⑦ 完全图：

1、无向图结点的度数
设G=<V,E>为无向图,与顶点，关联的边的条数称为v的度,记作 deg(v)。
约定:每个环算两条边,则环的度数为2。
最大度:△(G)max{d(v)lv∈V} 最小度,δ(G) min{d(v)lv∈V}。
由定义可知零图中各点度数为0，完全图k n 各点的度数为n-1。

定理1
设图G是具有n个结点、m条边的无向图,具中结点集合为V={v 1 ,v 2 ,…,v n },则
即顶点度数之和等于边数之和的两倍
定理1是显然的,因为在计算各点的度数时,每条边都计算两次,于是图G中全部顶点的度数之和就是边数的2倍
定理2
在任何无向图中，度数为奇数的结点必定是偶数个。
2、有向图结点的度数
设D=<V,E>为有向图,以顶点v为起始结点的弧的条数称为结点v的出度,记作 deg + (v)以顶点v为终止结点的弧的条数称为v的入度,记作 deg - (v)入度和出度之和称为顶点v的度,记作deg(v)显然有
定理3
在任何有向图中，所有节点的入度之和等于所有节点的出度之和，即

3、度数序列
设V={v 1 ,v 2 ,…,v n }为图G的顶点集，称{d(v 1 ),d(v 2 ),…d(v n )}为G的度数序列。

习题：P261 1,4,7,10,20,30

在有向图中,从顶点v 0 到顶点v n 的一条路径是图中的边的序列,其中每一条边的终点是下一条边的起点。

如果V(H)⊆V(G)且E(H)⊆E(G),则称H是G的子图，记作H⊆G。

若H是G的子图且V(H)=V(G)，则称H是G的支撑子图（或生成子图）

设图H=<V',E'>是图G=<V,E>的子图。若对任意结点u∈V'，v∈V'，如果(u,v)∈E,有(u,v)∈E',则H由V'唯一地确定，并称H是结点集合V'的点诱导子图,记作G(V')；如果H无孤立结点，且由E'所唯一确定，则称H是边集E'的边诱导子图，记作G(E')。
例： 图79中，图(b)与(c)均为(a)的子图，(c)为(a)的支撑子图，(b)为(a)的点诱导子图也是(a)的边诱导子图。

例：图710中，(a)--(f)都是(a)的子图，其中(a)--(d)为(a)的支撑子图，(e)为(a)的点诱导子图，(f)为(a)的边诱导子图。

1、无向图中两顶点的连通
在一个无向图G中，若从顶点u到v存在通路，则称u与v连通。
规定：u到自身总是连通的。
2、有向图中两顶点的可达
在一个有向图D中，若存在从顶点u到v有向通路，则称u可达v。
规定：u到自身总是可达的。
有向通路是有方向性的，所以在有向图中，若u可达v，但反之不成立 。
3、无向图的连通性
在无向图中，若从顶点v 1 到顶点v 2 有路径，则称顶点v 1 与v 2 是连通的。如果图中任意一对顶点都是连通的，则称此图是连通图，否则称G是非连通图。
4、有向图的连通性
一个有向图D=(V,E)，将有向图的所有的有向边替换为无向边，所得到的图称为原图的基图如果一个有向图的基图是连通图，则有向图D是弱连通的，否则称D为非连通的若D中任意两点u,v都有从u可达v，或从v可达u,则称D是单向连通的;若D中每点u均可达其他任一点v,则称D是强连通的

经过图G的每条边一次且仅一次,而且走遍每个结点的通类,称为欧拉通路。
经过图G的每条边一次且仅一次的回路,称为欧拉回路,具有欧拉回路的图称为欧拉图。
注:①欧拉回路要求边不能重复,结点可以重复笔不离开纸,个里及地疋元所有的边且走过所有结点,就是所谓的一笔画。
②凡是一笔画中出现的交点处,线一出一进总应该通过偶数条(偶度点),只有作为起点和终点的两点才有可能通过奇数条(奇度点)
习题：P271,1,4,13,21,22,34

定义 ：经过图中每个顶点一次且仅一次的通路(回路),称为哈密尔顿通路(哈密尔顿回路)存在哈密尔顿回路的图叫哈密尔顿图
注意：欧拉图与哈密尔顿图研究目的不同,前者要遍历图的所有边,后者要遍历图的所有点。
虽然都是遍历问题,两者的困难程度却大不相同欧拉图问题,欧拉已经解决了,而哈密尔顿问题却是一个至今仍未解决的难题,在大多数情况下,人们还是采用尝试求解方法来解决。
哈密尔顿图的判定定理1
设G是n(n≥3)阶无向简单图
①若G中任何一对不相邻的顶点的度数之和都大于等于n-1,则G中存在哈密尔顿通路;
②若G中任何一对不相邻的顶点的度数之和都大于等于n,则G是哈密尔顿图
哈密尔顿图的判定定理2
在n(n≥2)阶有向图D=<V,E>中,如果所有有向边均用无向边代替,所得无向图中含生成子图K。,则有向图D中存在哈密尔顿通路
推论n(n≥3)阶有向完全图是哈密尔顿图

欧拉:每条边一次
哈密尔顿(H回路):每个节点一次可能有哈密尔顿回路，没有欧拉回路
哈密尔顿回路还没找到简单的判别条件

20节

无向图+补图=完全图
而如果他们都不连通……我想他们组合起来也不会连同。这就失去完全图的意义了……
不知道对不对，呵呵。
补图……应该是这样定义的吧？？？？忘了~~~~

//n个点m条边,输出连通1,否则0
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
struct unit
{int u,v,next;
};
struct unit e[400010];
struct unit2
{int dfn,low;
};
struct unit2 b[100010];
int n,m,num=0,order=0,g=0,top=0;
int p[100010],used[100010],stack[100010],a[100010];
void add(int u,int v)
{e[num]u=u;
e[num]v=v;
e[num]next=p[u];
p[u]=num;
num++;
}
void tarjan(int i)
{int j,v;

order++;
b[i]dfn=order;
b[i]low=b[i]dfn;
top++;
stack[top]=i;
used[i]=1;

j=p[i];

while(j!=-1)
{if(used[e[j]v]==0) tarjan(e[j]v);
if(used[e[j]v]!=2) b[i]low=min(b[i]low,b[e[j]v]low);
j=e[j]next;
}

if(b[i]low==b[i]dfn)
{g++;
while(used[i]==1)
{a[stack[top]]=g;
used[stack[top]]=2;
top--;
}
}
}
int main()
{int i,j,x,y;

scanf("%d%d",&n,&m);

memset(p,-1,sizeof(p));

for(i=1;i<=m;i++)
{scanf("%d%d",&x,&y);
add(x,y);
add(y,x);
}

for(i=1;i<=n;i++)
if(used[i]==0) tarjan(i);

if(g>1)
cout<<0<<endl;
else
cout<<1<<endl;

return 0;
}

对一个图 G=(V,E) 中的两点 x 和 y ，若存在交替的顶点和边的序列 Γ=(x=v0-e1-v1-e2--ek-(vk+1)=y)则两点 x 和 y 是连通的。Γ是一条x到y的连通路径，x和y分别是起点和终点。当 x = y 时，Γ 被称为回路。如果通路 Γ 中的边两两不同，则 Γ 是一条简单通路，否则为一条复杂通路。如果图 G 中每两点间皆连通，则 G 是连通图。具体可以去百度文库搜索连通图

显然不对，两者没有任何关系
无向图指连接两个顶点的的边是非向量，比如叫A与B的连边，而不是A到B的连边
连通图指从图中任一顶点能从连边到达图中所有顶点
两者之间没有什么必然联系

对于一个无向图而言，它的一个极大连通子图即为一连通支。比如说，一个图由三部分构成，其中每一部分都是连通的，但三个部分之间互相不连通，那么每一部分即为无向图的一个连通分支。此图的连通分支数为3。

更形象些，你把教学楼附近的几棵树合起来看做是一个无向图，树叶和树枝分叉点为图的结点，树枝为图的边，每一棵树是连通的，但树与树之间没有树枝相连。因而，每棵树都可视为一个连通分支，树的个数为连通分枝数。

扩展资料

离散数学可以看成是构筑在数学和计算机科学之间的桥梁，因为离散数学既离不开集合论、图论等数学知识，又和计算机科学中的数据库理论、数据结构等相关，它可以引导人们进入计算机科学的思维领域，促进了计算机科学的发展。

1．集合论部分：集合及其运算、二元关系与函数、自然数及自然数集、集合的基数。

2．图论部分：图的基本概念、欧拉图与哈密顿图、树、图的矩阵表示、平面图、图着色、支配集、覆盖集、独立集与匹配、带权图及其应用。

3．代数结构部分：代数系统的基本概念、半群与独异点、群、环与域、格与布尔代数。

4．组合数学部分：组合存在性定理、基本的计数公式、组合计数方法、组合计数定理。

5．数理逻辑部分：命题逻辑、一阶谓词演算、消解原理。

---