论文部分内容阅读
一笔画定理是图论中的基本定理。在阐述它之前先介绍几个概念。在一个图中,包括了许多线和点。其中的点可这样分为两类:与其相连接的线的条数为偶数的点叫偶点;与其相连接的线的条数为奇数的点叫奇点。如图1,点B,D,H,F为奇点;A,C,E、G,I为偶点。引理1.一个图中奇点的个数必是偶数。引理2.(一笔画定理)一个图可以用一笔画完(每条线过且仅过一次)的充分必要条件是这个图中的奇点的个数为0或2。逆定理也成立。
The one-stroke painting theorem is the basic theorem in graph theory. Introduce a few concepts before explaining it. In one figure, many lines and points are included. The points can be divided into two categories: the even-numbered points of the connected lines are called even points; the odd-numbered points are called singular points. As shown in Figure 1, points B, D, H, and F are singularities; A, C, E, G, and I are even points. Lemma 1. The number of singularities in a graph must be even. Lemma 2. (stroke painting theorem) A sufficient and necessary condition for a graph to be drawn in one stroke (with each line passing over and only once) is that the number of singularities in this graph is 0 or 2. The inverse theorem also holds.