4.1 Definitions 图论·定义

本页译自 LibreTexts · Discrete Mathematics (Levin) 第 4.1 章。公式经 MathJax 渲染，自定义宏已注入。

Investigate! 探究！

Which (if any) of the graphs below are the same?

下面这些图中，有哪些（如果有的话）是相同的？

$image-59.svg$ $image-60.svg$ $image-61.svg$ $image-62.svg$ $image-63.svg$

（图：保留原文图示引用，未翻译图内文字。）

The graphs above are unlabeled. Usually we think of a graph as having a specific set of vertices. Which (if any) of the graphs below are the same?

上面的图没有标任何顶点名。通常我们把一个图看作拥有某一特定的顶点集合。下面这些图中，有哪些（如果有的话）是相同的？

$image-64.svg$ $image-65.svg$ $image-66.svg$ $image-67.svg$

（图：保留原文图示引用，未翻译图内文字。）

Actually, all the graphs we have seen above are just drawings of graphs. A graph is really an abstract mathematical object consisting of two sets $V$ and $E$ where $E$ is a set of 2-element subsets of $V\text{.}$ Are the graphs below the same or different?

其实，上面我们见到的所有图都只是图的「画出来」的样子。图本身是一种抽象的数学对象，由两个集合 $V$ 和 $E$ 组成，其中 $E$ 是 $V$ 的二元子集组成的集合。下面的图是相同的，还是不同的？

Graph 1:

图 1：

$V = \{a, b, c, d, e\}\text{,}$
$E = \{\{a,b\}, \{a, c\}, \{a,d\}, \{a,e\}, \{b,c\}, \{d,e\}\}\text{.}$

$V = \{a, b, c, d, e\}\text{，}$
$E = \{\{a,b\}, \{a, c\}, \{a,d\}, \{a,e\}, \{b,c\}, \{d,e\}\}\text{。}$

Graph 2:

图 2：

$V = \{v_1, v_2, v_3, v_4, v_5\}\text{,}$
$E = \{\{v_1, v_3\}, \{v_1, v_5\}, \{v_2, v_4\}, \{v_2, v_5\}, \{v_3, v_5\}, \{v_4, v_5\}\}\text{.}$

$V = \{v_1, v_2, v_3, v_4, v_5\}\text{，}$
$E = \{\{v_1, v_3\}, \{v_1, v_5\}, \{v_2, v_4\}, \{v_2, v_5\}, \{v_3, v_5\}, \{v_4, v_5\}\}\text{。}$

Before we start studying graphs, we need to agree upon what a graph is. While we almost always think of graphs as pictures (dots connected by lines) this is fairly ambiguous. Do the lines need to be straight? Does it matter how long the lines are or how large the dots are? Can there be two lines connecting the same pair of dots? Can one line connect three dots?

在开始研究图之前，我们需要先就「什么是图」达成一致。尽管我们几乎总是把图想成「用线连起来的点」那样的图画，但这种说法相当含混。线一定要是直的吗？线的长短、点的大小要紧吗？能否有两条线连接同一对点？一条线能否连三个点？

The way we avoid ambiguities in mathematics is to provide concrete and rigorous definitions. Crafting good definitions is not easy, but it is incredibly important. The definition is the agreed upon starting point from which all truths in mathematics proceed. Is there a graph with no edges? We have to look at the definition to see if this is possible.

在数学中，我们避免含混的办法，是给出具体而严格的定义。写出好的定义并不容易，却极为重要。定义是一切数学真理所由出发的、彼此约定的起点。有没有不含边的图？我们必须查定义才能知道这是否可能。

We want our definition to be precise and unambiguous, but it also must agree with our intuition for the objects we are studying. It needs to be useful: we could define a graph to be a six legged mammal, but that would not let us solve any problems about bridges. Instead, here is the (now) standard definition of a graph.

我们希望定义既精确无歧义，又要与所研究对象给我们的直观相符。定义还得有用：我们可以把图定义成「有六条腿的哺乳动物」，但那样我们解决不了任何关于桥的问题。因此，下面是（如今）图的规范定义。

Definition 定义

A graph is an ordered pair $G = (V, E)$ consisting of a nonempty set $V$ (called the vertices) and a set $E$ (called the edges) of two-element subsets of $V\text{.}$

图是一个有序对 $G = (V, E)$，由一个非空集合 $V$（称为顶点集）和一个集合 $E$（称为边集）组成，其中 $E$ 的元素是 $V$ 的二元子集。

Strange. Nowhere in the definition is there talk of dots or lines. From the definition, a graph could be

奇怪。定义里通篇没有提到点，也没有提到线。按这个定义，一个图可以是下面这样的：

\begin{equation*} (\{a,b,c,d\}, \{\{a,b\}, \{a,c\}, \{b,c\}, \{b,d\}, \{c,d\}\}) \end{equation*}

（上式：以四个顶点 $a,b,c,d$ 及其六条可能的边所构成的一个图。）

Here we have a graph with four vertices (the letters $a, b, c, d$) and four edges (the pairs $\{a,b\}, \{a,c\}, \{b,c\}, \{b,d\}, \{c,d\}$).

这里我们有一个含四个顶点（字母 $a, b, c, d$）和四条边（配对 $\{a,b\}, \{a,c\}, \{b,c\}, \{b,d\}, \{c,d\}$）的图。

Looking at sets and sets of 2-element sets is difficult to process. That is why we often draw a representation of these sets. We put a dot down for each vertex, and connect two dots with a line precisely when those two vertices are one of the 2-element subsets in our set of edges. Thus one way to draw the graph described above is this:

直接看集合、以及由二元子集组成的集合，很不便于理解。正因如此，我们常常把这些集合画成图来表示。每个顶点画一个点；当且仅当两个顶点属于边集中的某个二元子集时，才用一条线把它们连起来。因此，上面那个图的一种画法如下：

$image-68.svg$

（图：保留原文图示引用，未翻译图内文字。）

However we could also have drawn the graph differently. For example either of these:

不过，这个图也可以画成别的样子。例如下面两种画法：

$image-69.svg$ $image-70.svg$

（图：保留原文图示引用，未翻译图内文字。）

We should be careful about what it means for two graphs to be “the same.” Actually, given our definition, this is easy: Are the vertex sets equal? Are the edge sets equal? We know what it means for sets to be equal, and graphs are nothing but a pair of two special sorts of sets.

我们应当仔细想想，说两个图「相同」究竟是什么意思。其实，有了上面的定义，这件事很简单：顶点集相等吗？边集相等吗？我们清楚集合相等意味着什么，而图无非是一对特殊的集合罢了。

Example 1

示例 1

Are the graphs below equal?

下面两个图是否相等？

\begin{equation*} G_1 = (\{a,b,c\}, \{\{a,b\}, \{b,c\}\}); \qquad G_2 = (\{a,b,c\}, \{\{a,c\}, \{c, b\}\}) \end{equation*}

（上式分别给出两图的顶点集与边集；问二者是否相等。）

equal?

是否相等？

Solution

解答

No. Here the vertex sets of each graph are equal, which is a good start. Also, both graphs have two edges. In the first graph, we have edges $\{a,b\}$ and $\{b,c\}\text{,}$ while in the second graph we have edges $\{a,c\}$ and $\{c,b\}\text{.}$ Now we do have $\{b,c\} = \{c,b\}\text{,}$ so that is not the problem. The issue is that $\{a,b\} \ne \{a,c\}\text{.}$ Since the edge sets of the two graphs are not equal (as sets), the graphs are not equal (as graphs).

不相等。这里两个图的顶点集相同，这是个好的开始。而且两个图都有两条边。在第一个图中，边是 $\{a,b\}$ 和 $\{b,c\}$，而在第二个图中，边是 $\{a,c\}$ 和 $\{c,b\}$。既然 $\{b,c\} = \{c,b\}$，这倒不是问题所在。问题在于 $\{a,b\} \ne \{a,c\}$。由于两个图的边集（作为集合）不相等，这两个图（作为图）也就不相等。

Even if two graphs are not equal, they might be basically the same. The graphs in the previous example could be drawn like this:

即使两个图不相等，它们仍可能本质上是同一个图。上一例中的两个图可以画成下面这样：

$image-71.svg$

（图：保留原文图示引用，未翻译图内文字。）

Graphs that are basically the same (but perhaps not equal) are called isomorphic. We will give a precise definition of this term after a quick example:

那些本质上相同（但未必相等）的图，称为同构（isomorphic）。我们先看一个简短的例子，再给出这个术语的精确定义：

Example 2

示例 2

Consider the graphs:

考虑以下两个图：

$G_1 = (V_1, E_1)$ where $V_1 = \{a, b, c\}$ and $E_1 = \{\{a,b\}, \{a,c\}, \{b,c\}\}\text{;}$
$G_2 = (V_2, E_2)$ where $V_2 = \{u,v,w\}$ and $E_2 = \{\{u,v\}, \{u,w\}, \{v,w\}\}\text{.}$

$G_1 = (V_1, E_1)$，其中 $V_1 = \{a, b, c\}$，且 $E_1 = \{\{a,b\}, \{a,c\}, \{b,c\}\}\text{；}$
$G_2 = (V_2, E_2)$，其中 $V_2 = \{u,v,w\}$，且 $E_2 = \{\{u,v\}, \{u,w\}, \{v,w\}\}\text{。}$

Are these graphs the same?

这两个图是同一个图吗？

Solution

解答

The two graphs are NOT equal. It is enough to notice that $V_1 \ne V_2$ since $a \in V_1$ but $a \notin V_2\text{.}$ However, both of these graphs consist of three vertices with edges connecting every pair of vertices. We can draw them as follows:

这两个图不相等。只要注意到 $V_1 \ne V_2$ 就够了，因为 $a \in V_1$ 而 $a \notin V_2$。不过，这两个图都由三个顶点组成，且每对顶点之间都有边相连。我们可以把它们画成下面这样：

$image-72.svg$ $image-73.svg$

（图：保留原文图示引用，未翻译图内文字。）

Clearly we want to say these graphs are basically the same, so while they are not equal, they will be isomorphic. The reason is we can rename the vertices of one graph and get the second graph as the result.

我们显然想说这两个图本质上是同一个图——所以它们虽然不相等，却是同构的。理由在于：只要把其中一个图的顶点重新命名，就能得到第二个图。

Intuitively, graphs are isomorphic if they are basically the same, or better yet, if they are the same except for the names of the vertices. To make the concept of renaming vertices precise, we give the following definitions:

直观地说，如果两个图本质上相同——或者更准确地说，除了顶点名字不同以外完全一样——它们就是同构的。为了让「重命名顶点」这个概念变得精确，我们给出如下定义：

Isomorphic Graphs 同构图

An isomorphism between two graphs $G_1$ and $G_2$ is a bijection $f:V_1 \to V_2$ between the vertices of the graphs such that if $\{a,b\}$ is an edge in $G_1$ then $\{f(a), f(b)\}$ is an edge in $G_2\text{.}$

两个图 $G_1$ 与 $G_2$ 之间的一个同构（isomorphism），是顶点集之间的一个双射 $f:V_1 \to V_2$，满足：若 $\{a,b\}$ 是 $G_1$ 中的一条边，则 $\{f(a), f(b)\}$ 是 $G_2$ 中的一条边。

Two graphs are isomorphic if there is an isomorphism between them. In this case we write $G_1 \isom G_2\text{.}$

若存在它们之间的一个同构，则称这两个图同构。此时记作 $G_1 \isom G_2$。

An isomorphism is simply a function which renames the vertices. It must be a bijection so every vertex gets a new name. These newly named vertices must be connected by edges precisely if they were connected by edges with their old names.

同构无非是一个给顶点重新命名的函数。它必须是双射，这样每个顶点都能得到一个新名字。当且仅当这些顶点用旧名字时由边相连，它们用新名字时也必须由边相连。

Example 3

示例 3

Decide whether the graphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$ are equal or isomorphic.

判断图 $G_1 = (V_1, E_1)$ 与 $G_2 = (V_2, E_2)$ 是相等的，还是同构的。

$V_1 = \{a,b,c,d\}\text{,}$ $E_1 = \{\{a,b\}, \{a,c\}, \{a,d\}, \{c,d\}\}$
$V_2 = \{a,b,c,d\}\text{,}$ $E_2 = \{\{a,b\}, \{a,c\}, \{b,c\}, \{c,d\}\}$

$V_1 = \{a,b,c,d\}\text{，}$ $E_1 = \{\{a,b\}, \{a,c\}, \{a,d\}, \{c,d\}\}$
$V_2 = \{a,b,c,d\}\text{，}$ $E_2 = \{\{a,b\}, \{a,c\}, \{b,c\}, \{c,d\}\}$

Solution

解答

The graphs are NOT equal, since $\{a,d\} \in E_1$ but $\{a,d\} \notin E_2\text{.}$ However, since both graphs contain the same number of vertices and same number of edges, they might be isomorphic (this is not enough in most cases, but it is a good start).

这两个图不相等，因为 $\{a,d\} \in E_1$ 而 $\{a,d\} \notin E_2$。不过，由于两个图含有相同数目的顶点和相同数目的边，它们可能同构（多数情况下这还不够充分，但这是个好的开始）。

We can try to build an isomorphism. How about we say $f(a) = b\text{,}$ $f(b) = c\text{,}$ $f(c) = d$ and $f(d) = a\text{.}$ This is definitely a bijection, but to make sure that the function is an isomorphism, we must make sure it respects the edge relation. In $G_1\text{,}$ vertices $a$ and $b$ are connected by an edge. In $G_2\text{,}$ $f(a) = b$ and $f(b) = c$ are connected by an edge. So far, so good, but we must check the other three edges. The edge $\{a,c\}$ in $G_1$ corresponds to $\{f(a), f(c)\} = \{b,d\}\text{,}$ but here we have a problem. There is no edge between $b$ and $d$ in $G_2\text{.}$ Thus $f$ is NOT an isomorphism.

我们可以尝试构造一个同构。比如令 $f(a) = b\text{，}$ $f(b) = c\text{，}$ $f(c) = d$，且 $f(d) = a$。这肯定是个双射，但要确认它是同构，必须保证它保持边的关系。在 $G_1$ 中，顶点 $a$ 与 $b$ 由一条边相连。在 $G_2$ 中，$f(a) = b$ 与 $f(b) = c$ 由一条边相连。到这儿都没问题，但我们还得检查另外三条边。$G_1$ 中的边 $\{a,c\}$ 对应到 $\{f(a), f(c)\} = \{b,d\}$，这里却出了问题：$G_2$ 中 $b$ 与 $d$ 之间没有边。因此 $f$ 不是同构。

Not all hope is lost, however. Just because $f$ is not an isomorphism does not mean that there is no isomorphism at all. We can try again. At this point it might be helpful to draw the graphs to see how they should match up.

不过希望并未破灭。$f$ 不是同构，并不意味着根本不存在同构。我们可以再试一次。此时把图画出来，看看它们应当如何对应，可能会有帮助。

$image-74.svg$ $image-75.svg$

（图：保留原文图示引用，未翻译图内文字。）

Alternatively, notice that in $G_1\text{,}$ the vertex $a$ is adjacent to every other vertex. In $G_2\text{,}$ there is also a vertex with this property: $c\text{.}$ So build the bijection $g:V_1 \to V_2$ by defining $g(a) = c$ to start with. Next, where should we send $b\text{?}$ In $G_1\text{,}$ the vertex $b$ is only adjacent to vertex $a\text{.}$ There is exactly one vertex like this in $G_2\text{,}$ namely $d\text{.}$ So let $g(b) = d\text{.}$ As for the last two, in this example, we have a free choice: let $g(c) = b$ and $g(d) = a$ (switching these would be fine as well).

换个思路：注意在 $G_1$ 中，顶点 $a$ 与所有其他顶点都相邻。在 $G_2$ 中，也恰好有一个顶点具有这个性质，即 $c$。因此先定义 $g(a) = c$，以此构造双射 $g:V_1 \to V_2$。接着，$b$ 应该映到何处？在 $G_1$ 中，顶点 $b$ 只与顶点 $a$ 相邻。$G_2$ 中恰好只有一个这样的顶点，即 $d$。于是令 $g(b) = d$。至于最后两个顶点，本例中我们可以随意选择：令 $g(c) = b$、$g(d) = a$（把这两者互换也可以）。

We should check that this really is an isomorphism. It is definitely a bijection. We must make sure that the edges are respected. The four edges in $G_1$ are

我们应当验证这确实是个同构。它无疑是个双射。我们还必须确认边的关系被保持。$G_1$ 中的四条边是

\begin{equation*} \{a,b\}, \{a,c\}, \{a,d\}, \{c,d\} \end{equation*}

（上式：$G_1$ 的四条边。）

Under the proposed isomorphism these become

在上述同构之下，这些边变为

\begin{equation*} \{g(a), g(b)\}, \{g(a), g(c)\}, \{g(a), g(d)\}, \{g(c), g(d)\} \end{equation*} \begin{equation*} \{c,d\}, \{c,b\}, \{c,a\}, \{b,a\} \end{equation*}

（上式：变换后的四条边，恰好就是 $G_2$ 的边。）

which are precisely the edges in $G_2\text{.}$ Thus $g$ is an isomorphism, so $G_1 \cong G_2$

它们恰好就是 $G_2$ 中的边。因此 $g$ 是个同构，于是 $G_1 \cong G_2$。

Sometimes we will talk about a graph with a special name (like $K_n$ or the Peterson graph) or perhaps draw a graph without any labels. In this case we are really referring to all graphs isomorphic to any copy of that particular graph. A collection of isomorphic graphs is often called an isomorphism class.¹ This is not unlike geometry, where we might have more than one copy of a particular triangle. There instead of isomorphic we say congruent.

有时我们会用一个专门的名字来谈论某个图（例如 $K_n$ 或彼得森图），或者画出一张没有任何标号的图。这时我们其实指的是：与该特定图的任一副本都同构的所有图。一组彼此同构的图通常称为一个同构类（isomorphism class）。¹ 这与几何学颇相似：一个特定的三角形可能有多份副本，但在几何里我们不叫「同构」而叫「全等（congruent）」。

There are other relationships between graphs that we care about, other than equality and being isomorphic. For example, compare the following pair of graphs:

除了相等与同构，图之间还有我们关心的其他关系。例如，比较下面这一对图：

$image-76.svg$ $image-77.svg$

（图：保留原文图示引用，未翻译图内文字。）

These are definitely not isomorphic, but notice that the graph on the right looks like it might be part of the graph on the left, especially if we draw it like this:

这两个图肯定不同构，但注意：右边的图看起来像是左边图的一部分——尤其是如果我们把它画成下面这样时：

$image-78.svg$

（图：保留原文图示引用，未翻译图内文字。）

We would like to say that the smaller graph is a subgraph of the larger.

我们想说，较小的图是较大的图的一个子图（subgraph）。

We should give a careful definition of this. In fact, there are two reasonable notions for what a subgroup should mean.

我们应当给出它的精确定义。事实上，「子图」有两种合理的含义。

Subgraphs 子图

We say that $G_1 = (V_1, E_1)$ is a subgraph of $G_2 = (V_2, E_2)$ provided $V_1 \subseteq V_2$ and $E_1 \subseteq E_2\text{.}$

若 $V_1 \subseteq V_2$ 且 $E_1 \subseteq E_2$，则称 $G_1 = (V_1, E_1)$ 是 $G_2 = (V_2, E_2)$ 的子图。

We say that $G_1 = (V_1, E_1)$ is an induced subgraph of $G_2 = (V_2, E_2)$ provided $V_1 \subseteq V_2$ and $E_1$ contains all edges of $E_2$ which are subsets of $V_1\text{.}$

若 $V_1 \subseteq V_2$，且 $E_1$ 包含了 $E_2$ 中所有以 $V_1$ 的子集为元素的边，则称 $G_1 = (V_1, E_1)$ 是 $G_2 = (V_2, E_2)$ 的导出子图（induced subgraph）。

Notice that every induced subgraph is also an ordinary subgraph, but not conversely. Think of a subgraph as the result of deleting some vertices and edges from the larger graph. For the subgraph to be an induced subgraph, we can still delete vertices, but now we only delete those edges that included the deleted vertices.

注意，每个导出子图也都是普通的子图，但反过来不成立。可以把子图想成是从较大的图中删去一些顶点和边得到的结果。要让所得子图是导出子图，我们仍可以删去顶点，但此时只删去那些含有被删顶点的边。

Example 4

示例 4

$image-82.svg$ $image-79.svg$ $image-80.svg$ $image-81.svg$

（图：保留原文图示引用，未翻译图内文字。）

Here both $G_2$ and $G_3$ are subgraphs of $G_1\text{.}$ But only $G_2$ is an induced subgraph. Every edge in $G_1$ that connects vertices in $G_2$ is also an edge in $G_2\text{.}$ In $G_3\text{,}$ the edge $\{a,b\}$ is in $E_1$ but not $E_3\text{,}$ even though vertices $a$ and $b$ are in $V_3\text{.}$

这里 $G_2$ 和 $G_3$ 都是 $G_1$ 的子图。但只有 $G_2$ 是导出子图。在 $G_1$ 中连接 $G_2$ 内顶点的每一条边，也都出现在 $G_2$ 中。而在 $G_3$ 里，边 $\{a,b\}$ 属于 $E_1$ 却不属于 $E_3$，尽管顶点 $a$ 与 $b$ 都在 $V_3$ 中。

The graph $G_4$ is NOT a subgraph of $G_1\text{,}$ even though it looks like all we did is remove vertex $e\text{.}$ The reason is that in $E_4$ we have the edge $\{c,f\}$ but this is not an element of $E_1\text{,}$ so we don't have the required $E_4 \subseteq E_1\text{.}$

图 $G_4$ 不是 $G_1$ 的子图，尽管看上去我们只是去掉了顶点 $e$。原因在于：$E_4$ 中含有边 $\{c,f\}$，而它并不是 $E_1$ 的元素，因此不满足所需的 $E_4 \subseteq E_1$。

Back to some basic graph theory definitions. Notice that all the graphs we have drawn above have the property that no pair of vertices is connected more than once, and no vertex is connected to itself. Graphs like these are sometimes called simple, although we will just call them graphs. This is because our definition for a graph says that the edges form a set of 2-element subsets of the vertices. Remember that it doesn't make sense to say a set contains an element more than once. So no pair of vertices can be connected by an edge more than once. Also, since each edge must be a set containing two vertices, we cannot have a single vertex connected to itself by an edge.

回到一些基本的图论定义。注意，上面我们画的所有图都有一个性质：没有任何一对顶点被连接超过一次，也没有哪个顶点与自己相连。这类图有时被称为简单图（simple），不过我们之后就直接称它们为「图」。这是因为我们对图的定义规定，边是顶点的二元子集所组成的集合。记住，说一个集合含有某个元素「超过一次」是不合逻辑的。所以没有任何一对顶点能被一条边连接超过一次。同样，由于每条边必须是含有两个顶点的集合，我们不可能让单个顶点与自己由一条边相连。

That said, there are times we want to consider double (or more) edges and single edge loops. For example, the “graph” we drew for the Bridges of Königsberg problem had double edges because there really are two bridges connecting a particular island to the near shore. We will call these objects multigraphs. This is a good name: a multiset is a set in which we are allowed to include a single element multiple times.

话虽如此，有时我们也想考虑重（甚至多重）边以及单边环。例如，哥尼斯堡七桥问题中我们画的「图」就有重边，因为确实有两座桥把某个岛与近岸相连。我们把这类对象称为多重图（multigraph）。这个名字很贴切：多重集（multiset）正是一种允许同一元素出现多次的集合。

The graphs above are also connected: you can get from any vertex to any other vertex by following some path of edges. A graph that is not connected can be thought of as two separate graphs drawn close together. For example, the following graph is NOT connected because there is no path from $a$ to $b\text{:}$

上面的图也都是连通的（connected）：沿着由边构成的某条通路，可以从任意一个顶点到达任何其他顶点。不连通的图可以想成是两张分开的图被画得很靠近。例如，下面这个图不连通，因为不存在从 $a$ 到 $b$ 的通路：

$ex-gt-non-connected.svg$

（图：保留原文图示引用，未翻译图内文字。）

Most of the time, it makes sense to treat non-connected graphs as separate graphs (think of the above graph as two squares), so unless otherwise stated, we will assume all our graphs are connected.

多数时候，把不连通的图当作几张分开的图来处理更合理（把上面的图想成两个正方形），因此除非另有说明，我们假定所有的图都是连通的。

Vertices in a graph do not always have edges between them. If we add all possible edges, then the resulting graph is called complete. That is, a graph is complete if every pair of vertices is connected by an edge. Since a graph is determined completely by which vertices are adjacent to which other vertices, there is only one complete graph with a given number of vertices. We give these a special name: $K_n$ is the complete graph on $n$ vertices.

图中的顶点之间并不总是有边相连。如果我们把所有可能出现的边都加上，得到的图称为完全图（complete）。也就是说，若每一对顶点都由一条边相连，则该图是完全图。由于一个图完全由「哪些顶点与哪些顶点相邻」决定，给定顶点数后完全图只有一个。我们给它们一个专门的名字：$K_n$ 表示有 $n$ 个顶点的完全图。

Each vertex in $K_n$ is adjacent to $n-1$ other vertices. We call the number of edges emanating from a given vertex the degree of that vertex. So every vertex in $K_n$ has degree $n-1\text{.}$ How many edges does $K_n$ have? One might think the answer should be $n(n-1)\text{,}$ since we count $n-1$ edges $n$ times (once for each vertex). However, each edge is incident to 2 vertices, so we counted every edge exactly twice. Thus there are $n(n-1)/2$ edges in $K_n\text{.}$ Alternatively, we can say there are $\binom{n}{2}$ edges, since to draw an edge we must choose 2 of the $n$ vertices.

$K_n$ 中每个顶点都与其余 $n-1$ 个顶点相邻。我们把从某个给定顶点发出的边数称为该顶点的度（degree）。因此 $K_n$ 中每个顶点的度都是 $n-1$。$K_n$ 有多少条边？有人可能认为答案应是 $n(n-1)$，因为我们把 $n-1$ 条边数了 $n$ 次（每个顶点一次）。然而每条边关联两个顶点，于是每条边都被我们数了恰好两遍。所以 $K_n$ 共有 $n(n-1)/2$ 条边。换个说法，也可以说有 $\binom{n}{2}$ 条边，因为画一条边必须从 $n$ 个顶点中选出 2 个。

In general, if we know the degrees of all the vertices in a graph, we can find the number of edges. The sum of the degrees of all vertices will always be twice the number of edges, since each edge adds to the degree of two vertices. Notice this means that the sum of the degrees of all vertices in any graph must be even!

一般来说，如果我们知道一个图所有顶点的度，就能求出边数。所有顶点度数之和永远等于边数的两倍，因为每条边都会给两个顶点的度各加 1。注意，这意味着：任何图中所有顶点的度数之和必为偶数！

Example 5

示例 5

At a recent math seminar, 9 mathematicians greeted each other by shaking hands. Is it possible that each mathematician shook hands with exactly 7 people at the seminar?

在最近的一次数学研讨会上，9 位数学家互相握手致意。是否可能每位数学家在会上都恰好与 7 个人握了手？

Solution

解答

It seems like this should be possible. Each mathematician chooses one person to not shake hands with. But this cannot happen. We are asking whether a graph with 9 vertices can have each vertex have degree 7. If such a graph existed, the sum of the degrees of the vertices would be $9\cdot 7 = 63\text{.}$ This would be twice the number of edges (handshakes) resulting in a graph with $31.5$ edges. That is impossible. Thus at least one (in fact an odd number) of the mathematicians must have shaken hands with an even number of people at the seminar.

这看起来似乎可能。每位数学家选一个人不与之握手即可。但这不可能发生。我们其实在问：一个含 9 个顶点的图，能否让每个顶点的度都是 7。若这样的图存在，所有顶点的度数之和就是 $9\cdot 7 = 63$。这会是边数（握手次数）的两倍，从而得到一个有 $31.5$ 条边的图。这不可能。因此，至少有一位（其实是奇数位）数学家在会上与偶数个人握了手。

One final definition: we say a graph is bipartite if the vertices can be divided into two sets, $A$ and $B\text{,}$ with no two vertices in $A$ adjacent and no two vertices in $B$ adjacent. The vertices in $A$ can be adjacent to some or all of the vertices in $B\text{.}$ If each vertex in $A$ is adjacent to all the vertices in $B\text{,}$ then the graph is a complete bipartite graph, and gets a special name: $K_{m,n}\text{,}$ where $\|A\| = m$ and $\|B\| = n\text{.}$ The graph in the houses and utilities puzzle is $K_{3,3}\text{.}$

最后一个定义：若顶点可以分成两集合 $A$ 与 $B$，且 $A$ 中任两个顶点不相邻、$B$ 中任两个顶点也不相邻，则称该图为二部图（bipartite）。$A$ 中的顶点可以与 $B$ 中的部分或全部顶点相邻。若 $A$ 中每个顶点都与 $B$ 中所有顶点相邻，则该图是一个完全二部图（complete bipartite graph），并有一个专门的名字：$K_{m,n}$，其中 $\|A\| = m$、$\|B\| = n$。房屋与公用事业谜题中的图就是 $K_{3,3}$。

Named Graphs 命名图

Some graphs are used more than others, and get special names.

有些图比其他图更常用，因而有专门的名字。

$K_n$: The complete graph on $n$ vertices.
$K_{m,n}$: The complete bipartite graph with sets of $m$ and $n$ vertices.
$C_n$: The cycle on $n$ vertices, just one big loop.
$P_n$: The path on $n$ vertices, just one long path.

$K_n$：有 $n$ 个顶点的完全图。
$K_{m,n}$：两部大小分别为 $m$ 与 $n$ 的完全二部图。
$C_n$：有 $n$ 个顶点的圈，就是一个大环。
$P_n$：有 $n$ 个顶点的通路，就是一条长路径。

There are a lot of definitions to keep track of in graph theory. Here is a glossary of the terms we have already used and will soon encounter.

图论中有许多定义需要记住。下面是我们已经用到、并且即将遇到的术语表。

Graph Theory Definitions 图论定义

Graph: A collection of vertices, some of which are connected by edges. More precisely, a pair of sets $V$ and $E$ where $V$ is a set of vertices and $E$ is a set of 2-element subsets of $V\text{.}$
Adjacent: Two vertices are adjacent if they are connected by an edge. Two edges are adjacent if they share a vertex.
Bipartite graph: A graph for which it is possible to divide the vertices into two disjoint sets such that there are no edges between any two vertices in the same set.
Complete bipartite graph: A bipartite graph for which every vertex in the first set is adjacent to every vertex in the second set.
Complete graph: A graph in which every pair of vertices is adjacent.
Connected: A graph is connected if there is a path from any vertex to any other vertex.
Chromatic number: The minimum number of colors required in a proper vertex coloring of the graph.
Cycle: A path (see below) that starts and stops at the same vertex, but contains no other repeated vertices.
Degree of a vertex: The number of edges incident to a vertex.
Euler path: A walk which uses each edge exactly once.
Euler circuit: An Euler path which starts and stops at the same vertex.
Multigraph: A multigraph is just like a graph but can contain multiple edges between two vertices as well as single edge loops (that is an edge from a vertex to itself).
Planar: A graph which can be drawn (in the plane) without any edges crossing.
Subgraph: We say that $H$ is a subgraph of $G$ if every vertex and edge of $H$ is also a vertex or edge of $G\text{.}$ We say $H$ is an induced subgraph of $G$ if every vertex of $H$ is a vertex of $G$ and each pair of vertices in $H$ are adjacent in $H$ if and only if they are adjacent in $G\text{.}$
Tree: A (connected) graph with no cycles. (A non-connected graph with no cycles is called a forest.) The vertices in a tree with degree 1 are called leaves.
Vertex coloring: An assignment of colors to each of the vertices of a graph. A vertex coloring is proper if adjacent vertices are always colored differently.
Walk: A sequence of vertices such that consecutive vertices (in the sequence) are adjacent (in the graph). A walk in which no vertex is repeated is called simple.

图（Graph）：若干顶点的集合，其中一些顶点由边相连。更精确地说，是一对集合 $V$ 与 $E$，其中 $V$ 是顶点集，$E$ 是 $V$ 的二元子集组成的集合。
相邻（Adjacent）：若两个顶点由一条边相连，则称它们相邻。若两条边共用一个顶点，则称它们相邻。
二部图（Bipartite graph）：可以把顶点分成两个不相交集合，使得同一集合内任意两个顶点之间都没有边的图。
完全二部图（Complete bipartite graph）：第一部中每个顶点都与第二部中每个顶点相邻的二部图。
完全图（Complete graph）：每一对顶点都相邻的图。
连通（Connected）：若从任意一个顶点到任何其他顶点都存在一条通路，则称该图连通。
色数（Chromatic number）：对该图做恰当顶点着色所需的最少颜色数。
圈（Cycle）：起点与终点相同、但不含其他重复顶点的通路（见下文）。
顶点的度（Degree of a vertex）：关联于某顶点的边数。
欧拉通路（Euler path）：恰好经过每条边一次的途径。
欧拉回路（Euler circuit）：起点与终点相同的欧拉通路。
多重图（Multigraph）：与图几乎一样，但可以含有连接两个顶点之间的多条边，也可以含有单边环（即从一个顶点连到自身的边）。
平面图（Planar）：可以不让任何边相交地画在平面上的图。
子图（Subgraph）：若 $H$ 的每个顶点和每条边也都是 $G$ 的顶点或边，则称 $H$ 是 $G$ 的子图。若 $H$ 的每个顶点都是 $G$ 的顶点，且 $H$ 中每对顶点在 $H$ 中相邻当且仅当它们在 $G$ 中相邻，则称 $H$ 是 $G$ 的导出子图。
树（Tree）：无圈（且连通）的图。（不连通且无圈的图称为森林。）树中度为 1 的顶点称为叶子。
顶点着色（Vertex coloring）：给图的每个顶点指定一种颜色。若相邻顶点总被着以不同颜色，则称该顶点着色是恰当的。
途径（Walk）：一个顶点序列，其中（序列中）相邻的顶点在（图中）也相邻。不含重复顶点的途径称为简单途径。