欧拉图(P317)

欧拉通路

欧拉回路

欧拉图

半欧拉图

充分必要条件

定理1:无向图G是欧拉图当且仅当G是连通图且没有奇度定点

定理2:无向图G是半欧拉图当且仅当G是连通的且恰有两个奇度顶点

定理3:有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度等于出度

定理4:有向图是半欧拉图当且仅当D是单向连通的，并且D中恰有两个奇度顶点，其中一个的入度比出度大1，另一个的出度比入度大1，其余顶点的出度和入度相等

定理5:G是非平凡欧拉图当且仅当G是连通的且为若干个边不重的圈之并

哈密顿图(P320)

哈密顿通路

哈密顿回路

哈密顿图

半哈密顿图

目前为止没有找到便于判断的充分必要条件

定理6:设无向图G=<V,E>是哈密尔顿图，对于任意结点V的真子集V’，均有p(G-V’)<=|V’|

推论:设无向图G=<V,E>是半哈密尔顿图，对于任意的V的真子集V1，并且V1不是空集，都有p(G-V1)<=∣V1 ∣ + 1

定理7:设G是无向简单图，若对任意不相邻的顶点u,v，均有d(u) + d(v)>=n−1则G中存在哈密尔顿通路

推论:设G(n>=3)是无向简单图，若对G中任意不相邻的顶点u,v，均有d(u) + d(v)>=n则G中存在哈密尔顿回路

定理8:若D为n(n>=2)的竞赛图，则D中具有哈密尔顿通路