loadingS(t0)：=[S(p0) | t0]； （表结构）
No3. P：=PU{t0}；T：=T\\{t0}；mark(t0)：=d(t0) No4. if t0=v then exit else goto No2； 我们也可以采用回溯方法。
算法二：在Dijkstra算法之后增加一个回溯系统，求出一条从u到v的最短路径。
No1. P：={u}；T：=V\\P；d(u)：=0；(?t∈T)(d(t)：=∞)； No2. (?t∈T)(d(t)：=min{d(t)，d(p)+w(p，t)})；
p?P
(?t0∈T)(?t∈T)(d(t0)≤d(t))；
No3. P：=PU{t0}；T：=T\\{t0}；mar(t0)：=d(t0) No4. S：=[v]；g：=v
No5. (?p∈P)(d(p)=d(g)=W(p，q))； s：=[p | s]； q：=p；
No6. ifg=u then exit else goto No3 以上两种算法都直接给出了从结点u到结点v的最短路径。但是，算法一的记忆比较庞大，而算法二又重复了Dijkstra算法中的一些判断过程。我们综合以上两种算法，又有如下
算法三：在求出从结点u到结点v的最短路径之间各结点的最短长度d值以及前驱结点（紧前结点）
No1. P：= {u}；T：=V\\P；d(u)：=0；(?t∈T)(d(t)：=∞)； No2. (?t∈T)(d(t)：=min{d(t)，d(p)+w(p，t)})；
p?P
(?t0∈T)(?t∈T)(d(t0)≤d(t))； (?p∈P)(d(p)=d(p0)+w(p0，t0))；
No3. P：=PU{t0}；T：=T\\{t0}；mark(t0)：=(p0，d(t0))； No4. if t0=v then exit else goto No2；
算法三并未直接给出从结点u到结点v的最短路径，但它的记忆系统比较简单，计算方便。要给出从结点u到v的最短路经时，只要从终步v开始，根据标记的第一个分量，向前回溯即可得到。 18．判断下列图示能否一笔画。
17
a a
b
c
[解] 根据本章§2定理2：图中奇结点的个数是偶数。所以奇结点的个数为2k，当
k=0，1时，此图是一笔画的，而当k＞1时，则此图是k笔画的。于是 图(a)，不是一笔画，因为它的奇结点为四个（用○·表示）； 图（b），（c）都是一笔画，因为它的奇结点是二个；
19．设G是有向图，证明G是Euler图的充要条件是：G是强连通的，且G中每一
结点的进度等于出度。 [证] 必要性
若G是Euler图，则G中含有有向Euler圈，并且G中无狐立点，从而G
中每个结点都与一条有向边相连。由于每条向边都必须在有向Euler圈上，因此每个结点也都在有向Euler圈上，所以从任一结点出发都可到达另一任意结点，故此G是强连通的。
而且，又由于每条有向边只能在有向Euler圈中出现一次，于是每一个结点，
有一边进来，就应有一边出去，再有一边进来，就应再有一边出来；这样，每一结点的进度必然等于度。 充分性
因为G是强连通的，故G中任何两个结点都可互相到达，因此G中存在着
有向简单圈。不妨设C是G中长度最长的有向简单圈套 ，则C必是G中的有向Euler圈，从而G是Euler图。
否则，必有边e不在圈C中，但e的一个端点在C上，不然的话，则图G
18
一定不强连通，这和已知条件矛盾。由于对于图G中每个点v，degG(u)= 并且C是一个有向圈，从而对图G1=（V（G），E（G）\\C）仍有=degG(u)= degG(u)，
degG(u)，故此在G1中一定存在含有e的有向圈C1中一定存在含e的有向圈
C1，C∪C1显然仍是G中的有向圈，且此有向圈的长度大于C的长度，这和C是G中最长的有向圈的假定相矛盾，故C一定是G中的有向Euler圈。 这个有向Euler圈C可利用一个算法给出： No1. 以G中任一结点出发，沿着有向边走
成一个圈，而且是简单圈套；
No2. 若此圈已是有向Euler圈，出口；
No3. 否则，除此圈外，必仍有若于边不在其中，这些边中至少有一条边以引中至少有一条边以此圈中的某一结点为起点，以这个结点为起点走出一个圈（这个别圈不应含原圈中的任一边，并且是一简单圈）；
No4. 将此圈插入原圈中，得到一个新的长度更长的简单圈，然后goto No2.
20．设G是连通的无向图，且有2k＞0奇结点。证明：在G中存在k条边不重的简
单路G1，C2，C3?Ck，使
E(G)=E(C1)∪E(C2)∪E(E3)∪?∪E(Ck)
[证] 设v1，v2，?，vk，vk+1?，v2k为G中的2k个奇结点，在vi和vi+k两个结点间
连以新边ei*(i=1，2，?，k)，所得之图记为G*，则G*的每个结点的度均为偶数，又由于G连通，则G*也是连通的，根据Euler定理，知在G*中存在Euler圈C*。若我们从C*中除去这k条新边ei*(i=1，2，?，k)，则C*就分解成k条边不重的简单路C1，C2，C3?Ck，并且显然有E(G)=E(C1)∪E(C2)∪E(C3)?∪E(Ck)。
21．构造一个长度为16的De Bruijn序列。
[解] 我们定义一个有向图D4如下：D4的项点是3位二进制数p1p2p3，其中pi=0或1。存在一条以项点p1p2p3为起点，以项点q1q2q3为终点的向边（p1p2p3，q1q2q3）当且仅当p2=q，p3=q2。另外，D4的每条有向边（p1p2p3，p2p3p4）上都标以四位二进制数p1p2p3p4。D4如下图1所示：
显然，D4是连通的，并且D4的每个项点都具有入度2和出度过2，故由有
19
向图的Euler定理，知D4中存在着一条有向Euler圈，这条有向Euler圈从图1可容易得到为
a1，a2,，a3，a4，a5，a6，a7，a8，a9，a10，a11，a12，a13，a14，a15，a16。 它可看作是D4的弧的序列，它产生一个长为24=16位二进制数0000111100101101（它恰好是由ai(i=1,16)的第一位数字组成），和鼓轮表面的设计要求符合。用这个16位二进制数设计的鼓轮如图2所示： 这个16位二进制数就是要求的长度为16的De B ruijn序列。
a1 弧 标号 a1 0000 a2 0001 000 a2 a16 a3 0011 a8 a4 0111 001 100 a5 1111
a15 a9 a6 1110 010 a7 1100 a8 1001 a10 a3 a14 a7 a9 0010 a10 0101 101 a11 a13 a11 1011 a12 0110 011 110 a12 a13 1101 a4 a6 a14 1010
111 a15 0100 a16 1000
a5 图1
20