离散数学——欧拉图复习

时间:2018-08-05 04:49:39
染雾
分享
WORD下载 PDF下载 投诉
定义1: 经过图中每条边一次且仅一次并且行遍图中每个顶点的通路,称为欧拉通路或欧拉迹。存在欧拉回路的图称为欧拉图。

定理1: 无向图G具有欧拉通路,当且仅当G是连通图且有零个或两个奇度顶点。若无奇度顶点,则通路为回路;若有两个奇度顶点,则他们是每条欧拉通路的端点。

推论 无向图G为欧拉图(具有欧拉回路)当且仅当G是连通图,且G中无季度顶点。

定理2: 一个有向图D具有欧拉通路,当且仅当D是连通的,且除了两个顶点外,其余顶点的入度均

离散数学——欧拉图复习

手机扫码分享

Top