关于欧拉路径 汉密尔顿路径 以及其他
如果给定无孤立结点图G若存在一条路,经过图中每边一次且仅一次这条条路称为欧拉路;若存在一条回路,经过图中每边一次且僅一次那么该回路称为欧拉回路。存在欧拉回路的图称为欧拉图。对于无向图G具有一条欧拉路,当且仅当G是连通的且有零个或两個奇数度结点。
有向图G具有一条单向欧拉路当且仅当是可达的,且每个结点入度等于出度一个有向图G具有单向欧拉路,当且仅当是可達的而且除两个结点外,每个结点的入度等于出度而这两个结点中,一个结点的入度比出度大1另一个结点的入度比出度小1。
汉密尔頓路 给定图G若存在一条路,经过图中每个结点恰好一次这条路称作汉密尔顿路。
汉密尔顿回路 给定图G若存在一条回路,经过图中每個结点恰好一次这条回路称作汉密尔顿回路。
汉密尔顿图 具有汉密尔顿回路的图称作汉密尔顿图。
定理 5.4.3 若图G=<VE>具有汉密尔顿回路,则对于结点集V的每个非空子集S均有 成立。
定理 5.4.4 设G为具有n个结点的简单图如果G中每一对结点度数之和大于等于n-1,则在G中存在一条漢密尔顿路
定理 5.4.5 设G是具有n个结点的简单图,如果G中每一对结点度数之和大于等于n则在G中存在一条汉密尔顿回路。