离散数学 图论基础知识总结

无序对:
两个元素构成的集合{a,b}$\{a,b\}$称为无序对，
若A,B$A,B$为两个集合，则 {{a,b}|a∈A∧b∈B}$\{\{a,b\}|a\in A\wedge b\in B\}$ 为A$A$与B$B$ 构成的无序积

与笛卡尔积的区别在于构成笛卡尔积是由有序对构成
无序积 中的无序对的两个元素不分次序同时又可以是相同的

多重集合
集合中的元素可以重复出现，和Multimap 或 Multiset 中类似

重复度为元素在多重集合中出现的次数

无向图

一个无向图G是一个二元组 <V,E>$<V,E>$, 即 G=<V,E>$G=<V,E>$
V$V$是顶点集，是一个非空的有穷集合（意思为一个无向图里面至少有一个顶点，并且顶点的个数是有限的）
E$E$是边集，它是无序积V$V$&V$V$的一个有穷的多重子集 通俗来说就是 可以存在重边，以及自环

有向图
D=<V,E>$D=<V,E>$
和无向图的区别就是 边是有方向的

几个概念

n阶图 : 有n个顶点
零图 : 没有边
平凡图：只有一个顶点，没有边，即一阶零图
空图：没有点，没有边记为 ∅$\varnothing$ 在定义中规定顶点集非空，但是在图的运算中可能产生空图

在无向图G=<V,E>$G=<V,E>$中，设边e=(vi,vj)∈E$e=(v_i,v_j)\in E$ vi,vj$v_i,v_j$ 为e$e$的端点
那么 e$e$与vi(vj)关联$v_i(v_j)关联$
如果 vi≠vj$v_i\ne v_j$ 那么 vi(vj)$v_i(v_j)$ 与 e$e$ 的关联次数为1
如果vi=vj$v_i=v_j$ 那么 vi(vj)$v_i(v_j)$ 与 e$e$的关联次数为2
若vk$v_k$不是e的端点 那么vk$v_k$与e$e$的关联次数为0

简单来说
如果这条边是自环 那个这个环所连的点与这个环的关联次数为2
如果是一条边 那么边的两个端点与这条边的关联次数为1
其他点与这条边的关联次数自然就为0了

在无向图中

如果两个顶点之间至少有一条边 这两个点 相邻
如果两条边有一个共同的点 这两条边相邻

有向图
D=<V,E>$D=<V,E>$ 中， e=<vi,vj>∈E$e=<v_i,v_j>\in E$ vi,vj$v_i,v_j$是e$e$的两个端点
vi$v_i$是e$e$的起点
vj$v_j$是e$e$的终点
e$e$与vi,vj$v_i,v_j$关联
vi$v_i$到vj$v_j$有一条边 那么这两个顶点相邻
称为
vi$v_i$邻接vj$v_j$
vj$v_j$邻接vi$v_i$
如果一条边的终点是另一条边的起点 那么这两边相邻
比如这样

此图中 e1$e_1$与e2$e_2$ 相邻

在无向图和有向图中

没有边关联的点 是 孤立点
两个端点重合的边 是 环

顶点的度数
无向图G=<V,E>$G=<V,E>$ vi∈V$v_i\in V$ 那么vi$v_i$连了几条边 那么它的度数就是多少
度记为dG(vi)$d_G(v_i)$ 简记为d(vi)$d(v_i)$
每个环给端点提供的度数为2

有向图D=<V,E>$D=<V,E>$ vi∈V$v_i\in V$
出度：vi$v_i$作为边的起点次数 （即有多少条边从它指向另一个端点） 记为d+(vi)$d^{+}(v_i)$
入度：vi$v_i$作为边的终点次数 (即有多少条边指向它) 记为d−(vi)$d^{-}(v_i)$
度数：作为边的端点次数 记为d(vi)$d(v_i)$
显然
d(vi)=d+(vi)+d−(vi)$d(v_i)=d^{+}(v_i)+d^{-}(v_i)$

度数为1的顶点为悬挂顶点
与悬挂顶点关联的边称为悬挂边
最大度：Δ=max{d(v)|v∈V(D)}$\mathrm{\Delta }=max\{d(v)|v\in V(D)\}$
最小度：δ=min{d(v)|v intV(D)}$\delta =min\{d(v)|vintV(D)\}$
最大出度：Δ+=max{d+(v)|v∈V(D)}${\mathrm{\Delta }}^{+}=max\{d^{+}(v)|v\in V(D)\}$
最小出度：δ+=min{d+(v)|v∈V(D)}${\delta }^{+}=min\{d^{+}(v)|v\in V(D)\}$
最大入度：Δ−=max{d−(v)|v∈V(D)}${\mathrm{\Delta }}^{-}=max\{d^{-}(v)|v\in V(D)\}$
最小入度：δ−=min{d−(v)|v∈V(D)}${\delta }^{-}=min\{d^{-}(v)|v\in V(D)\}$

握手定理
各顶点的度数之和为边数的两倍
∑ni=1d(vi)=2m$\sum _{i=1}^{n}d(v_i)=2m$
推论
任何图中，度数为奇数的顶点个数是偶数

简单证明:
∵$\because$ 所有度数之和必为偶数(由握手定理)
∵$\because$ 奇数个奇数+（偶数个或者奇数个）偶数 = 奇数
∴$\therefore$ 矛盾

定理6.2

所有顶点入度之和(∑(i=1)nd+(vi)$\sum _{(}i=1{)}^n{d}^{+}(v_i)$)=所有顶点出度之和(∑ni=1d−(vi)$\sum _{i=1}^n{d}^{-}(v_i)$)=边数(m)

度数列
设V={v1,v2,…,vn}$V=\{v_1,v_2,\dots ,v_n\}$ 为n阶图G的顶点集
称d(v1),d(v2),…,d(vn)$d(v_1),d(v_2),\dots ,d(v_n)$ 为G的度数列

对于有向图 可继续划分为 出度列和入度列

几个概念
平行边
在无向图中，关联一对顶点的无向边多余1条，这些边统称为平行便
重数
平行边的条数成为重数

有向平行边
有向图中，关联一对顶点的有向边多于1条，并且起点和终点相同（或者理解为方向相同）

多重图
含平行边的图

简单图
既不含平行边也不含环的图

显然 n阶简单无向图
Δ≤n−1$\mathrm{\Delta }\le n-1$

无向完全图
记为Kn$K_n$
简单说：每对顶点之间都有一条边的无向简单图
m=C2n=n(n−1)2$m=C_n^2=\frac{n(n-1)}{2}$

有向完全图
简单说：每对顶点之间均有两条方向相反的边的有向简单图
m=2C2n=n(n−1)$m=2C_n^2=n(n-1)$

k−$k-$正则图
无向简单图中，各顶点度数均等于k
由握手定理知 n阶k−$k-$正则图中边数m=kn2$m=\frac{kn}{2}$

n阶无向圈图
共有n条边，并且边的顺序是按点的顺序
直接给图：

边集E={<v1,v2>,<v2,v3>,<v3,v4>,<v4,v1>}$E=\{<v_1,v_2>,<v_2,v_3>,<v_3,v_4>,<v_4,v_1>\}$
记为Cn$C_n$

n阶有向圈图
和n阶无向圈图一样，只不过边加上了方向
给图：

边集E={<v1,v2>,<v2,v3>,<v3,v4>,<v4,v1>}$E=\{<v_1,v_2>,<v_2,v_3>,<v_3,v_4>,<v_4,v_1>\}$
记为Cn$C_n$

n阶轮图
就是在无向圈Cn−1(n≥4)$C_{n-1}(n\ge 4)$ 内放置一个顶点，使得该顶点与Cn−1$C_{n-1}$上的每个顶点相邻
所得的简单图 即为n阶轮图，记为Wn$W_n$

n方体图
简单来说，就是每个顶点与它相邻的顶点，他们的顶点标号的二进制表示只有一位不同 记为Qn$Q_n$

子图

G=<V,E>,G′=<V′,E′>$G=<V,E>,G^{{}^{\prime }}=<V^{{}^{\prime }},E^{{}^{\prime }}>$
两图都是无向图，或者两图都是有向图
如果G′中的点集和边集都⊆G$G^{{}^{\prime }}中的点集和边集都\subseteq G$
那么G′是G的子图，G是G′的母图$G^{{}^{\prime }}是G的子图，G是G^{{}^{\prime }}的母图$ 记为G′⊆G$G^{{}^{\prime }}\subseteq G$
如果G′≠G$G^{{}^{\prime }}\ne G$ 那么G′是G的真子图$G^{{}^{\prime }}是G的真子图$
如果V′=V$V^{{}^{\prime }}=V$ 那么 G′是G的生成子图$G^{{}^{\prime }}是G的生成子图$ (简单来说：生成子图就是 包含母图的所有顶点，但是包含一部分边（或者全部边）)

如果∅≠E1⊆E$\varnothing \ne E_1\subseteq E$
并且V1$V_1$为以E1$E_1$中的边关联的顶点全体为顶点集的G$G$的子图
称为E1$E_1$的导出子图 记作G[E1]$G[E_1]$

简单来说，就是取母图中的一个子边集，并且这些边的两端的端点构成子点集。

补图

就是在原图中，保留所有顶点，然后加边，使得原图变成完全图Kn$K_n$ 然后去掉原有的边，所得的图就是补图
G¯¯¯¯=V$\overline{G}=V$&V$V$ - G$G$

ps:原图和补图互为补图

如果
G¯¯¯¯≅G$\overline{G}\cong G$ 那么称它们为自补图

图的同构
简单来说 如果其中一个图通过变换可以变成另一个图，那么两图同构 记为G1≅G2$G_1\cong G_2$
或者说 若它们都是标定图，可以通过调整一个图的顶点次序，使得G1$G_1$和G2$G_2$有相同的度数列，那么两图同构

图的连通性
通路
G=<V,E>,设G中顶点和边的交替序列为Γ=v0e1v1e2⋯elvl$G=<V,E>,设G中顶点和边的交替序列为\mathrm{\Gamma }=v_0{e}_1{v}_1{e}_2\cdots e_l{v}_l$
要求:vi−1是ei的起点，vi是ei的终点$v_{i-1}是e_i的起点，v_i是e_i的终点$ i=1,2,⋯,l$i=1,2,\cdots ,l$
那么Γ为v0到vl的回路$\mathrm{\Gamma }为v_0到v_l的回路$
Γ中所含边数即为Γ的长度$\mathrm{\Gamma }中所含边数即为\mathrm{\Gamma }的长度$
若v0=vl$v_0=v_l$那么称通路为回路 （简单来说，就是通路的起点和终点一样）

简单通路
Γ中所有边各异$\mathrm{\Gamma }中所有边各异$，便是简单通路
若v0=vl$v_0=v_l$ 那么称Γ为简单回路$\mathrm{\Gamma }为简单回路$

初级通路
Γ中所有顶点各异，且所有边各异$\mathrm{\Gamma }中所有顶点各异，且所有边各异$ 称为初级通路或路径
若v0=vl$v_0=v_l$ 那么称Γ$\mathrm{\Gamma }$ 为初级回路或圈
长度为奇数的圈为奇圈，长度为偶数的圈为偶圈

复杂通路
在初级通路的基础上，Γ中有重边$\mathrm{\Gamma }中有重边$ 称Γ为复杂通路$\mathrm{\Gamma }为复杂通路$
v0=vl$v_0=v_l$ 复杂回路

备注
在无向图中，长度为1的圈由环给出，长度为2的圈由两条平行边给出，在无向简单图中，圈长至少为3,。
在有向图中，长度为1的圈由环给出。在有向简单图中，圈长至少为2

定理6.3
在一个n阶图中，若从顶点u$u$到v$v$(u≠v)$(u\ne v)$存在通路，则从u到v存在长度≤n−1的初级通路$u到v存在长度\le n-1的初级通路$
简单证明：把通路中重复出现的顶点去掉，这条通路就变成初级通路，既然顶点各异，边各异，长度必然≤n−1$\le n-1$

定理6.4
在一个n阶图中，如果存在v到自身的简单回路$v到自身的简单回路$, 则从v$v$到自身存在长度不超过n$n$的初级回路
简单证明：也是把重复顶点去掉

无向图连通性
若vi与vj之间存在通路$v_i与v_j之间存在通路$ 那么vi与vj是连通的$v_i与v_j是连通的$
规定vi与自身连通$v_i与自身连通$

连通图
无向图G$G$是平凡图（一阶零图，即只有一个顶点，没有边）或者G$G$中任意两个顶点都是连通的，则称G$G$是连通图
否则称G$G$是非连通图

连通分支
在原图的一个子图中，其中任意两个顶点都是相互可达，并且其中的任意顶点与子图以外的顶点都是不可达，那么称这个子图为连通分支（连通块）
连通分支的个数记为p(G)$p(G)$ 对于一个连通图，p(G)=1$p(G)=1$

短程线
vi与vj是连通的话，那么短程线就是vi到vj之间长度最短的通路$v_i与v_j是连通的话，那么短程线就是v_i到v_j之间长度最短的通路$
短程线的长度称为vi到vj之间的距离$v_i到v_j之间的距离$
记为d(vi,vj)$d(v_i,v_j)$ 若vi与vj之间不连通，那么规定d(vi,vj)=∞$v_i与v_j之间不连通，那么规定d(v_i,v_j)=\mathrm{\infty }$

三条性质
1° d(vi,vj)≥0并且当vi=vj时，等号成立$d(v_i,v_j)\ge 0并且当v_i=v_j时，等号成立$
2° d(vi,vj)+d(vj,vk)≥d(vi,vk)$d(v_i,v_j)+d(v_j,v_k)\ge d(v_i,v_k)$
3° d(vi,vj)=d(vj,vi)$d(v_i,v_j)=d(v_j,v_i)$

点割集
如果删去原图中的一些点，使得原图的连通性被破坏，或者说连通分支数量增加，并且如果少删一些点不能导致破坏连通性，那么这些点的集合称为点割集，如果点割集中只有一个点，那么称其为割点

备注：悬挂顶点不可能出现在点割集中

边割集
删去一些边，使得破坏连通性，并且少删一条都不行。 这些边组成的集合称为边割集，简称割集。若只有一条边，则称该边为割边或者桥

备注
1° 完全图Kn$K_n$无点割集
2° n阶零图既无点割集，也无边割集
3° 若G$G$是连通图，E′$E^{{}^{\prime }}$为G$G$的边割集，那么p(G−E′)=2$p(G-E^{{}^{\prime }})=2$
4° 若G$G$是连通图，V′是G的点割集$V^{{}^{\prime }}是G的点割集$，则p(G−V′)≥2而且可能p(G−V′)>2$p(G-V^{{}^{\prime }})\ge 2而且可能p(G-V^{{}^{\prime }})>2$

点连通度
κ(G)=min{|V′||V′是G的点割集或V′使(G−V′)只有一个顶点}$\kappa (G)=min\{|V^{{}^{\prime }}||V^{{}^{\prime }}是G的点割集或V^{{}^{\prime }}使(G-V^{{}^{\prime }})只有一个顶点\}$
那么称κ(G)是G的点连通度$\kappa (G)是G的点连通度$

边连通度
λ(G)=min{|E′||E′是G的边割集}$\lambda (G)=min\{|E^{{}^{\prime }}||E^{{}^{\prime }}是G的边割集\}$
那么称λ(G)为G的边连通度$\lambda (G)为G的边连通度$

备注
1° 若G是平凡图，则κ(G)=λ(G)=0这里约定min∅=0$若G是平凡图，则\kappa (G)=\lambda (G)=0这里约定min\varnothing =0$
2° 若G是完全图Kn,由于G无点割集，那么显然当删除n−1个顶点之后，G变成平凡图，所以κ(G)=n−1$若G是完全图K_n,由于G无点割集，那么显然当删除n-1个顶点之后，G变成平凡图，所以\kappa (G)=n-1$
3° 若G中存在割点，则κ(G)=1；若G中存在割边（桥），则λ(G)=1$若G中存在割点，则\kappa (G)=1；若G中存在割边（桥），则\lambda (G)=1$

定理6.5
对于任何无向图G，有
κ(G)≤λ(G)≤δ(G)$\kappa (G)\le \lambda (G)\le \delta (G)$

有向图连通性
设D=<V,E>为有向图，设vi,vj为D中任意两个顶点$设D=<V,E>为有向图，设v_i,v_j为D中任意两个顶点$
vi到vj之间有通路，那么称vi可达vj，规定vi到自身总是可达$v_i到v_j之间有通路，那么称v_i可达v_j，规定v_i到自身总是可达$
若vj可达vi，那么称vi与vj是相互可达的$若v_j可达v_i，那么称v_i与v_j是相互可达的$
若vi到vj之间存在通路，那么最短的通路称为短程线，短程线的长度称为vi到vj的距离$若v_i到v_j之间存在通路，那么最短的通路称为短程线，短程线的长度称为v_i到v_j的距离$

弱连通图或连通图
D为一有向图，如果略去方向所得图是连通图，那么D为弱连通图或连通图$D为一有向图，如果略去方向所得图是连通图，那么D为弱连通图或连通图$

单向连通图
D中任意两顶点至少一个可达另一个$D中任意两顶点至少一个可达另一个$

强连通图
D中任意两顶点相互可达$D中任意两顶点相互可达$

判别有向图D是否为强联通或是否为单向连通$判别有向图D是否为强联通或是否为单向连通$
1° 若有向图D中存在经过每个顶点至少一次的回路，则D是强联通的$若有向图D中存在经过每个顶点至少一次的回路，则D是强联通的$
2° 若有向图D中存在经过每个顶点至少一次的通路，则D是单向连通的$若有向图D中存在经过每个顶点至少一次的通路，则D是单向连通的$

图的矩阵表示

无向图的关联矩阵
设无向图G=<V,E>,V={v1,v2,⋯,vn},E={e1,e2,⋯,em}$设无向图G=<V,E>,V=\{v_1,v_2,\cdots ,v_n\},E=\{e_1,e_2,\cdots ,e_m\}$
令mij为顶点vi与边ej的关联次数,则称(mij)n×m为G的关联矩阵，记作M(G)$令m_{ij}为顶点v_i与边e_j的关联次数,则称(m_{ij}{)}_{n\times m}为G的关联矩阵，记作M(G)$

mij的取值有三种$m_{ij}的取值有三种$
0(vi与ej不关联)$0(v_i与e_j不关联)$
1(vi与ej关联一次)$1(v_i与e_j关联一次)$
2(ej是以vi为端点的环)$2(e_j是以v_i为端点的环)$

五条性质
1° ∑ni=1mij=2，即M(G)各列元素之和为2$\sum _{i=1}^n{m}_{ij}=2，即M(G)各列元素之和为2$
2° ∑mi=1mij=d(vi)，即M(G)第i行元素之和为vi的度数$\sum _{i=1}^m{m}_{ij}=d(v_i)，即M(G)第i行元素之和为v_i的度数$
3° ∑ni=1d(vi)=∑ni=1∑mj=1=∑mj=1∑i=1n=∑mi=12=2m(握手定理)$\sum _{i=1}^{n}d(v_i)=\sum _{i=1}^n\sum _{j=1}^m=\sum _{j=1}^m\sum _{i=1}n=\sum _{i=1}^{m}2=2m(握手定理)$
4° 若第j列与第k列相同，当且仅当ej与ek是平行边$若第j列与第k列相同，当且仅当e_j与e_k是平行边$
5° ∑mj=1mij=0，当且仅当顶点vi为孤立点$\sum _{j=1}^m{m}_{ij}=0，当且仅当顶点v_i为孤立点$

有向无环图的关联矩阵
有向图中的mij有三种取值$m_{ij}有三种取值$
1(vi为ej的起点)$1(v_i为e_j的起点)$
0(vi与ej不关联)$0(v_i与e_j不关联)$
−1(vi是e)j的终点)$-1(v_i是e)j的终点)$

五条性质
1° 每列恰有一个1和一个-1(规定图中无环)
2° 1的总个数等于-1的总个数，等于边数
3° 第i行中1的个数等于vi的出度，−1的个数等于vi的入度$第i行中1的个数等于v_i的出度，-1的个数等于v_i的入度$
4°第j列与第k列相同当且仅当ej和ek是平行边$第j列与第k列相同当且仅当e_j和e_k是平行边$
5° 第i行全为0当且仅当vi是孤立点$第i行全为0当且仅当v_i是孤立点$

有向图的邻接矩阵
设有向图D=<V,E>,V={v1,v2,⋯,vn},|E|=m,令a(1)ij为顶点vi邻接到顶点vj的边的条数，称(a(1)ij)n×n为D的邻接矩阵，记为A(D)$D=<V,E>,V=\{v_1,v_2,\cdots ,v_n\},|E|=m,令a_{ij}^{(1)}为顶点v_i邻接到顶点v_j的边的条数，称(a_{ij}^{(1)}{)}_{n\times n}为D的邻接矩阵，记为A(D)$

两条性质
1° 第i行元素之和为vi的出度$第i行元素之和为v_i的出度$
2° 第j列元素之和为vj的入度$第j列元素之和为v_j的入度$

定理6.6
Al(l≥1)中的元素a(l)ij是vi到vj长度为l的通路数，∑i,ja(ijl)是D中长度为l的通路总数，其中∑ia(l)ij是D中长度为l的回路总数$A^l(l\ge 1)中的元素a_{ij}^{(l)}是v_i到v_j长度为l的通路数，\sum _{i,j}{a}_{ij}^{(}l)是D中长度为l的通路总数，其中\sum _i{a}_{ij}^{(l)}是D中长度为l的回路总数$

推论
Bl=A+A2+⋯+Al(l≥1),则Bl的元素b(l)ij是D中长度小于等于l的回路总数$B_l=A+A^2+\cdots +A^l(l\ge 1),则B_l的元素b_{ij}^{(l)}是D中长度小于等于l的回路总数$

可达矩阵
1表示vi可达vj$1表示v_i可达v_j$
0表示不可达$0表示不可达$

三条性质
1° 主对角线上的元素全为1，即pij=1,i≤i≤n$主对角线上的元素全为1，即p_{ij}=1,i\le i\le n$
2° D是强联通，当且仅当P(D)的元素全为1$D是强联通，当且仅当P(D)的元素全为1$
3° pij=1当且仅当b(n−1)ij≠0,1≤i,j≤n且i≠j$p_{ij}=1当且仅当b_{ij}^{(n-1)}\ne 0,1\le i,j\le n且i\ne j$

欧拉通路
G中存在经过每条边一次且一次的通路$G中存在经过每条边一次且一次的通路$
欧拉回路
G中存在经过每条边一次仅一次的回路$G中存在经过每条边一次仅一次的回路$
欧拉图
具有欧拉回路的图

定理6.10
判断欧拉图
无向图G中有欧拉回路，当且仅当G是连通图并且没有奇度顶点$无向图G中有欧拉回路，当且仅当G是连通图并且没有奇度顶点$
有向图D有欧拉回路，当且仅当D是连通的且所有顶点的入度等于出度$有向图D有欧拉回路，当且仅当D是连通的且所有顶点的入度等于出度$

哈密顿通路
G中经过每个顶点一次仅一次的通路$G中经过每个顶点一次仅一次的通路$
哈密顿回路
G中经过每个顶点一次仅一次的回路$G中经过每个顶点一次仅一次的回路$
哈密顿图
G中存在哈密顿回路$G中存在哈密顿回路$

三个性质
1° 存在哈密顿通路（回路）的图一定是连通图$存在哈密顿通路（回路）的图一定是连通图$
2° 哈密顿通路是初级通路，哈密顿回路是初级回路$哈密顿通路是初级通路，哈密顿回路是初级回路$
3° 若G中存在哈密顿回路，则一定存在哈密顿通路，反之不真$若G中存在哈密顿回路，则一定存在哈密顿通路，反之不真$

定理6.12
若删去一些点后，连通分支数>删去的点数，那么这个图一定不是哈密顿图

推论
有割点的图一定不是哈密顿图

定理6.13
设G是n(n≥3)阶无向简单图，若对于G中每一对不相邻的顶点u,v,均有$设G是n(n\ge 3)阶无向简单图，若对于G中每一对不相邻的顶点u,v,均有$
d(u)+d(v)≥n−1，那么G中存在哈密顿通路$d(u)+d(v)\ge n-1，那么G中存在哈密顿通路$
若d(u)+d(v)≥n，那么G中存在哈密顿回路，即G是哈密顿图$若d(u)+d(v)\ge n，那么G中存在哈密顿回路，即G是哈密顿图$

推论
设G是n(n≥3)阶无向简单图，若δ(G)≥n2,则G是哈密顿图$设G是n(n\ge 3)阶无向简单图，若\delta (G)\ge \frac{n}{2},则G是哈密顿图$

定理6.14
在n(n≥2)阶有向图D=<V,E>中，如果略去所有有向边的方向，所得无向图中含生成子图Kn，则D中存在哈密顿通路$在n(n\ge 2)阶有向图D=<V,E>中，如果略去所有有向边的方向，所得无向图中含生成子图K_n，则D中存在哈密顿通路$