AKSZ-图论
2024-06-09 17:32:00
发布于：广东
5阅读
0回复
0点赞
图和树
图(有向图，无向图，有向图的基图是无向图)
定义
图有若干节点和线组成
表示
G(V,E) V顶点集合，E边集合
完全图
定义:无向图中任意两点都有相连
计算方法：1.n阶完全图有n*(n-1)/2条边
稀疏图（边数量相对少（远小于n*(n-1)））&&稠密图(接近完全图或有向完全图)
自环（自己链连接自己）&&重边（两点之间有多条边相连）
简单图
无向或有向图，无自环或重边
多重图
无向或有向图，有自环或重边
联通
从u到v有路径，则称u与v联通
连通图
无向图中任意两点相连
强连通图
有向图中，有从u到v的路径，也有从v到u的路径
路径
在图G(V,E)中，
树
定义
无向连通图中不存在回路
性质
有n个点，n-1条边
度
结点所拥有的子树的数量，为结点的度，度=0->叶子结点，度!=0->分支结点
前驱 后继
除根外，任意结点都有前驱结点
除叶子结点外都有后继结点
树的深度(高度)
根为第一层，根的孩子为第二层，以此类推
二叉树（树的度数为2）
两个子树，左子树（左孩子），右子树（右孩子）
满二叉树
有k层，且结点树为$ 2^k-1 $，即是一个标准的二叉树
完全二叉树
二叉树高度为k，除第k层以前是满的，第k层不完全，但第k层的结点是从左到右连续的
####二叉搜索树
根结点的左子树<根节点
根节点的右子树>根节点
这里空空如也
有帮助，赞一个