15问答网 > 图论的基本概念有哪些？

图论的基本概念有哪些？

2024-11-02 23:57:39

推荐回答（5个）

回答1：

1、有向图和无向图

有向图，就是有方向的图；所谓无向图，就是没有方向的图。

2、路径和环

我们把没有经过重复的点的路径就叫做简单路径。

环的定义是在路径的定义的基础上做了一定的拓展，首尾相接的路径我们就把它叫做一个环。同样我们也有简单环，也就是除开首尾以外，剩下的部分不会经过重复的点的环就叫做简单环。

3、极大独立集

如果K是G的独立集，且不是任何其他独立集的真子集，就为极大独立集。

4、极大团

如果一个团不被其他任一团所包含，即它不是其他任一团的真子集，则称该团为图G的极大团。

5、最大团

顶点最多的极大团，称之为图G的最大团。

6、独立集

独立集是指图G=(V,E)中两两互不相邻的顶点构成的集合。

参考资料：百度百科-图论

回答2：

1、无向图

一个无向图U是一个二元组，N是一个非空集合的顶点集，记为N(U)，其中的元素是顶点或结点；E是无序积NxN的多重子集（元素可多次出现），是边集，记为E(U)，其中的元素称为无向边或边。

例如，N={n1,n2,n3,n4,n5},E={(n1,n2), (n2,n2), (n2,n3), (n1,n3), (n1,n4)}

2、有向图

一个有向图D是一个二元组，N是一个非空集合的顶点集，其中的元素是顶点或结点，记为N(D)；E是卡氏积的多重子集，记为E(D)，其元素称为有向边或边或弧。

例如，N={n1,n2,n3,n4,n5},E={,,,,,,,}

3、混合图

图中有些边是有向边，另一些边是无向边。

4、邻接集

给定一个无向图U和图中的一个结点ni，ni的邻接集就是在图中直接和ni相连的结点集合。根据有向边描述的方向性，在有向图中ni的邻接集又可分为两部分。

5、无向完全图。

设G是n阶无向简单图，若G中任何顶点都与其余n-1个顶点相邻，则G为n阶无向完全图。

参考资料：百度百科-图论

回答3：

1、有向图和无向图

有向图，就是有方向的图；所谓无向图，就是没有方向的图。

2、路径和环

我们把没有经过重复的点的路径就叫做简单路径。

3、子图

我们把一张大图的点选一些出来，再选一些连在这些点之间的边出来，这样的小图就叫做子图。

4、连通图

如果存在一条从一个点到另外一个点的路径，那么这两个点就是连通的，如果所有点都互相连通的话，这样一张图就叫做连通图。

5、树和森林

一张连通图如果不存在环的话我们就叫做一棵树，如果一张图不存在环的话我们就把这张图叫做森林。

参考资料来源：百度百科-图论

回答4：

图论中的基本概念有：

1 完全图：若一个图的每一对不同顶点恰有一条边相连，则称为完全图。

2 团：对于给定图G=(V,E)。V是图G的顶点集，E是图G的边集。图G的团就是一个两两之间有边的顶点集合。简单地说，团是G的一个完全子图。

3 极大团：如果一个团不被其他任一团所包含，即它不是其他任一团的真子集，则称该团为图G的极大团。

4 最大团：顶点最多的极大团，称之为图G的最大团。

5 独立集：独立集是指图G=(V,E)中两两互不相邻的顶点构成的集合。

6 极大独立集：如果K是G的独立集，且不是任何其他独立集的真子集，就为极大独立集。

7 最大独立集：极大独立集中元素最多的集合为最大独立集。

8 补图：图G的补图，通俗的来讲就是完全图Kn去除G的边集后得到的图Kn-G。

9 最大独立集中顶点数量= 补图的最大团中顶点数量。

扩展资料：

定义：

图G=（V,E）是一个二元组（V,E）使得E⊆[V]的平方，所以E的元素是V的2-元子集。为了避免符号上的混淆，我们总是默认V∩B=Ø。集合V中的元素称为图G的定点（或节点、点），而集合E的元素称为边（或线）。

通常，描绘一个图的方法是把定点画成一个小圆圈，如果相应的顶点之间有一条边，就用一条线连接这两个小圆圈，如何绘制这些小圆圈和连线时无关紧要的，重要的是要正确体现哪些顶点对之间有边，哪些顶点对之间没有边。

引理1

有向图G无回路当且仅当对G进行深度优先搜索没有得到反向边。

证明：→：假设有一条反向边(u,v)，那么在深度优先森林中结点v必为结点u的祖先，因此G中从v到u必存在一通路，这一通路和边(u,v)构成一个回路。

←：假设G中包含一回路C，我们证明对G的深度优先搜索将产生一条反向边。设v是回路C中第一个被发现的结点且边(u,v)是C中的优先边，在时刻d[v]从v到u存在一条由白色结点组成的通路，根据白色路径定理可知在深度优先森林中结点u必是结点v的后裔，因而(u,v)是一条反向边。（证毕）

参考资料：百度百科——图论

回答5：

图论基本概念
重要定义：
有向图：每条边都是有向边的图。
无向图：每条边都是无向边的图。
混合图：既有有向边又有无向边的图。
自回路：一条边的两端重合。
重数：两顶点间若有几条边，称这些边为平行边，两顶点a,b间平行边的条数成为（a,b）的重数。
多重图：含有平行边的图。
简单图：不含平行边和自回路的图。
注意！一条无向边可以用一对方向相反的有向边代替，因此一个无向图可以用这种方法转化为一个有向图。
定向图：如果对无向图G的每条无向边指定一个方向由此得到的有向图D。称为的G定向图.
底图：如果把一个有向图的每一条有向边的方向都去掉，得无向图G称为的D底图。
逆图：把一个有向图D的每条边都反向由此得到的图称为D的逆图。
赋权图：每条边都赋上了值。
出度：与顶点相连的边数称为该定点的度数，以该定点为始边的边数为出度。入度：以该定点为终边的边数为入度。
特殊！度数为零的定点称为孤立点。度数为一的点为悬挂点。
无向完全图：在阶无向图中如果任何两点都有一条边关连则称此图是无向完全图。Kn
完全有向图：在阶有向图中如果任意两点都有方向相反的有向边相连则称此图为完全有向图。
竟赛图：阶图中如果其底图是无向完全图，则程此有向完全图是竟塞图。
注意！n阶有向完全图的边数为n的平方；无向完全图的边数为n(n-1)/2。
下面介召图两种操作：①删边：删去图中的某一条边但仍保留边的端点。
②删点：删去图中某一点以及与这点相连的所有边。
子图：删去一条边或一点剩下的图。
生成子图：只删边不删点。
主子图：图中删去一点所得的子图称的主子图。
补图：设为阶间单无向图，在中添加一些边后，可使成为阶完全图；由这些添加边和的个顶点构成的图称为的补图。
重要定理：
定理5.1.1 设图G是具有n个顶点m条边的有向图，其中点集V={v,v,….,v}
deg+(vi)=deg-(vi)=m
定理5.1.2 设图G是具有n个顶点m条边的无向图，其中点集V={v,v,v,……,v}
deg(vi)=2m
推论在无向图中，度数为积数的顶点个数为偶数。
通路和富权图的最短通路
1通路和回路
基本概念：
通路的长度：通路中边的条数。
回路：如果通路中始点与终点相同。
简单通路：如果通路中各边都不相同。
基本通路：如果通路中各顶点都不相同。显然（基本通路一定是简单通路，但简单通路不一定是基本通路）
可达：在图G中如果存在一条v到d通路则称从v到d是可达。
连通：在无向图中如果任意两点是可达的，否则是不连通的。
强连通：在有向图中如果任意两点是互可达的。
单向连通：在有向图中如果存在任意两点的通路。
弱连通：在有向图中如果其底图是连通的。
权：在图的点或边上表明某种信息的数。
赋权图：含有权的图。
赋权图的最短通路问题的算法：先求出到某一点的最短通路，然后利用这个结果再去确定到另一点的最短通路，如此继续下去，直到找到到的最短通路为止。
指标：设V是图的点集，T是V的子集，且T含有z但不含a，则称T为目标集。在目标集T中任取一个点t，由a到t但不通过目标集T中其它点所有通路中，个边权和的最小者称为点t关与T的指标记作DT(t)。
图和矩阵
住意两个的区别：A·A 中元素的意义：当且仅当a 和a 都是1时，a a =1而a 和a 都为1意味着图G中有边(v ,v )和(v ,v )。于是可得如下结论：从顶点v 和v 引出的边，如果共同终止于一些顶点，则这些终止顶点的数目就是b 的值；特别对于b ，其值就是v 的出度。

A ·A中元素的意义：当且仅当a 和a 都为1时，a a =1，这意味着图中有边(v ,v )和(v ,v )。于是的得如下结论：从某些点引出的边，如果同时终止于v 和v ，则这样的顶点数就是的值。特别对于b ，其值就是的v 入度。

幂A 中元素的意义：当m=1时，a 中的元素=1，说明存在一条边(v ,v )，或者说从v 到v 存在一条长度为一的通路。

A 中元素a 表示从v 到v 的长度为m的所有通路的数目。
欧拉图
主要定义：
如果图中存在一条通过图中个边一次且仅一次的回路，则称此回路为欧拉回路，具有欧拉回路的图称为欧拉图。

如果图中存在一条通过图中各边一次且仅一次的通路，则称此回路为欧拉通路，具有欧拉通路的图称为半欧拉图。

主要定理：一个无向连通图是欧拉图的充要条件是图中各点的度数为偶数。

一个无向连通图是半欧拉图的充要条件是图中至多有两个奇数度点。

设图G是有向连通图，图G是欧拉图的充要条件是图中每个顶点的入度和出度相等。

设图G是有向连通图，图G是半欧拉图的充要条件是至多有两个顶点，其中一个顶点入度比它的出度大1，另一个顶点入度比它的出度少1；而其他顶点的入度和出度相等。
哈密顿图
主要定义：如果图G中存在一条通过图G中各个顶点一次且仅一次的回路，则称此回路为图的哈密顿回路；具有哈密顿回路的图称为哈密顿图。

如果图G中存在一条通过图G中各个顶点一次且仅一次的回路，则称此回路为图的哈密顿回路；具有哈密顿回路的图称为哈密顿图。
主要定理：设图G是哈密顿图，如果从G中删去个p顶点得到图G’，则图G’的连通分支数小于等于p。

设图G是具有n个顶点的无向简单图，如果G中任意两个不同顶点的度数之和大于等于n-1，则具有哈密顿通路，即G是半哈密顿图。

设图G是具有n个顶点的无向简单图，如果G中任意两个不同顶点的度数之和大于等于n，则G具有哈密顿回路，即G是哈密顿图。

最新问答

技嘉x99主板集成cpu是什么意思

裸眼视力0.12要经常配戴眼镜吗？配多少度的？？？

铁罐发胶可以喷在塑料瓶里存放吗。能放几天？

求助啊，剑圣大神来，懂得都来关于血脉

ilk,pch,pbd,obj,idb,pdb这些扩展名各是什么意思

想知道:重庆市从长寿北站到长寿站怎么坐公交？大概多少时间，谢谢！

为什么我的QQ一开视频和语音就没响应？

以前我小很多事都不知道，误会了很多人，其中就有我奶奶，我一直以为她对我们家都很坏没有感情，谁知道原

我是不是不会做人啊，该怎么办呢

有一部小说，讲一个学生能看出人生什么病，还把他老师的妇科病治好了