蓝桥杯备考：图论初解
1：图的定义
我们学了线性表和树的结构，那什么是图呢？
线性表是一个串一个是一对一的结构
树是一对多的，每个结点可以有多个孩子，但只能有一个父亲
而我们今天学的图！就是多对多的结构了
V表示的是图的顶点集，E表示图的边的集合
图可以分为有向图和无向图
有向图就是每个边都是有方向的，无向图没方向
无向图可以转化成有向图
接下来我们介绍一下自环和重边
而没有自环和重边的图，我们称之为简单图，有自环和重边的图，叫多重图
稠密图和稀疏图 e>n*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条边
比如说
我们要让它只有三条边还得是连通的，还得是一个树，就叫做它的生成树
对生成树来言，砍掉一条边就叫菲连通，加上一条边就是图不是树
菲连通
图