《图论及其应用》(一)
发布网友
发布时间：2024-10-15 06:37
共1个回答
热心网友
时间：2024-11-03 09:32
一. 定义与基本概念
图或有序对指的是顶点集合与边集合的组合，分为有限图和空图。顶点数和边数是图的基本属性。简单图没有重边和环，而复合图则可以包含重边和环。相邻和相关联描述顶点间的关系。非标定图没有顶点标号，而标定图则有明确的顶点标号。完全图中每对顶点间都有一条边相连，偶图没有环，而完全偶图中每对顶点间都有两条边相连。补图是原图与所有可能边集的差集，自补图是补图等于原图的图。图的度指从一个顶点出发的边的数量，最小度和最大度分别指图中顶点的最小和最大度数。奇点和偶点根据度数是否为奇数或偶数进行分类。正则图中所有顶点的度数相同。度序列是图中所有顶点度数的排列。图划分是将图分为若干子集。可图指的是能够划分成两两不相交且覆盖所有顶点的两组。频序列是图中度数出现的次数。子图是原图的子集，真子图是除了原图本身外的子图，生成子图是通过特定运算得到的子图。边导出子图和不相交的边不重的并图、交图、差、对称差等都是子图的特殊形式。联图和积图是通过特定运算得到的新图。方体是一种特殊的积图。路径、回路、连通图等描述了顶点间的关系和性质。赋权图中的边有权重，最短路是连接两个顶点权重最小的路径。邻接矩阵、关联矩阵、邻接代数等工具用于描述图的结构。部图、完全部图、完全几乎等部图和完全等部图描述了图的结构特性。度序列的比较如度序列优于、度序列弱于等。
注意：图的四种二元运算如并图、交图、差、对称差后得到的新图的点数和边数有特定的规律，且需注意偶图不包含环但可以有重边。无限图，如整数集合上的“整除关系”图，也是图论中的重要实例。补图和自补图的概念适用于简单图，而偶图不能有环。度序列与图的同构性有关，不同的图可以具有相同的度序列。图的积运算是网络构造的常用方法，超立方体结构在并行计算机网络拓扑中具有优势。
树是图论中应用广泛的一类图，森林、树叶、分支点等是其重要概念。平凡树和最小连通图描述了树的特定性质。离心率、半径、直径等描述了树的几何特性。中心点、中心、分支、权、形心点、形心等概念描述了树的结构特性。生成树和生成森林是通过特定运算得到的树。根树、树根、树叶、内点、分支点等描述了树的结构和性质。树的层数、高、祖先、父亲、儿子、兄弟等描述了树的层次结构。有序树、外向树、内向树、m元树、m元完全树、最优二元树等描述了树的特定结构和性质。前缀的概念在树的某些应用中也有所体现。
注意：理解树的结构和性质时，需注意树的简单性，如平凡树不是偶图，但非平凡树一定是偶图。树在理论研究和实际问题中的应用广泛。
图的连通度描述了图的连通性，割边、割点、块、块割点树、顶点割、最小点割、连通度、边割、最小边割、边连通度等是连通度相关的概念。连通度的高低反映了图的结构性质，如连通图中任意两点间不相交路的条数与连通程度有关。拓扑学中的其他连通性参数，如图的坚韧度、核度等，提供了更深入的连通性分析。宽直径相关概念用于衡量网络传输延迟。
欧拉图与哈密尔顿图是图论中的重要概念，Euler闭迹、Euler迹、最优环游、Hamilton路、Hamilton图、闭图、闭包、度极大非Hamilton图族、旅行售货员问题TSP、最优圈、超图、Peterson图、Thomassen图、线图、细分图等是其相关概念。闭图的概念要注意其定义和逻辑。度极大非H图族中的度范围定义有助于简化分析。线图和细分图的性质提供了联系Euler图与哈密尔顿图的视角。
匹配与因子分解涉及图的边和顶点覆盖。匹配、M饱和点、M非饱和点、完美匹配、最大匹配、M交错路、M可扩充路、S的邻集、覆盖、最小覆盖、奇分支、偶分支、因子分解、n-因子、n-因子分解、n-可因子化、森林因子分解、荫度、M非饱和点、M可扩路、M交错树、最优匹配、可行顶点标号、相等子图等是匹配与因子分解相关的概念。匹配问题的解决方法和M饱和点/M非饱和点的定义需要仔细理解。完美匹配和1-因子分解之间存在联系。图的一个一因子实际上是一个完美匹配的导出子图，图的可一因子分解意味着它能分解为若干边不重的完美匹配的导出子图之并。
平面图和其可平面性是图论中一个关键概念。可平面图、面、外部面、极大可平面图、极小不可平面图、外可平面图、极大外可平面图、对偶图、基本非平面图（Kuratowaki图）、在2度顶点内的扩充或收缩、关系、桥、附着顶点、可画入等描述了平面图的性质和构造。平面图及其偶图的一些性质，如点数与面数、边数之间的关系，以及度数与面数之间的关系等，提供了深入理解平面图的途径。
图的着色涉及边和顶点的分配，k边着色、边色数、划分、色组、着色、色数、色划分、色图、次大度、色多项式、理想子图、伴随多项式等是着色相关的概念。边着色实际上是对图的一种划分，边色数对应图的最小独立集划分数。色多项式的核心计算方法是递推公式。拉姆齐数描述了在特定条件下，至少包含一个特定子图的图的最小阶数。
有向图的概念包括有向图、始点、终点、重数、基础图、定向图、出度、入度、有向图的邻接矩阵和关联矩阵、简单有向图、可达性、强连通的、单向连通的、弱连通的等。有向图的性质和操作如可达性、连通分支等描述了有向图的结构。
二. 定理与证明
1. 若一个图是自补的，则该图的顶点数为偶数。
2. 图中所有顶点的度数之和等于边数的两倍。
推论1：在任何图中，奇点的个数为偶数。
推论2：正则图的阶数和度数不同时为奇数。
3. 若存在非负整数组和偶数，且满足某个条件，则该图是可图的。
4. 简单图中所有点的度数不能互不相同。
5. 简单图和它的补图有相同的频序列。
6. 简单图的所有不同生成子图的个数是特定值。
7. 若图是不连通的，则它的一连通子图。
8. 一个图是偶图当且仅当它不包含奇圈。
9. 代数图论相关定理包括连通图的条件、邻接矩阵与通道数的关系、邻接代数的维数等。
点击返回目录
