概述
参考书目：《Introduction to Graph Theory》 by Robin J.Wilson
发博文仅作为条记记载。
目次
第 1 章 弁言（Introduction）
- 什么是图（What is a graph?）：通过蹊径舆图和电气网络等实例引出图的概念，包罗极点、边、度等根本元素，先容了图的多种体现方式及相干概念，如简单图、多重边、环、有向图等，还提及了路径、循环、连通性、树等根本概念。
第 2 章 界说和示例（Definitions and examples）
- 界说 (Definition)：正式界说了简单图和一样平常图，引入了同构、连通性、毗连、度、子图、矩阵体现等概念。
- 示例（Examples）：枚举了多种告急范例的图，如零图、完全图、循环图、路径图、轮图、正则图、柏拉图图、二分图、立方体图、图的补图等，论述了它们的界说和特点。
- 三个谜题（Three puzzles）：以 “八个圆圈标题”“六个人集会标题”“四个立方体标题” 为例。
第 3 章 路径和循环（Paths and cycles）
- 连通性（Connectivity）
- 欧拉图（Eulerian graphs）
- 哈密顿图（Hamiltonian graphs）
- 一些算法（Some algorithms）：先容了最短路径标题（如迪杰斯特拉算法）、中国邮递员标题（在欧拉回路底子上办理）和观光商标题（现在无高效算法，可通过近似算法求解）。
第 4 章 树（Trees）
- 树的性子（Properties of trees）：界说了森林（无环图）和树（连通森林），证明白树的多个等价性子。
- 计数树（Counting trees）
- 更多应用（More applications）
第 5 章 平面性（Planarity）
- 平面图（Planar graphs）
- 欧拉公式（Euler's formula）
- 其他曲面上的图（Graphs on other surfaces）
- 对偶图（Dual graphs）
- 无穷图（Infinite graphs）
第 6 章 图的着色（Colouring graphs）
- 极点着色（Colouring vertices）
- 布鲁克斯定理（Brooks' theorem）
- 舆图着色（Colouring maps）
- 边着色（Colouring edges）
- 色多项式（Chromatic polynomials）
第 7 章 有向图（Digraphs）
- 界说（Definitions）
- 欧拉图和比赛图（Eulerian digraphs and tournaments）
- 马尔可夫链（Markov chains）
第 8 章 匹配、婚姻与门格尔定理（Matching, marriage and Menger's theorem）
- 霍尔婚姻定理（Hall's'marriage'theorem）
- 横截理论（Transversal theory）
- 霍尔定理的应用（Applications of Hall's theorem）
- 门格尔定理（Menger's theorem）
- 网络流（Network flows）
第 9 章 拟阵（Matroids）
- 拟阵简介（Introduction to matroids）
- 拟阵的例子（Examples of matroids）
- 拟阵与图（Matroids and graphs）
- 拟阵与横截（Matroids and transversals）
媒介
学习图论的条件：具备根本的初等聚集论、矩阵论知识，相识抽象代数知识。
本书可以分为四部分：
- 第 1 ~ 4 章节：底子部分，包罗图的界说和示例、连通性、欧拉路径和哈密顿路径等。
- 第 5 ~ 6 章：关于平面性和着色的内容，特殊提及了四色定理。
- 第 7 ~ 8 章：有向图理论和横截理论，应用于关键路径分析、马尔可夫链、网络流
- 第 9 章：拟阵，接洽前面章节，并先容最新的发展
第一章：引入 Introduction
什么是图 graph？
根本概念
图、点、边、度
- 极点 vertices
- 边 edge
- 图 graph
- 一个图是一组极点以及极点怎样毗连的体现。
- 任何度量属性都是无关紧急的。
- 上述意思是，哪怕差异应用场景中属性差异，但是体现出的极点和边的关系雷同，就可以视为同一个图。
- 度 degree
简单图、环、多重边
- 简单图 simple graphs
- 环 loop
- 多重边 multiple edges
有向图、路径（第 3 章）
- 有向图 directed graphs
- 路径 walks
- 一个极点到达另一个极点的方式
- 由一系列边构成，一条边紧跟着另一条边
- 简单路径 path
- 环 cycle
- 欧拉图 Eulerian
- 图中包罗恰恰颠末图中每条边一次的路径，而且该路径在初始极点竣事
- 哈密顿图 Hamiltonian
- 图中包罗恰恰颠末图中每个极点一次的路径，而且该路径在初始极点竣事
连通图、非连通图（第 3 章）
- 连通图 connected graph
- 非连通图 disconnected graph
- 一个图由多个部分(parts)构成
- 此中每个部分大概是一个连通子图
树（第 4 章）
- 树 trees
- 每对极点之间只有一条路径的连通图
- 树可以被界说为不含圈的连通图
平面图 planar graph（第 5 章）
着色标题 colouring problem（第 6 章）
- 平面图在着色标题中也起偏告急作用。
- 着色标题
- 实行用给定命量的颜色给一个简单图的极点着色，使得图的每条边毗连差异颜色的极点。
- 四色定理 four-colour theorem
- 假如图是平面图，那么我们总是可以只用四种颜色以这种方式给其极点着色
- 我们总是可以用四种颜色给任何舆图的国家着色，使得没有两个相邻的国家利用雷同的颜色
婚姻标题 marriage problem（第 8 章）
- 婚姻标题
- 假设有一群女孩和一群男孩，每个女孩都熟悉几个男孩。婚姻标题就是探究在什么条件下，可以大概让每个女孩都嫁给她熟悉的男孩，而且不存在辩论（比方两个女孩不能嫁给同一个男孩等环境）。
- 婚姻标题和在图中探求毗连两个给定极点的不相交路径的标题相干。
- 标题转化为图模子
- 将婚姻标题中的女孩和男孩分别看作图中的差异范例极点。比方，用一种极点体现女孩聚集，另一种极点体现男孩聚集。假如一个女孩熟悉一个男孩，就在代表这个女孩的极点和代表谁人男孩的极点之间连一条边。如许就构建了一个图，此中极点的分布和毗连关系反映了女孩与男孩之间的熟悉环境。
- 不相交路径与婚姻匹配的接洽
- 探求可行匹配：在这个图中，要实现每个女孩都嫁给她熟悉的男孩，就相称于从女孩极点聚集到男孩极点聚集找到一组不相交的路径（这里的不相交意味着一个男孩不会被多个女孩同时选择，即路径不能共用极点）。每条路径的出发点是一个女孩极点，尽头是她可以匹配的男孩极点，这些路径的聚集就代表了一种大概的婚姻匹配方案。
- 判断匹配的存在性：假如可以大概找到如许一组不相交路径，使得每个女孩极点都能通过一条路径毗连到一个男孩极点，那么就意味着存在一种满足条件的婚姻安排，即每个女孩都能嫁给她熟悉的男孩。反之，假如找不到如许的不相交路径，就阐明不存在满足全部女孩都嫁给熟悉男孩的婚姻安排。
- 横截理论 transversal theory
- 横截理论（Transversal Theory）是组合数学中的一个告急理论，重要研究聚集体系的特定性子和布局，特殊是关于元素与聚集之间的相交关系，它与婚姻标题等组合标题密切相干。
拟阵（第 9 章）
拟阵理论是对具有在其上界说的 “独立布局” 的聚集的研究，它既推广了向量空间中的线性独立性，又推广了本书前面关于图和横截的一些结果。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金 |
发表于 2025-12-30 18:12:39