锐客网

  1. 首页 > it技术 > >

欧拉路与欧拉回路

对无向图：
定义：给定无孤立结点图G，若存在一条路，经过图中每条边一次且仅仅一次，该条路称欧拉路，若存在一条回路，经过图中每边一次且仅仅一次，该回路称为欧拉回路。具有欧拉回路的图称为欧拉图，不是柏拉图。
定理：无向图G具有一条欧拉路，当且仅当G是连通的，且有0个或者是两个奇数度得结点。
推论：无向图G具有一条欧拉回路，当且仅当G是连通的，并且所有结点的度数均为偶数。
一笔画问题就是典型的这类问题：要判定一个图G是否可一笔画出，有两种情况， 从图中某一个结点出发，经过图G中每个边一次再回到该结点，或者是从G中某一个结点出发，经过G中每边一次且仅一次到达另一个结点，分别对应着欧拉回路和欧拉路的问题
对有向图：
定义：给定有向图G，通过图中每边一次且仅一次的一条单向路（回路），称作单向欧拉路（回路）。
定理：有向图G具有 单向欧拉路，当且仅当它是连通的，而且除两个结点外，每个结点的入度等于出度，但这两个结点中，一个结点的入度比出度大1，另一个结点的入度比出度小1。
定理：有向图G具有一条单向欧拉回路，当且仅当是连通的，且每个结点入度等于出度。
【欧拉路与欧拉回路】转载于:https://www.cnblogs.com/hpustudent/archive/2011/08/11/2134843.html

    推荐阅读


    上一篇：不仅仅是笑哦|如何装B

    下一篇：zigbee 2（OSAL概要）