离散数学总结图论

的图称为半欧拉图。规定平凡图是欧拉图。欧拉图的判定无向图G是欧拉图当且仅当G是连通图,且G中没有奇度顶点。无向图G是半欧拉图当且仅当G是连通的,且G中恰有两个奇度顶点。有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度都等于出度。有向图D是半欧拉图当且仅当D是单向连通的,且D中恰有两个奇度顶点,其中一个的入度比出度大1,另一个的出度比入度大1,而其余顶点的入度都等于出度。G是非平凡的欧拉图当且仅当G是连通的且为若干个边不重的圈的并。Fleury算法,能不走桥就不走桥哈密顿图经过图(有向图或无向图)中所有顶点一次且仅一次的通路称为哈密顿通路。经过图中所有顶点一次且仅一次的回路称为哈密顿回路。具有哈密顿回路的图称为哈密顿图。具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图。平凡图是哈密顿图。哈密顿图的判定无向图G=<V,E>是哈密顿图,对于任意V1V,且V1≠,均有p(G-V1)≤|V1|无向图G=<V,E>是半哈密顿图,对于任意的V1V且V1≠,均有p(G-V1)≤|V1|+1设G是n阶无向简单图,若对于G中任意不相邻的顶点vi,vj,均有d(vi)+d(vj)≥n-1,则G中存在哈密顿通路。若d(vi)+d(vj)≥n,则G中存在哈密顿回路,从而G为哈密顿图。若D为n(n≥2)阶竞赛图,则D中具有哈密顿通路。设二部图G=<V1,V2,E>,|V1|≤|V2|,且|V1|≥2,|V2|≥2:?(1)若G是哈密顿图,则|V1|=|V2|。?(2)若G是半哈密顿图,则|V2|=|V1|+1。?(3)若|V2|≥|V1|+2,则G不是哈密顿图,也不是半哈密顿图。带权图设图G=<V,E>(无向图或有向图),W:E→R,对G的每一条边e,称W(e)为边e的权,把这样的图称为带权图,记作G=<V,E,W>。设P是G中的一条通路,P中所有边的权之和称为P的长度,记作W(P)。即