数模学习Day01,7.26

数模学习Day01,7.26

数模学习Day01,7.26

前言

写在前面吧，由于暑期时间有限，8.15开学又要考试，任务就两件但是仍不轻松，我对基础模型的学习到现在仍没有一个系统的认识。于是决定每天至少学习一个基础模型，从今天开始，同时学习记录在贵论坛上进行发表，以此督促自己，同时能把心得与大家分享，有错误欢迎大家指出。谢谢。

我用的数模参考书是司守奎 《数学建模算法与应用》 第二版。

图论建模

preface

1. 图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型

基本概念

1. 对于平面上n个点，用一些线连接起来，忽略次要因素，记为图（graph）G=（V,E）。V(vertex)为顶点集，E(edge)为边集。

2. 有向图：每条边都有方向

   无向图：每条边都没有方向

   混合图：部分边有方向

3. 简单图：任一边的两端点不重合，任两顶点间最多一条边。

4. 相邻：两顶点间相连

5. 完全图：任两顶点间都相邻，记为 K ∣ V ∣ {K_{left| V right|}} K∣V∣​ ,否则称非完全图

6. 二分图：这个概念画图很好理解，就是一个顶点集V满足 V = X ∪ Y V = X cup Y V=X∪Y,其中X是都是分立的点（或者死板的说X中无相邻的顶点集），Y也是。

   X：
   Y：

   ps: 如果对于X中任何一个顶点，都满足与Y的任意顶点相邻。

   ​

   此时即称为完全二分图。记为 K ∣ X ∣ , ∣ Y ∣ {K_{left| X right|,left| Y right|}} K∣X∣,∣Y∣​,相当于理解为二分图和完全图的叠加意。

7.27更新

7. 关于度：若顶点v是边e的端点，那么v与e相关联

   ​ 而一个顶点所关联的所有边数成为该顶点的度（dimension），记为 d ( v ) d(v) d(v)。其中度为奇数为奇顶点，偶数为偶顶点。

   ​ 有一条定理：一个图中奇顶点的总数必为偶数。

   这个其实很容易想到，因为每出现一条边，必然涉及两个顶点，总度数要＋2，所以总度数必为偶数，同时如果把总度数减去总的偶顶点数，那么剩下的只剩所有奇顶点的总度数了。故。。。

   8. 关于边和顶点结合起来的一些性质：

      大家先看一条记录方法： W = v 0 e 1 v 1 e 2 . . . v k − 1 e k v k W = {v_0}{e_1}{v_1}{e_2}...{v_{k - 1}}{e_k}{v_k} W=v0​e1​v1​e2​...vk−1​ek​vk​,

      很容易发现每条边e两边都有顶点v，说明这一行是沿着顶点边顶点边的顺序书写的，故记W为一条道路（way）。

      • 其中，当这条道路中的各边都不相同时，称为迹（trace）

      • 其中，当这条道路的的各个顶点都不相同时，称为轨道（track），
        同时可记为 P ( v 0 , v k ) P({v_{rm{0}}},{v_k}) P(v0​,vk​),这里P(path)意。

      • 关于起点和终点重合

        • 当W为道路时称为回路
        • 当W的各个顶点都相异，或者说W为轨道时，此时称为圈。

​ ps:机智的同学已经意识到回路的范围定义包含了圈，如同道路的定 义包含了迹和轨道一样。

9. 连通图：图满足其中任两顶点都存在道路。

10. 关于Hamilton,

    • 我们知道哈密尔顿1859年提出周游世界游戏，最先研究找连通图中的生成圈问题，故以他命名
    • 若图中有一条轨道***包含所有顶点***，则称该轨道为hamilton轨
    • 闭合的Hamilton轨称为Hamilton圈。
    • 含有Hamilton圈的图称为Hamilton图。

11. 距离（distance）：两顶点u与v（起点与终点）间最短轨道之长

    • 对于完全二分图来说，可以参考之前的X+Y图，可以得知，X中顶点间的距离必为偶数，X与Y中的顶点的距离必为奇数。

最后一点啦

12. 赋权图：指的是每条边上都附有一个或多个实数对应的图，称为该边的权值。

图与网络的数据结构

讨论图与网络的表示方法（想想都知道矩阵会比较简洁）

声明： G = ( V , E ) G = (V,E) G=(V,E)为一个简单无向图，顶点集表示为 V = { v 0 , v 1 , . . . v n } , ∣ V ∣ = n V = { {v_0},{v_1},...{v_n}} ,left| V right| = n V={v0​,v1​,...vn​},∣V∣=n,边集表示为 E = { e 0 , e 1 , . . . e m } , ∣ E ∣ = m E = { {e_0},{e_1},...{e_m}} ,left| E right| = m E={e0​,e1​,...em​},∣E∣=m。

有两种表示方法：邻接矩阵表示和稀疏矩阵（指零元素很多的矩阵）表示，这里主要讨论前者。

1. 当G为赋权图

   邻接矩阵记为 W = ( w i j ) n × n W = {({w_{ij}})_{n times n}} W=(wij​)n×n​，

   满足 w i j = { w e i g h t ( e d g e e x i s t s b e t w e e n v i & v j ) 0 o r ∞ ( e d g e u n e x i s t s b e t w e e n v i & v j ) {w_{ij}} = left{ begin{array}{l} weight (edge exists between {v_i}& {v_j})\ {rm{0 or }}infty (edge unexists between {v_i}& {v_j}) end{array} right. wij​={weight(edgeexistsbetweenvi​&v