--- tags: - 离散数学 - 图论 返回目录: '[[数学系/离散数学/离散数学|离散数学]]' abstract: '图、树与网络优化基础' finished: false --- # 图论 一个图G是一个序偶,其中V是一个非空集合，E是V的2元素子集的集合。分别称V和E是图G的顶点集和边集。V中的元素是图G的顶点，E中的元素是图G 的边。 V记作V（G），E记作E（G） 对于图G=，若|V|=p，|E|=q，称作（p，q）图。P称为图G的阶。边集E为空集的图称为零图。（1，0）图称为平凡图。 在图中，若边e=(u,v),则称顶点u与顶点v相邻接，并称顶点u与边e相关联，顶点v和边e相关联； 若边e和f有一个共同的端点，则称e和f相邻接；没有边关联于它的顶点称为孤立点；不与其它任何边相邻接的边称为孤立边。 两端点相同的边称为环；两端点间的若干条边称为平行边；有环的图称为带环图；没有环的图称为无环图；有平行边的图称为多重图；没有环也没有平行边的图称为简单图； 任何两个不同顶点之间都由边相连的简单图叫完全图。具有p个顶点的完全图记作Kp。完全图的总边数为p（p-1）/2 设G=是简单图，且V=V1，则称G为二部图 若 ,我们称G为完全二部图，|V1|=m,V2=n时完全二部图记作Km，n。完全二部图的总边数为mn。 如果给（p，q）图G的每条边ei赋予一个权重wi，则称G为赋权图。赋权图常记作G=,其中W={w1,w2,…},并称w（G）= 用一维数组存放网络中所有节点数据。 用二维数组存放节点连接关系的数据 这个二维数组称为连接矩阵 ## 最小支撑树问题 求最小树的方法：“破圈法”和“避圈法” ■破圈法：“见圈破圈”，即如果看到图中有一个圈，就将这个圈的边去掉一条，直至图中再无一圈为止。 ■ 步骤如下： 在图中找一个回路; 去掉该回路中权值最大的边; ➢ 反复此过程，直至图中再无回路，得到最小支撑树。 避圈法：开始选一条最小权的边，以后每一步中，总从与已选边不构成圈的那些未选边中，选择一条权最小的。（每一步中，如果有两条或两条以上的边都是权值最小的边，则从中任选一条）。 6、最小支撑树问题 求最小树的方法：“破圈法”和“避圈法” ![[最小树支撑]] ## 复杂网络分析 **1.** ***\*课程背景和重要性\****： o 我选择参加这门课程是出于对复杂网络分析的好奇，复杂网络可以较为形象地描述系统主体间的联系，在计算机、生命科学等领域获得广泛应用。 **2.** ***\*课程内容的收获\****： ***\*提前学习了图，包括度，边，邻接矩阵，路径长度，簇等等概念。核心在于学习了各种复杂网络模型，包括最基本的无向有向图，规则网络中的全局耦合网络、最近邻耦合网络和星型耦合网络。随机网络，小世界网络，复杂网络同步以及介于两者之间的无标度网络。\**** **3.** ***\*个人成长和发展\****： ***\*如何让我们在数学分析和高等代数学到的知识落地是本门课程的核心思想。其中，在描述度分布中，我们利用到了概率论中的概率分布函数来阐述。比如随机网络的度分布近似于泊松分布，而无标度网络度分布近似于幂律分布。以及\****用概率模型描述节点之间连接的随机性。 ***\*在研究邻接矩阵和拉普拉斯矩阵运用到了特征值和特征向量，了解到它是一个实对称矩阵。\**** 在学习网络***\*同步理论\****时，主要研究在复杂网络中，节点之间如何达到同步。涉及到耦合强度、耦合拓扑结构等因素。复习了线性稳定性分析和非线性动力学，即动态平衡中常微分和偏微分方程的应用。还有“以直代曲”的思想用泰勒展开式让本来复杂的多项式降维成线性关系。 ***\*4\*******\*未来设想部分：\**** o 尤其是在当今的数字化时代，复杂系统与复杂网络的理论和方法有了更广阔的用武之地，在其与人工智能、生物、社会、经济等多学科交叉融合的过程中不断涌现出更具挑战的新问题，有待进一步探索。 ## 基本定理 > [!proposition] 握手定理 > 有限无向图满足 $\sum_{v\in V}\deg(v)=2|E|$。 > ^prop-handshaking > [!proof]- 证明 > 每条边恰有两个端点，在所有顶点度数之和中被计算两次，因此总和为边数的两倍。 > [!proposition] 树的边数 > 含 $ 个顶点的树恰有 -1$ 条边。 > ^prop-tree-edges > [!proof]- 证明 > 对 $ 归纳。=1$ 时显然。若 >1$，树必有叶顶点；删除叶及其唯一边后仍为树，按归纳假设有 -2$ 条边，加回一条边即得 -1$。