代数图论3：进入正题前的准备

循环图 Circulant Graphs

之前提到过 cycle，我们这里再把 cycle 拿出来做一个更加详细的定义

n点循环 $C_n$

The cycle on n vertices is the graph Cn with vertex set {0, … , n- 1} and with i adjacent to j if and only if j - i = ±1 mod n.

也就是说，我们利用了同模的概念来表达一种周而复始的“循环递增”。

循环图 circulant graphs

Let $\mathbb{Z}_n$ denote the additive group of integers modulo n. If $C$ is a subset of $\mathbb{Z}_n \setminus 0$, then construct a directed graph $X = X (\mathbb{Z}_n , C)$ as follows. The vertices of X are the elements of $\mathbb{Z}_n$ and $( i, j)$ is an arc of $X$ if and only if $j - i \in C$. The graph $X(\mathbb{Z}_n, C)$ is called a circulant of order $n$, and $C$ is called its connection set.

大致可以这样来理解这套定义，$\mathbb{Z}_n$事实上表达了这张图的点的个数，是自由度，而$C$则是间隔多少个来连边，是连线方式。

对于一个比较大的循环群$R$我们有
$$
\left | \mathrm{Aut}(X) \right | \ge 2n
$$
因为一般的循环图至少可以进行“旋转”与“反转”的操作，这构成一个与$D_{2n}$同构的自同构子群。只是在$n\le2$时有可能出现谬误，因为点数太少了。

平面图 Planar graph

A graph is called planar if it cann be drawn without crossing edges.

对于平面图有一个很经典的结果

欧拉公式

Theorem 1.8.1 (Euler)
If a connected plane graph has $n$ vertices, $e$ edges and $f$ faces,
then $n - e + f = 2$.

证明也很直接。

1. 我们注意到对一个多边形进行三教剖分并不会改变它 $(n-e+f)$ 的结果，因此我们可以假设我们面对的都是已经被三角剖分的图形。
2. 我们又注意到，对于一个已经三角剖分过的平面图删去一个顶点以及与这个顶点相关的边，$(n-e+f)$ 也不会改变，因此我们可以用这个手段来减少顶点数。
3. 递归直到剩下一个三角形（即只剩下三个顶点），我们得知 $(n-e+f)=2$

平面图的性质

Lemma_1

A planar graph with $n$ vertices has no more than $3n-6$ edges.

Proof:
注意到$2e\ge3f$
$f\le\frac 2 3 e$
由$(n-e+f)=2$可知$e-(n-2)=f\le\frac 2 3 e$.
所以我们有$e\ge 3n-6$.

利用这些引理，我们可以验证一些图像是否是平面图

$K_5$ 不是一个平面图

Proof：
由Lemma 1即可验证

$K_{3,3}$不是平面图

Proof：
考虑$K_{3,3}$里的顶点数和边数，那么有$n=6,e=9$.
并不满足Lemma 1中给出的不等关系，因此不可能是平面图

对偶图

Given a plane graph $X*$, we can form another plane graph called the dual graph $X*$ . The vertices of $X*$ correspond to the faces of $X$, with each vertex being placed in the corresponding face . Every edge e of X gives rise to an edge of $X*$ joining the two faces of X that contain $e$.

大致就是点变成面，面变成点。只是在变化的时候，可能要把平面图的标准放松一点点。因为两个面之间可能不止有一条共同边。

射影平面

The real projective plane is a nonorientable surface, which can be rep­ resented on paper by a circle with diametrically opposed points identified.

在这个平面上，画出$K_5$便成为可能。

感觉像装了传送门一样