做网站都需要买什么,网站后台添加表格,网站设计平台 动易,八宝山做网站公司文章目录 引言一、图与网络的基本知识1.1 图与网络的基本概念1.1.1 图的定义1.1.2 图中相关术语1.1.3 一些特殊图类1.1.4 图的运算 写在最后 引言
按照正常进度应该学习动态规划了#xff0c;但我想换换口味#xff0c;而且动态规划听说也有一定难度#xff0c;还不一定会考… 文章目录 引言一、图与网络的基本知识1.1 图与网络的基本概念1.1.1 图的定义1.1.2 图中相关术语1.1.3 一些特殊图类1.1.4 图的运算 写在最后 引言
按照正常进度应该学习动态规划了但我想换换口味而且动态规划听说也有一定难度还不一定会考。
先说说图论的一些背景知识和发展情况吧。
图论是几十年来发展迅速、应用广泛的一个新的数学分支。它与数学的其他分支如矩阵论、概率论、数值分析等都有着密切地联系。事实上图论为任何一个包含了一种二元关系的系统提供了一个数学模型也因为它使用了图解式的表示法图就具有了一种直观的和符合美学的外形。
图论的发展大致分为 3 个阶段。 第一阶段是从 18 世纪中叶到 19 世纪中叶称为萌芽期。起源是“七桥游戏”问题如下图所示。 问题是能否从这四块陆地中的任何一块开始通过每一座桥一次并且仅一次再次回到起点。
瑞士数学家欧拉Euler就这一问题发表了图论的第一篇论文证明了不存在七桥游戏问题的解并且把这个问题边一笔画问题深入一步地一般化了给出了一个图存在欧拉圈的判定法则。
自从中国邮递员问题Chinese Postman Problem提出来以后欧拉问题才具有了强烈的实用价值。
中国邮递员问题是这样的邮递员在沿着邮路出发前必须先从邮局取走他所应分发的邮件。为了节约时间每一位邮递员都愿意以尽可能少的行程走完他所必须走的所有路线。用图论的话来说是指如何以尽可能少的行程遍历邮路上所有各条街道后又回到他的出发点。
这类问题的第一篇论文是由中国数学家、山东师范大学的管梅谷教授在 1962 年提出的因而得名“中国邮递员问题”。 19 世纪中叶到 20 世纪中叶是图论发展的第二阶段这一时期图论大量问题涌现其中以 Hamilton 问题和四色猜想最为著名。
1856 年英国数学家 William Hamilton 爵士发明了“绕行世界”的游戏。这个游戏用一个规则十二面体它的 20 个顶点标以 20 个城市的名字要求游戏者找一条从某一城市出发的路线它经过每个城市恰好一次并且最终回到出发点。
将正十二面体投影到平面上就得到了下图。 实际上 Hamilton 周游世界问题是图论中的点一笔画问题是要在上图中找具有以下两个特点的一个圈 H H H 1.图中的每一个顶点都在圈 H H H 中出现2.在 H H H 中顶点不重复出现起终点不算重复。这个圈称为 Hamilton 圈。
四色猜想问题即能否仅用 4 种颜色给地图染色使得相邻国家有不同的颜色。用图来描述就是用点来表示国家两个国家若有公共边界就用一条边将这两点连接起来于是四色猜想问题就转化为能否用四种颜色给平面的点染色使得相邻的点有不同颜色。 20 世纪中叶以后是图论发展的第三个阶段这一时期图论经过爆炸性的发展成长为一门独立学科。其中最重要的是出现了研究问题和解决问题的强有力工具计算机。 一、图与网络的基本知识
1.1 图与网络的基本概念
1.1.1 图的定义
自然界和人类社会中大量的事物及事物之间的关系常可以用图形来描述。常将所研究对象看成一个点用连线带箭头或者不带箭头表示对象之间的某种特定关系。为了区别起见我们称不带箭头连线称为边带箭头的连线称为弧。
定义 1.1 —— 一个图是由一个非空集合 V V V 以及 V V V 中元素的无序或有序点对组成的集合 E E E 或 A A A所组成。 V V V 中元素的无序点对所构成的集合称为边集合 E E E 由点集合 V V V 和边集合 E E E 构成的图称为无向图简称图记作 G ( V , E ) G(V,E) G(V,E) 。一条连接点 v i , v j v_i,v_j vi,vj 的边 e i j e_{ij} eij 记为 e i j [ v i , v j ] e_{ij}[v_i,v_j] eij[vi,vj] 或 e i j [ v j , v i ] e_{ij}[v_j,v_i] eij[vj,vi] 。 V V V 中元素的有序点对构成的集合称为弧集合 A A A 由点集合 V V V 和弧集合 A A A 构成的图为有向图记为 D ( V , A ) D(V,A) D(V,A) 。一条方向是从 v i v_i vi 指向 v j v_j vj 的弧记为 a i j ( v i , v j ) a_{ij}(v_i,v_j) aij(vi,vj) 。 若图 G G G 中某个边的两个端点相同称该边为环若两个点之间有多于一条的边称为多重边。一个无环、无多重边的图称为简单图无环但允许有多重边的图称为多重图。
图 G G G 或 D D D 中的点数记为 n ∣ V ∣ n|V| n∣V∣ 边弧数记为 m ∣ E ∣ ( m ∣ A ∣ ) m|E| (m|A|) m∣E∣(m∣A∣) 在不引起混乱的情况下分别简记为 n , m n,m n,m 其中 n n n 为图的阶若 n n n 为有限的称为有限阶。
1.1.2 图中相关术语
端点。当 e i j [ v i , v j ] e_{ij}[v_i,v_j] eij[vi,vj] 时与边 e i j e_{ij} eij 相连的顶点称为边 e i j e_{ij} eij 的端点。边与点相关联。当 e i j [ v i , v j ] e_{ij}[v_i,v_j] eij[vi,vj] 时 e i j e_{ij} eij 与 v i , v j v_i,v_j vi,vj 称为边顶相关联。邻点。邻边。环。只与一个顶点相关联的边称为环。平行边。具有相同的两个端点的边称为平行边。邻域。与某点相邻接的点的集合。次。以点 v i v_i vi 为端点的边的数目称为点 v i v_i vi 在 G G G 中的次记为 d ( v i ) d(v_i) d(vi) 。 如果有环则按两条边记即 d ( v i ) d l ( v i ) 2 l ( v i ) d(v_i)d_l(v_i)2l(v_i) d(vi)dl(vi)2l(vi) 其中 d l ( v i ) d_l(v_i) dl(vi) 是与 v i v_i vi 相关联的非环边数 l ( v i ) l(v_i) l(vi) 是与 v i v_i vi 相关联的环数。次序列。若 V { v 1 , v 2 , … , v p } V\{v_1,v_2,\dots,v_p\} V{v1,v2,…,vp} 则相对于每个点都有一个次则可以得到一个次序列 ( d ( v 1 ) , d ( v 2 ) , … ) (d(v_1),d(v_2),\dots) (d(v1),d(v2),…) 。
定理 1.1 —— 对于图 G ( V , E ) G(V,E) G(V,E) 其中 ∣ V ∣ n , ∣ E ∣ m |V|n,|E|m ∣V∣n,∣E∣m 则有 ∑ v ∈ V d ( v ) 2 m \sum_{v \in V}d(v)2m v∈V∑d(v)2m 定理 1.2 —— 奇数次顶点的总数是偶数。
悬点。次为 1 的点。悬边。悬点关联的边。孤立点。次为 0 的点。链。初等链。链 Q Q Q 中的顶点均不相同。简单链。链中边都不相同。链的长度。为所包含的边数。圈。路。路径。有向图中路每个顶点均不相同称为路径。回路。路的第一个点和最后一个点相同。
1.1.3 一些特殊图类
平凡图。节点数 n 1 n1 n1 边数 m 0 m0 m0 的图。零图。边数 m 0 m0 m0 。连通图。图中每对节点都有一条链路连接称这个图是连通的。树。无圈的连通图。完备图。任意两个顶点之间恰有一条边相关联。二分图。完全二分图。正则图。每个点的次数均相同。有向网络。加权的有向图。
1.1.4 图的运算
1子图和支撑 子图、支撑子图都是图 G G G 的点或边作删除运算得到的。子图点和边都是原图的子集支撑子图点和原图一样边是原图子集。
2图的收缩运算
3割集 常记为 Φ ( X ) \varPhi(X) Φ(X) 如下图中若 X { V 1 } X\{V_1\} X{V1} 则割集为 Φ ( X ) { [ v 1 , v 2 ] , [ v 1 , v 3 ] , [ v 1 , v 4 } \varPhi(X)\{[v_1,v_2],[v_1,v_3],[v_1,v_4\} Φ(X){[v1,v2],[v1,v3],[v1,v4} 。即用一条线去割要求可以将 X X X 完整割出来这条线碰着的边记为割集。 4图的同构 设 G 1 , G 2 G_1,G_2 G1,G2 为两个同阶图若顶点集合 V 1 , V 2 V_1,V_2 V1,V2 以及边集合 E 1 , E 2 E_1,E_2 E1,E2 之间在保持关联性质条件下一一对应则称图 G 1 , G 2 G_1,G_2 G1,G2 同构。如下图所示。 写在最后
这概念可是真的多不过结合图来理解就还好后面我们来说说如何用矩阵表示图。
