图论导引 - 目录、引言、第一章 - 11/05

概述

参考书目：《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 章）

拟阵理论是对具有在其上定义的 “独立结构” 的集合的研究，它既推广了向量空间中的线性独立性，又推广了本书前面关于图和横截的一些结果。