欧拉图和哈密顿图 客官°小女子只卖身不卖艺 2022-05-27 13:14 164阅读 0赞 ## 欧拉图及欧拉路径 ## * 欧拉图 * 如果图G上有一条经过所有顶点、所有边的闭路径(边不重复,顶点可以重复) * 充分必要条件 * 无向图:G连通,所有顶点的度都是偶数 * 有向图:G弱连通,每个顶点出度与入度相等 * 欧拉路径 * 如果图G上有一条经过所有顶点、所有边的路径(边不重复,顶点可以重复) * 充分必要条件 * 无向图:G连通,恰有两个顶点的度是奇数 * 有向图:G连通,恰有两个顶点的出度与入度不相等,其中一个出度比入度多1,另一个入度比出度多1。 ## 哈密顿图及哈密顿通路 ## * 哈密顿图 * 如果图G上有一条经过所有顶点的回路(不要求经过所有的边,也称作哈密顿回路) * 充分非必要条件:如果具有n个顶点的图G的每一对顶点度数之和不小于n,且n>=3 * 哈密顿通路 * 如果图G上有一条经过所有顶点的通路(非回路) * 充分非必要条件:如果具有n个顶点的图G的每一对顶点度数之和不小于n-1,那么G中有一条哈密顿通路 哈密顿通路问题在上世纪七十年代被证明是“NP完全的” ## 图的连通性 ## * u可达v * u=v或存在一条u到v的路径 * 连通的无向图 * 无向图中的任意两个顶点都是可达的 * 连通的有向图 * 有向图中的任意两个顶点都是互相可达的 * 单向连通的有向图 * 任意两个顶点至少从一个顶点到另一个顶点是可达的 * 弱连通的有向图 * 将有向图看作是无向图时是连通的
还没有评论,来说两句吧...