图论

哥尼斯堡七桥问题

哥尼斯堡七桥问题：什么样的图形可以一笔画？-视频=李永乐

度数：每个点连接的线段数目，根据度数可将点分为奇点和偶点。
奇点：一般是落笔或收笔的点。
偶点：中间经过的点(一进一出)，如果落笔和收笔是同一个点，那该点也是偶点。

欧拉1736：奇点的的个数是零个或者\( 2\)个，才能一笔画。
(1) 零个：欧拉回路
(2) \( 2\)个：欧拉路径

欧拉说哥尼斯堡七桥问题有4个奇点，所以不能一笔画。那能几笔画呢？
一个图形，奇点个数必为偶数(考虑提笔和落笔)，假设这个偶数为\( 2k\)
(1) \( k\)笔画出；
(2) 增加\(k-1\)条线，于是只剩下两个奇点，满足欧拉路径；
(3) 增加\( k\)条线，满足欧拉回路。

弗勒里算法：
(1) 画一条线，删一条线；
(2) 不要把图形断开。

二分图