蓝桥杯备考：图论初解

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条边

比如说

我们要让它只有三条边还得是连通的，还得是一个树，就叫做它的生成树

对生成树来言，砍掉一条边就叫菲连通，加上一条边就是图不是树

菲连通

图