数学交叉建模

图论

基本概念

顶点集合 $V={v ~1~, V ~2~, ······ }$

边集合 $E={e1, e2, e3,······}$

关系函数 $F(e)={u,v}$

图的表示就有 $ G={V, E, F}$

欧拉图特点: 线图,连通,无奇度顶点(https://zhidao.baidu.com/question/208310107.html)

边与边之间有相邻不相邻关系:共顶点则为相邻关系,反之亦然;

求欧拉巡回的算法:fleury算法,hierholzer算法

求最佳巡回算法:edmonds算法

图

巡回是指从一点出发经过一系列移动之后又能回到初始顶点;

不具有b结构的称为简单图

二部图

二部图与完全二部图:

若$V(G)=X∪Y$, $X∩Y=φ$ 且$X$中任意两顶点不相邻,$Y$ 中任意两顶点不相邻,则称为二部图或偶图;若$X$中每一顶点皆与$Y$ 中一切顶点相邻,称为 完全二部图或完全偶图,记为 $(m=|X|,n=|Y|)$

二部图

有向图:就是有方向的图

加权图:图中的边上带有权重的图

加权图
加权图

子图和生成子图

子图:类似子集

生成子图:保留原图顶点,但是少了部分边

路径和连通

通路:只要可以走就行 walk

道路:边不能重复,但顶点可以重复 Trail

路径:顶点、边都不能重复

定义:起点和终点重合的路径称为圈,长为K的圈称为k阶圈

起点和终点重合的道路称为闭通路

图与网络的数据结构

邻接矩阵

0不相邻,1相邻

邻接矩阵
邻接矩阵

1234567表示顶点,1表示相通,0表示不通;

加权图的带权邻接矩阵 A=(W~ij~)n×n

$w~ij~$$=\cases{权值&$当Vi 与Vj 之间有边时$\cr 0&$当i=j时$\cr∞&$当Vi与Vj 之间无边时$\cr}$

有向图的邻接矩阵 A=(W~ij~)n×n

$aij$=$=\cases{1&$若(vi,vj)∈E$\cr 0&$若(vi,vj)∉E$\cr}$

有向图
有向图
邻接矩阵
邻接矩阵

无向图的邻接矩阵 A=(W~ij~)n×n

$a~ij~ $$=\cases{1&$当Vi 与Vj 相邻$\cr 0&$当Vi与Vj 不相邻$\cr}$

稀疏矩阵

边矩阵

定义一个m列的矩阵第1,2行分别存放百年的起点和终点

边矩阵
边矩阵

最短路径

MATLAB命令

https://www.cnblogs.com/markReaper/p/8454817.html

最小生成树

kruskal算法

关于图论中的匹配问题

https://mengzelev.github.io/2018/11/28/matchings/

https://zh.wikipedia.org/wiki/%E5%8C%B9%E9%85%8D_(%E5%9B%BE%E8%AE%BA)

https://www.renfei.org/blog/bipartite-matching.html

匹配:不相邻的边构成的集合

<最大匹配,匹配,理想匹配>

座位安排问题,任务分配问题(加权二部图的最大权匹配问题),旅行商问题TSP,最小费用流



模糊聚类分析和模式识别

聚类分析

聚类定义:通俗地说,聚类就是分类问题(没有任何关于分类的先验知识,仅靠事物的相似性作为类属划分的准则属于无监督范畴)

常用的模糊聚类分析方法:

  • 基于模糊函数的聚类分析方法:模糊传递闭包法,直接聚类法,最大树法和编网法
  • 基于目标函数的聚类分析方法:称为模糊C均值聚类算法

模糊聚类分析

建立在模糊相似矩阵之上对分类对象进行定量分类的方法

主要内容有:数据标准化,建立模糊相似矩阵,动态聚类

如何聚类分析

  • 数据标准化
  • 建立数据矩阵

设论域$U={x~1~, x2, x3,······}$为被分类对象,每个对象又有m个指标表示性状,$xi={xi1,xi2·····xim}$,则得到原始数据矩阵$X=(x_{ij})_{n\times m}$

  • 标准差标准化 (使数据正规化,在$[0,1]$之间)

标准化方法

​ 极差正规化,极差标准化,最大值规格化

123.png
123.png

用最大最小值构造模糊相似矩阵

模糊相似矩阵

定理

相似系数法
相似系数法
夹角余弦法
夹角余弦法
常用方法
常用方法

聚类

模糊等价矩阵

定义:给定$U$上的一个模糊关系$R_{ij}=[r_{ij}]_{n\times n}$,若它满足:

  • 自反性($r_{ij}=1$)
  • 对称性($r_{ij}=r_{ji}$)
  • 传递性($R\circ R \subseteq R$)

称$R$是$U$上的一个模糊等价矩阵。

传递性
传递性

相似性度量的相关、相似系数矩阵满足自反性和对称性,但不一定满足传递性。

对于传递性,可先计算$R○R(记作R^2)$,然后看其是否满足传递性。若不满足,经过$R○R=R^2, R^2○R^2=R^4 …$运 算,可将$R$改造成满足传递性的模糊等价矩阵;

模糊等价矩阵的$\lambda $截矩阵

设$R=[r_{ij}]{n×n}$是模糊等价矩阵,对任意$λ∈[0,1]$,称$Rλ=[r{ij}^{(λ)}]{n×n}为$$R=[r{ij}]_{n×n} λ$截矩阵,其中:

截矩阵1

截矩阵2
截矩阵2

分类

由模糊等价矩阵的$\lambda$截矩阵可知,当$r_{ij}=1$时,$i与j应为同类$,否则为异类

让$\lambda$ 由小到大变化,可形成动态聚类图
分类
分类

最佳阈值$\lambda$的确定

  • 对于不同的$λ∈[0,1]$,可得不同的分类方案,从而 形成一种动态聚类图。这对全面了解对象的分类情 况是比较形象和直观的。但有的实际问题需要选择 某个阀值λ,确定一个具体的分类,这就是确定阀 值λ的问题。

<动态聚类图>

用$F-统计量$ 确定$\lambda$的最佳值

  • 最佳值的确定1
    最佳值的确定1
  • 最佳值的确定2
    最佳值的确定2

模式识别

隶属度和贴近度

  • 隶属度

    • 模糊向量和内外积

      0≤ai≤1(i=1,2,…,n),则称向量a=(a**1,**a2,…,a**n)为模糊向量。设ab**是模糊向量,则分别称:

      123.png

      ​ 为向量ab内积和外积。符号$∧$和$∨$分别表示两个元素取小和取大。

      取大取小

  • 最大隶属度原则

    • 原则1

      原则1

    • 原则2

      原则2

  • 贴近度

    贴近度是描述模糊集之间彼此靠近程度的指标,是我国学者汪培庄教授提出的,由于研究的问题不同,贴近度也有不同的定义形式,它的一般定义为:

    AB是论域$U$上的两个模糊子集,则称

    A与B的贴近度

    • 择近原则

回归模型

相关关系基本概念

一元线性回归分析

一元回归模型的检验

一元线性回归分析

多元线性回归分析

时间序列

非平稳序列的处理

  • $X_t=X_{t-1}+\delta_t$

  • $X_t=Z_t\times\delta_t, Z_t$~N(0,1)