"图论模型与网络特性分析及应用"

第9 讲 图论模型1；引入的弧的数目称为的入度,记为−(),()= () −()称为的度.度为奇数的顶点称为奇顶点, 度为偶数的顶点称为偶顶点.定理 10.1给定图 = (, ), ;第 10 章 图论模型图论是运筹学的一个经典和重要分支, 专门研究图与网络模型的特点、性质以及求解方法. 许多优化问题, 可以利用图与网络的固有特性所形成的特定方法来解决, 比用数学规划等其他模型求解往往要简单且有效得多.图论起源于 1736 年欧拉对哥尼斯堡七桥问题的抽象和论证. 1936 年, 匈牙利数学家柯尼西出版的第一部图论专著《有限图与无限图理论》, 树立了图论发展的第一座里程碑. 近几十年来, 计算机科学和技术的飞速发展, 大大地促进了图论的研究和应用, 其理论和方法已经渗透到物理学、化学、计算机科学、通信科学、建筑学、生物遗传学、心理学、经济学、社会学等各个学科中.10.1 图的基础理论及 networkx 简介10.1.1 图的基本概念所谓图, 概括地讲就是由一些点和这些点之间的连线组成的. 定义为 𝐺 = (𝑉, 𝐸),其中 𝑉 是顶点的非空有限集合, 称为顶点集. 𝐸 是边的集合, 称为边集. 边一般用�𝑣𝑖, 𝑣 𝑗� 表示, 其中 𝑣𝑖, 𝑣 𝑗 属于顶点集 𝑉.以下用 |𝑉| 表示图 𝐺 = (𝑉, 𝐸) 中顶点的个数, |𝐸| 表示边的条数.图 10.1 是;" 在第9讲中，介绍了图论模型1，其中引入的弧的数目被称为入度，记为deg-(v)，Degree(v) = |{u ∈ V | (u,v) ∈ E}|。如果图中每个顶点的入度称为图的入度，出度定义类似。此外，如果某个顶点的度是奇数，则称该顶点为奇顶点，如果度是偶数，则称为偶顶点。在第10章中提到，图论是运筹学中的一个重要分支，专门研究图与网络模型的特点、性质以及求解方法。许多优化问题可以利用图与网络的特性来解决，比其他模型求解更简单有效。 图论的起源可以追溯到1736年欧拉对哥尼斯堡七桥问题的研究。1936年，匈牙利数学家柯尼西出版了第一部图论专著《有限图与无限图理论》，标志着图论的发展有了重要的里程碑。随着近几十年来计算机科学和技术的飞速发展，图论在各个学科中得到了广泛的研究和应用，包括物理学、化学、计算机科学、通信科学、建筑学、生物遗传学、心理学、经济学和社会学等领域。 在第10.1节中介绍了图的基础理论及networkx的简介。图被定义为由一些点和这些点之间的连线组成。其中V是顶点的非空有限集合，称为顶点集，而E是边的集合，称为边集。边一般用(vi, vj)表示，其中vi, vj属于顶点集V。图G=(V, E)中，|V|表示顶点的个数，而|E|则表示边的数目。 在图论学科中，网络x是一个Python编程语言的图论软件包，其简介和使用方法也在本节进行了介绍。总之，图论是一个重要的运筹学分支，他的理论和方法已经被广泛的应用到很多学科和研究领域。