图论
图 是由若干个给定的顶点/以及若干条连接两个顶点的边所构成的图形
图 是 图论 的研究对象
图(graph)图(graph)图(graph):通常用 G(V,E)G(V,E)G(V,E)表示。VVV 为集合,EEE 为边集合。
> G(V,E)-->GraphGraphGraph VertexVertexVertex EdgeEdgeEdge
顶点的个数称为图的阶
路径
在图G(V,E)中从顶点viv_ivi 出发,沿着一些边经过一些顶点vp1v_{p1}vp1 ,vp2v_{p2}vp2 ,………………,vpmv_{pm}vpm
有向图
有向图:单向的
<1,5>为一对顶点构成的有序对(用尖括号括起来)
有向图的基图:忽略有向图所有边的方向,得到的无向图称为该有向图的基图。(无向图G为有向图的G1的基图)
完全图
一个n阶的完全图含有n∗(n−1)÷2n*(n-1) \div 2n∗(n−1)÷2条边。
完全有向图
有向图中任何一对顶点u和v,都存在<u,v>&<v,u>两条有向边。一个n阶的完全有向图含有n∗(n−1)n*(n-1)n∗(n−1)条边。
稀疏图
边的数目相对较小(远小于n∗(n−1)n*(n-1)n∗(n−1)).
稠密图
边的数量相对较多(接近于完全图或者有向完全图
平凡图
只有一个顶点的图
自环
一个节点连接到自身的边
重边
两个结点之间存在多条边。
带权图
边上有带权值的图
简单图(5)
一种无向图或有向图,其中不存在自环和重边。
多重图(5)
一种无向图或有向图,其中存在自环和重边。
连通
若从顶点u到v有路径,则称顶点u和v是连通的。
连通图
如果无向图中任意一对顶点都是连通的,称此图为连通图。
强连通图
有向图中,每一对顶点u和v,存在u<−>vu<->vu<−>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顶点构成的子图已经无法再扩展了。
显然,对于连通图来说,它的最大连通子图就是其本身,连通分量也是其本身。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
例题
有101010个顶点的无向图至少有( )条边边边才能确保是一个连通图。
解析:2个顶点需要1条边,3个顶点需要2条边,以此类推
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
树
n个V,n-1 个E 连通
当n==0时,称为空树。
二叉树
是一种度数为2的树
满二叉树:
定义:一个深度为k且有2k−12^k-12k−1个结点的树叫做满二叉树。
树中结点的最大层次称为树的(深度)高度;
完全二叉树
若二叉树的高度为kkk,则共有kkk层,除第kkk层外,其他各层(1 (k−1))(1~(k-1))(1 (k−1))的结点数都达到最大个数,且第kkk层缺少的结点是从右向左并连续的(存在的是从左到右),这就是完全二叉树。
注意:注意:注意:满二叉树也是完全二叉树的一种。
二叉搜索树
一种应用广泛的二叉树。