图论（1）--图的基本概念
- 格式：pdf
- 大小：107.94 KB
- 文档页数：2
图论（1）--图的基本概念
有向图和⽆向图的建⽴以及赋权图
引⼊
Q：什么是图论？
A：图论是数学的⼀个分⽀。它以图为研究对象。图论中的图是由若⼲给定的点及连接两点的线所构成的图形，这种图形通常⽤来描述某些事物之间的某种特定关系，⽤点代表事物，
⽤连接两点的线表⽰相应两个事物间具有这种关系。
现在我们来探讨⽆向图和有向图的概念以及如何去建⽴最基本的图的模型
什么是图
对于初⼊图论的⼈来说，复杂的定义可能会直接劝退他们，现在我来举⼀个⾮常简单的例⼦。
这就是最常见的图，由于它没有指向，即没有明确的⽅向，它被称为⽆向图。
图是由顶点和边组成的，你应该很容易就知道那些元素是顶点，那些是边。
下⾯的具有⽅向的便是有向图：
若有的边有向，有的边⽆向，则称为混合图。
接下来我们将引⼊更多的概念：
若两个顶点有边相连，则称两个顶点相相邻，两个点称为起点/终点或端点
如1指向2，则这两个顶点相邻，这两个顶点被称为断点，⽽1被称为起点，2被称为终点。
仅含⼀个顶点的边称为⾃环
在⽆向图中，包含顶点v的边的个数，称为顶点的度。 在有向图中，以v为起点的边的个数，称为点的出度，以v为终点的边的个数，称为顶点的⼊度。
⽆向图的建⽴
建⽴简单⽆向图，我们使⽤Matlab，版本为R2017a。
% 函数graph(s,t)：可在 s 和 t 中的对应节点之间创建边，并⽣成⼀个图
% s 和 t 都必须具有相同的元素数；这些节点必须都是从1开始的正整数，或都是字符串元胞数组。
s1 = [1,2,3,4]; %s为顶点，必须保证连续且从1开始的正整数
t1 = [2,3,1,1]; %边 s与t之间是⼀⼀对应的
G1 = graph(s1, t1);
plot(G1) %画出效果图
效果图：
带汉字的⽆向图：
% 注意字符串元胞数组是⽤⼤括号包起来的哦
s2 = {'学校','电影院','⽹吧','酒店'};
t2 = {'电影院','酒店','酒店','KTV'};
G2 = graph(s2, t2);
plot(G2, 'linewidth', 2) % 设置线的宽度
% 下⾯的命令是在画图后不显⽰坐标
set( gca, 'XTick', [], 'YTick', [] );
效果图：
有向图的建⽴：
% ⽆权图 digraph(s,t)
s = [1,2,3,4,1];
t = [2,3,1,1,4];
G = digraph(s, t);
plot(G)
set( gca, 'XTick', [], 'YTick', [] );
注意边的顺序和⽅向，依次为1指向2,2指向3,3指向1,4指向1和1指向4
效果图：赋权图的建⽴：
赋权图，每条边都有⼀个⾮负实数对应的图。这个实数称为这条边的权。
简⽽⾔之就是，顶点到顶点每⼀条边上都有⼀个数字，这个数字被称为权，在不同的实际问题当中权被理解成不同概念，例如，在最经典的求解最短路径问题中，权被理解为路程长
短。
这就是⼀个赋权图的例⼦，现在我们来着⼿创建赋权有向图和赋权⽆向图
赋权⽆向图
% 函数graph(s,t,w)：可在 s 和 t 中的对应节点之间以w的权重创建边，并⽣成⼀个图
s = [1,2,3,4];
t = [2,3,1,1];
w = [3,8,9,2];
G = graph(s, t, w);
plot(G, 'EdgeLabel', G.Edges.Weight, 'linewidth', 2)
set( gca, 'XTick', [], 'YTick', [] );
在之前s,t基础上，我们增加w这个值，就是权重，其余的代码不变。
效果图：
赋权有向图
s = [1,2,3,4];
t = [2,3,1,1];
w = [3,8,9,2];
G = digraph(s, t, w);
plot(G, 'EdgeLabel', G.Edges.Weight, 'linewidth', 2)
set( gca, 'XTick', [], 'YTick', [] );
邻接矩阵
为了我们⽅便进⾏数学上的计算，我们引⼊图的邻接矩阵这个概念。
当图上两个顶点相邻时，我们⽤1来表⽰，当图上两个顶点不相邻时，我们⽤0来表⽰，这样由0和1组成的矩阵我们称为图的邻接矩阵。
先看⾏再看列，例如（1,1）元素值为0，代表它不形成⾃环，（1，2）元素值为1，代表1和2是邻接的，以此类推。
可以看到，这种表⽰法⾮常简单、直接，另外⽆向图的邻接矩阵是⼀个对称阵。
关联矩阵
我们引⼊关联矩阵的概念，同样是在图中，当顶点是这条边的起点时，记为1，为终点时，记为-1。除此之外的其他情况记为0。
接下来我们将会介绍如何图的最短路径问题以及求解最短路径的算法迪杰斯特拉算法和弗洛伊德算法。
