论文论文集论文题目欧拉图

定义：经过图中每条边一次且仅一次并且行遍图中每个顶点的通路（回路），称为欧拉通路或欧拉迹（欧拉回路或欧拉闭迹），存在欧拉回路的图称为欧拉图。以下是无向图和有向图是否存在欧拉通路或回路的判别法：定理1：无向图具有欧拉通路，当且仅当G是连通图且有0个或两个奇度顶点。若无奇度顶点，则通路为回路；若有两个奇度顶点，则它们是每条欧拉通路的端点。推论1：无向图G为欧拉图（具有欧拉回路）当且仅当G是连通的，且G中无奇度顶点。定理2：一个有向图D具有欧拉通路，当且仅当D是连通的，且除了两个顶点外，其余顶点的入度均等于出度。这两个特殊的顶点中，一个顶点的入度比出度大1，另一个顶点的入度比出度小1.推论2：一个有向图D是欧拉图（具有欧拉回路），当且仅当D是连通的，且所有顶点的入度等于出度。

图论起源于18世纪，1736年瑞士数学家欧拉（Euler）发表了图论的第一篇论文“哥尼斯堡七桥问题”。在当时的哥尼斯堡城有一条横贯全市的普雷格尔河，河中的两个岛与两岸用七座桥连结起来，见图（1）。当时那里的居民热衷于一个难题：有游人怎样不重复地走遍七桥，最后回到出发点。 为了解决这个问题，欧拉用A,B,C,D4个字母代替陆地，作为4个顶点，将联结两块陆地的桥用相应的线段表示，如图（2），于是哥尼斯堡七桥问题就变成了图（2）中，是否存在经过每条边一次且仅一次，经过所有的顶点的回路问题了。欧拉在论文中指出，这样的回路是不存在的。 欧拉图图G的一个回路，若它恰通过G中每条边一次，则称该回路为欧拉回路。存在欧拉回路的图就是欧拉图。 只存在欧拉通路的图不能叫做欧拉图，可以叫做欧拉半图。 欧拉图是普通逻辑学中的重点之一，图论的一部分，可以直观的表示概念间的关系，刑事侦查逻辑里有实际用途。编辑本段关于欧拉图的定理 1.无向连通图G是欧拉图，当且仅当G不含奇数度结点(G的所有结点度数为偶数)； 2.无向连通图G含有欧拉通路，当且仅当G有零个或两个奇数度的结点； 3.有向连通图D是欧拉图，当且仅当D中每个结点的入度＝出度 4.有向连通图D含有欧拉通路，当且仅当D中除两个结点外，其余每个结点的入度＝出度，且此两点满足deg－(u)－deg＋(v)＝±1。（起始点s的入读=出度+1，结束点t的出度=入度+1 或两个点的入读=出度）