1、有向图和无向图
有向图,就是有方向的图;所谓无向图,就是没有方向的图。
2、路径和环
我们把没有经过重复的点的路径就叫做简单路径。
环的定义是在路径的定义的基础上做了一定的拓展,首尾相接的路径我们就把它叫做一个环。同样我们也有简单环,也就是除开首尾以外,剩下的部分不会经过重复的点的环就叫做简单环。
3、极大独立集
如果K是G的独立集,且不是任何其他独立集的真子集,就为极大独立集。
4、极大团
如果一个团不被其他任一团所包含,即它不是其他任一团的真子集,则称该团为图G的极大团。
5、最大团
顶点最多的极大团,称之为图G的最大团。
6、独立集
独立集是指图G=(V,E)中两两互不相邻的顶点构成的集合。
参考资料:百度百科-图论
1、无向图
一个无向图U是一个二元组<N,E>,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,E>,N是一个非空集合的顶点集,其中的元素是顶点或结点,记为N(D);E是卡氏积的多重子集,记为E(D),其元素称为有向边或边或弧。
例如,N={n1,n2,n3,n4,n5},E={<n1,n1>,<n2,n3>,<n3,n2>,<n3,n4>,<n2,n4>,<n4,n5>,<n5,n4>,<n1,n2>}
3、混合图
图中有些边是有向边,另一些边是无向边。
4、邻接集
给定一个无向图U和图中的一个结点ni,ni的邻接集就是在图中直接和ni相连的结点集合。根据有向边描述的方向性,在有向图中ni的邻接集又可分为两部分。
5、无向完全图。
设G是n阶无向简单图,若G中任何顶点都与其余n-1个顶点相邻,则G为n阶无向完全图。
参考资料:百度百科-图论
1、有向图和无向图
有向图,就是有方向的图;所谓无向图,就是没有方向的图。
2、路径和环
我们把没有经过重复的点的路径就叫做简单路径。
环的定义是在路径的定义的基础上做了一定的拓展,首尾相接的路径我们就把它叫做一个环。同样我们也有简单环,也就是除开首尾以外,剩下的部分不会经过重复的点的环就叫做简单环。
3、子图
我们把一张大图的点选一些出来,再选一些连在这些点之间的边出来,这样的小图就叫做子图。
4、 连通图
如果存在一条从一个点到另外一个点的路径,那么这两个点就是连通的,如果所有点都互相连通的话,这样一张图就叫做连通图。
5、 树和森林
一张连通图如果不存在环的话我们就叫做一棵树,如果一张图不存在环的话我们就把这张图叫做森林。
参考资料来源:百度百科-图论
本回答被网友采纳图论中的基本概念有:
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)是一条反向边。(证毕)
参考资料:百度百科——图论