下载文档原格式
图论（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效果图：赋权图的建⽴：赋权图，每条边都有⼀个⾮负实数对应的图。
图论--图的基本概念1.图：1.1⽆向图的定义：⼀个⽆向图G是⼀个有序的⼆元组<V,E>，其中V是⼀个⾮空有穷集，称作顶点集，其元素称作顶点或结点。
E是⽆序积V&V的有穷多重⼦集，称作边集，其元素称作⽆向边，简称边。
注意：元素可以重复出现的集合称作多重集合。
某元素重复出现的次数称作该元素的重复度。
例如，在多重集合{a,a,b,b,b,c,d}中，a,b,c,d的重复度分别为2，3，1，1。
从多重集合的⾓度考虑，⽆元素重复出现的集合是各元素重复度均为1的多重集。
1.2有向图的定义：⼀个有向图G是⼀个有序的⼆元组<V,E>，其中V是⼀个⾮空有穷集，称作顶点集，其元素称作顶点或结点。
E是笛卡尔积V✖V的有穷多重⼦集，称作边集，其元素为有向边，简称为边。
通常⽤图形来表⽰⽆向图和有向图：⽤⼩圆圈（或实⼼点）表⽰顶点，⽤顶点之间的连线表⽰⽆向边，⽤带箭头的连线表⽰有向边。
与1.1，1.2有关的⼀些概念和定义：（1）⽆向图和有向图统称为图，但有时也把⽆向图简称作图。
通常⽤G表⽰⽆向图，D表⽰有向图，有时也⽤G泛指图（⽆向的或有向的）。
⽤V(G),E(G)分别表⽰G的顶点集和边集，|V(G)|,|E(G)|分别是G的顶点数和边数，有向图也有类似的符号。
（2）顶点数称作图的阶，n个顶点的图称作n阶图。
（3）⼀条边也没有的图称作零图，n阶零图记作N n。
1阶零图N1称作平凡图。
平凡图只有⼀个顶点，没有边。
（4）在图的定义中规定顶点集V为⾮空集，但在图的运算中可能产⽣顶点集为空集的运算结果，为此规定顶点集为空集的图为空图，并将空图记作Ø。
（5）当⽤图形表⽰图时，如果给每⼀个顶点和每⼀条边指定⼀个符号（字母或数字，当然字母还可以带下标），则称这样的图为标定图，否则称作⾮标定图。
（6）将有向图的各条有向边改成⽆向边后所得到的⽆向图称作这个有向图的基图。
（7）若两个顶点v i与v j之间有⼀条边连接，则称这两个顶点相邻。
