Graph

对于三元组,满足：

  • 顶点集有限；
  • 边集是顶点无序对组成的(可重)集合，也即；

Simple Graph

当边集有重复元素，称相同的边为重边/平行边(multiple/parallel edges);

称点与边是关联的(indicent)，当且仅当,这样称是边​的一个端点(end)；

称点是相邻的(nerbor)，当且仅当边;

称边为自环(loop),当且仅当边的两个端点相同；

称图是简单的(simple),当且仅当边集既没有重边也没有自环；

Degree

称顶点的度(degree)为顶点关联的边数

  • 自环在度中贡献2次；

称图的最大度；

最小度为;

称点为孤立点(isolated vertex)，当且仅当;

称点为悬垂点(pendent vertex),当且仅当

Handshaking Theorem(握手定理)

对任意图

推论：对于任意图，奇数度的顶点的个数为偶数；

Definitions

称图是图​的子图(subgragh)，如果

进一步，若图是图的生成子图(spanning subgragh)，如果

称两个图同构(isomorphism),记作,当且仅当存在映射

使得对于的任意两点,均有

彼此同构的图构成等价类；

如果图满足,它们的不交并(disjoin)表示为

其点集为,边集为;

无标号图计数问题：阶图同构图等价类个数；

有标号图计数问题：顶点固定的阶图同构图等价类个数；

称为简单图的补图(complement graph)，当且仅当其点集和边集满足

  • 补关系是自反的；

称图为自补的(self-complement),当且仅当

  • ;
  • 是自补的；

Connectedness

称图为连通的(connected),如果该图无法被划分为两个图的不交并；否则为非连通的(disconnected)；

  • 一个非连通图至少可以划分为两个连通分支
  • 连通图仅有一个连通分支；

记图的连通分支数为

Representation

定义图的邻接矩阵(adjacency matrix)

关联矩阵(incident matrix)

Laplacian矩阵

将的特征值称为图的Laplace特征值，按非递增序排列如下：

  • 图是连通的当且仅当;此时被称为Fiedler 值；

  • 中连通分量的数量是的零空间的维度;

注意：

  • ​是对称的方阵；
  • 一般认为非简单图，自环,重边处值为2；

Examples

一般的图

称图为空图(empty graph), 当且仅当其边集为空,记作；

称图为完全图(complete graph),当且仅当其任意两个顶点均连边，记作;

  • 完全图的边数为

称图是**正则的**(regular)，如果;

  • 一般认为;
  • 正则图也指代立方体图；

对于正则图来说，不能同时为奇数;

Petersen Graph

对于图,对于,记的全体二元子集为

，

image-20240919195844604

性质：

  • 3-正则的；
  • 色数为3；
  • 非平面的；

Platonic Graph(正多面体图)

Platonic图也称正多面体图；它们都是正则的；

image-20240919200111239

image-20240919200127071

Bipartite图（二部图）

称图为二部图(Bipartite)，如果其顶点和边集满足

  • 可以划分为两个不相交的部集

对于完全二部图,其边集是所有之间的所有边；

image-20240919200448924

特别的，我们称为爪，为星；

Hypercube(k-cube)

二进制定义(Binary Definition)

对于维度为的二进制序列;

立方体图,是指点集和边集满足如下条件：

也就是说，两点连边当且仅当仅有一个二进制位不同；

递归定义(Recursive structure)

  • ;

其中两个图的Cartesian积 定义如下：

image-20240919201148526

性质

  • 是一个二部图
    • 考虑每个点的按位异或，值为1的和值为0的分别为两个部集；、
  • 是正则的；

独立集与Ramsey 问题

在图中，称点集为独立集，如果满足：

换言之，没有两个点在中相邻；

对于给定的,存在最小的正整数,使得对于任意阶的简单图，要么存在,要么存在阶的独立集，这个正整数称为Ramsey数；

如果我们将红蓝二染色，等价描述为必存在阶蓝色完全图或者阶的红色完全图；

Hadamand矩阵

Lemma

proof:由红蓝二染色的对称性易得；

Theorem

proof:

注意到以下反例，推知

image-20240925195643353

只需证明：将二染色必存在红色或蓝色;

考察,有5条关联的边，由抽屉原理，必有3条边同色，不妨假设为红色,那么若存在红边，那么和该红边构成红色,否则构成蓝色;其余平凡；

Theorem(Erdös and Szekeres, 1935)

对于给定，存在上界，并且满足不等关系：

proof:只需证明阶完全图二染色必存在红色或蓝色;

选择,将划分为两个集合,满足：

  • 若为蓝色，则;
  • 若为红色，则;

显然,由抽屉原理，要么，要么;

由归纳假设，要么中存在红色或蓝色,要么中存在红色或蓝色，算上结论显然；

Corollary(Greenwood and Gleason, 1955)

当均为偶数时

proof:假设,考虑阶的完全图,显然为奇数，对,

以下三种情况必有其一成立：

由归纳假设，平凡，只需考虑:

现统计蓝色边数量，由的任意性和握手定理，

奇偶性矛盾!

Theorem

proof:一方面;

另一方面，下图说明

image-20240925212612682

Theorem

proof:一方面;

另一方面,下图说明

image-20240925212907505

Theorem

proof:由推论;

另一方面，下图说明

image-20250113174120961

通过的二次剩余可以构造该图；

目前的Ramsey数的进展如下：

image-20240925213332395