有向欧拉图的判别法【定理4-3】有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度都等于出度。【定理4-4】有向图D是半欧拉图当且仅当D是单向连通的，且D中恰好有两个奇度顶点，其中一个的入度比出度大1，另一个的出度比入度大1，而其余顶点的入度都等于出度。【定理4-5】G是

哈密尔顿问题和路径压缩1哈密尔顿回路和TSP路径与回路哈密尔顿问题偏计算机，欧拉问题偏数学，所以本章我们主要讲哈密尔顿回路和哈密尔顿路径哈密尔顿回路哈密尔顿路径欧拉回路欧拉路径哈密尔顿回路定义从一个点出发，沿着边走，经过每个顶点恰好一次，之后再回到出发点，过程

1．欧拉回路17世纪的东普鲁士有一座哥尼斯堡（Konigsberg）城（现为俄国的加里宁格勒（Kaliningrad）城），城中有一座奈佛夫（Kneiphof）岛，普雷格尔（Pregol）河的两条支流环绕其旁，并将整个城市分成

一、前置知识1、连通、极大联通子图连通：图中任意两点皆可互达极大连通子图：对连通图来说：是这个连通图本身对非连通图来说：有多个极大联通子图2、回路、简单回路