代数图论：初见

什么是图 Graph

A graph $X$ consits of a vertex set $V(X)$ and an edgeset $E(X)$, where an edge is an unordered pair of distinct vertices of $X$.

图$X$由两部分组成，一部分是顶点集$V(X)$，另一部分是边集$E(X)$。每条边本质上都是包含两个顶点的无序集。

依照边的关系所自然导出的一个拓扑，事实上正是这里的离散拓扑。因此，有限图在自然导出的拓扑下是一个零维空间。

简单图 Simple graph

我们一开始要研究的图是简单图，它在图的基础上满足三个额外的条件

• 两点之间至多有一条边
• 边无向
• 点与自己之间没有边

几种常见的简单图

1. 全连接图 complete graph $K_n$ 有n个零点，且点与点之间都有边 的简单图
2. 空图 empty graph 只有顶点没有边的简单图
3. 零图 null graph 没有顶点的简单图

同构 isomorphic

因为我们在研究图的时候，事实上更加关心图的顶点与边之间的关系，而不会去关心顶点本身的含义。因此我们需要一个等价关系来说明这些图本质上是“相同的”。

We say that $\varphi:V(X) \to V(Y)$ is an isomorphism from $X$ to $Y$, if $\varphi$ is a bijective and $\forall a,b \in V(X), ab \in E(X) \Leftrightarrow \varphi(a)\varphi(b) \in E(V)$.

由此我们通过$\varphi$构造了一个顶点集与顶点集的对应，同时也保存的边的关系。可以验证，这个定义满足等价关系的三个公理。

Example 1

有向图 directed graph

即不满足简单图的第二个条件，边有向。

连通图 connected graph

即两个顶点之间存在路径链接

子图 subgraph

A subgraph of a graph $X$ is a graph $Y$ such that

$$
V(Y) \subset V(X), E(Y) \subset E(X)
$$
即从已知的图$X$里取出一些顶点和相关的边来构成一个图。可以直观理解为图里面包含的一个图

特殊的子图

生成子图 spanning subgraph

$$
V(X) = V(Y)
$$
即包含了所有原来的图的顶点

诱导子图 induced subgraph

顶点可以不是原来的顶点集，但是，所有可以包含进来的边都会被包含进来。

道路 path

一个顶点序列，相邻顶点之间存在边

环 cycle

一个首尾相接的道路
又或者可以定义为，每个顶点都有且仅有两个边连出

树 tree

一个无环的连通子图

森林 forest

一个无环的子图
或者说，一堆树的并

独立集 independent set

一个子图，且是空图
可以定义最大独立集大小$\alpha(X)$

团 clique

一个全连接子图
可以定义最大团大小$\omega(X)$

某个连通图的最大子树

即最大生成子树

最大森林

如果一个图不是连通图，那么每个连通分支都有一个最大树，我们称这个几何是最大森林