AKSZ-图论
2024-06-09 17:38:46
发布于:广东
图论
图 是由若干个给定的顶点/以及若干条连接两个顶点的边所构成的图形
图 是 图论 的研究对象
:通常用 表示。 为集合, 为边集合。
G(V,E)-->
顶点的个数称为图的阶
路径
在图G(V,E)中从顶点出发,沿着一些边经过一些顶点,,,
有向图
有向图:单向的
<1,5>为一对顶点构成的有序对(用尖括号括起来)
有向图的基图:忽略有向图所有边的方向,得到的无向图称为该有向图的基图。(无向图G为有向图的G1的基图)
完全图
一个n阶的完全图含有条边。
完全有向图
有向图中任何一对顶点u和v,都存在<u,v>&<v,u>两条有向边。一个n阶的完全有向图含有条边。
稀疏图
边的数目相对较小(远小于).
稠密图
边的数量相对较多(接近于完全图或者有向完全图
平凡图
只有一个顶点的图
自环
一个节点连接到自身的边
重边
两个结点之间存在多条边。
带权图
边上有带权值的图
简单图(5)
一种无向图或有向图,其中不存在自环和重边。
多重图(5)
一种无向图或有向图,其中存在自环和重边。
连通
若从顶点u到v有路径,则称顶点u和v是连通的。
连通图
如果无向图中任意一对顶点都是连通的,称此图为连通图。
强连通图
有向图中,每一对顶点u和v,存在u<->v(双向奔赴)。
连通图和连通分量
如果在图G中,任意2个顶点之间都存在路径,那么称G为连通图(注意是任意2顶点)。上面那张城市之间的图,每个城市之间都有路径,因此是连通图。而下面这张图中,顶点8和顶点2之间就不存在路径,因此下图不是一个连通图,当然该图中还有很多顶点之间不存在路径。
上图虽然不是一个连通图,但它有多个连通子图:0,1,2顶点构成一个连通子图,0,1,2,3,4顶点构成的子图是连通图,6,7,8,9顶点构成的子图也是连通图,当然还有很多子图。我们把一个图的最大连通子图称为它的连通分量。0,1,2,3,4顶点构成的子图就是该图的最大连通子图,也就是连通分量。连通分量有如下特点:
1)是子图;
2)子图是连通的;
3)子图含有最大顶点数。
注意:“最大连通子图”指的是无法再扩展了,不能包含更多顶点和边的子图。0,1,2,3,4顶点构成的子图已经无法再扩展了。
显然,对于连通图来说,它的最大连通子图就是其本身,连通分量也是其本身。
例题
有个顶点的无向图至少有( )条才能确保是一个连通图
。
解析:2个顶点需要1条边,3个顶点需要2条边,以此类推
树
n个V,n-1 个E 连通
当n==0时,称为空树。
二叉树
是一种度数为2的树
满二叉树:
定义:一个深度为k且有个结点的树叫做满二叉树。
树中结点的最大层次称为树的(深度)高度;
完全二叉树
若二叉树的高度为,则共有层,除第层外,其他各层的结点数都达到最大个数,且第层缺少的结点是从右向左并连续的(存在的是从左到右),这就是完全二叉树。
满二叉树也是完全二叉树的一种。
二叉搜索树
一种应用广泛的二叉树。
这里空空如也
有帮助,赞一个