欧拉路

欧拉路

2019年11月5日 0 作者 Null NaN

欧拉路

本文由Sunset_Rl 写成,现代为发表
1. 连通无向图

  1. 奇度数的点0个或2个有0个时是欧拉回路,2个时是存在欧拉路当奇度数的点大于2时,奇度数点有2k个,那么可以通过k笔把图画出来一张图奇度数点的数量为偶数,如果对图中每一个点度数求和那么总和为2倍的边数,那么就一定为偶数,那么所有奇度数的点加起来的和为偶数,所以奇度数的点一点有两个
  2. 有向连通图图
  3. 所有点的入度等于出度的时候,就有欧拉回路
  4. 一个点的入度减出度和一个点的出度减入度都等于1,剩下所有点的入度等于出度

BEST定理:计算图中有多少种不同的欧拉路(做法:转成有多少种不同的生成树)把每个点最后一次走出的边拿出来,那么这些边会组成一棵生成树,所以会发现欧拉路的数量和生成树的定理 是一一对应的。

练习:给定无向图,要求把边分成两部分,使得任一部分的边都组成一条路径(m <= 1e4)

转化一下:用两条路径覆盖所有路径

思路:先判断连通块个数,如果大于2就直接舍弃;

如果连通块个数等于2,要保证每个连通块都是欧拉路;

如果连通块个数等于1,那么这个连通块就要被两笔画,那么奇度数 的点要<=4,等于0或2时,直接切开即可;

点数等于4时候,想办法把两笔画转换成1/0笔画问题,

在两个奇度数的点连一条边(虚边),再进行一笔画问题,然后再砍开就完事了