律师行业网站建设,html购物网页设计报告,秦淮做网站价格,南京 网站开发1#xff1a;图的定义 我们学了线性表和树的结构#xff0c;那什么是图呢#xff1f; 线性表是一个串一个是一对一的结构 树是一对多的#xff0c;每个结点可以有多个孩子#xff0c;但只能有一个父亲 而我们今天学的图#xff01;就是多对多的结构了 V表示的是图的顶点集…1图的定义 我们学了线性表和树的结构那什么是图呢 线性表是一个串一个是一对一的结构 树是一对多的每个结点可以有多个孩子但只能有一个父亲 而我们今天学的图就是多对多的结构了 V表示的是图的顶点集E表示图的边的集合 图可以分为有向图和无向图 有向图就是每个边都是有方向的无向图没方向 无向图可以转化成有向图 接下来我们介绍一下自环和重边
而没有自环和重边的图我们称之为简单图有自环和重边的图叫多重图
稠密图和稀疏图 en*logn就是稠密图
否则就是稀疏图
顶点的度无向图中顶点的度等于出度入度度
有向图中顶点的度出度加入度
路径
比如说A到D可以是A----》B-----》C——》D 也可以是A——》B——》D也可以是A——》B——》C——》A—》——》B——》D v1到v4的路径可以是v1——》v2——》v4 也可以是v1——》v3——》v4 也可以是v1——》v2——》v3——》v4
没有回路就是简单路径否则就是回路或者环
对于不带权路径就是边数
对于带权路径就是边*权值的和 子图就是把图的结点拿出来几个边拿出来几条组成的一个新的图就叫子图
子图也有说叫生成子图的就是说把你的结点全拿出来但是边可以扔掉几个
这个就是生成子图这个就是子图
再看有向图的例子
这就是一个生成子图
这个可以叫一个子图
连通图如果一个图的顶点是n个变数小于n-1一定不是连通图连通图就是任意一对顶点都是能到达的
极大联通子图拿出一个子图子图的边和结点尽可能多并且是连通的
连通分量极大连通子图的数量
可以分成三个极大连通图连通分量就是3
连通图的生成树指的是连通图的一个极小联通子图也就是说n个顶点有n-1条边
比如说
我们要让它只有三条边还得是连通的还得是一个树就叫做它的生成树
对生成树来言砍掉一条边就叫菲连通加上一条边就是图不是树
菲连通
图
