图论学习笔记

咳，要想解决如题的问题，我们首先要引入一些定理（仅在一张连通图中通用）。

我们先定义寄点是跟这个点相连的边数目有奇数个的点。对于能够一笔画的图，我们有一下两个定理。

定理1：如果一张图存在一笔画且不会回到起点，这个图有且只有2个寄点。（前提是图是连通的）。我们称这样的路径为欧拉路。。。所以我们也可以知道这玩意是谁恁出来的了。。。。。。。

定理2：如果一个张图存在一笔画且最后回到起点，这个图没有寄点。（前提是图是连通的）。我们称这样的路径为欧拉回路。

如果你知道了上面两个定理，恭喜你，你成功的解决了一笔画问题，如果要输出路径则只需要建立一个一维数组储存路径即可。

但是对于最少笔画问题我们应该怎么办呢？

这时候我们只需要引入一条推论即可。。。。。（怎么感觉很水的样子）

推论：对于不能一笔画的连通图来说，奇点数除以二便可算出此图需几笔画成。

至此，本博客研究的问题得解，咳QAQ。