Luogu P1341 – 欧拉路径

  • 2018-11-27
  • 132
  • 0
  • 0

PROBLEM

https://www.luogu.org/problemnew/show/P1341

ANALYSIS

找到无向图中字典序最小的欧拉路径(不一定是回路),不存在则输出 No Solution .

起初考虑复杂了,写了一个没脑子的暴搜。

一笔画问题,如果有奇数入度节点,若数量不为2,则构不成欧拉回路。

如果数量为2,则一定从某一奇数入度节点开始画。

如果没有奇数入度结点,那么任何节点都可以作为起始点。

字典序还是比较好处理的。

定理一

  1. 连通的无向图 G有欧拉路径的充要条件是:  G中奇顶点(连接的边数量为奇数的顶点)的数目等于0或者2。
    (实际上,连通无向图中,奇顶点的数目总是偶数。)
  2. 连通的无向图 G是欧拉环(存在欧拉回路)的充要条件是: G中每个顶点的度都是偶数。

定理二

如果连通无向图 G2k个奇顶点,那么它可以用 k笔画成,并且至少要用 k笔画成。

SOLUTION

 

REFERENCE

  1. https://zh.wikipedia.org/wiki/%E4%B8%80%E7%AC%94%E7%94%BB%E9%97%AE%E9%A2%98
  2. https://www.luogu.org/problemnew/solution/P1341

CC BY-NC-SA 4.0 本作品使用基于以下许可授权:Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

评论

还没有任何评论,你来说两句吧