BUAA 离散数学2 知识点整理

离散数学
数学
Publish Date:   2024-08-25

图论

欧拉路径和欧拉回路

对于无向图

对于无向图，所有边都是连通的：

  • 存在欧拉路径的充分必要条件:度数为奇数的点只能有 0 或 2 个
  • 存在欧拉回路的充分必要条件:度数为奇数的点只能有 0 个

对于有向图

对于有向图，所有边都是连通的：

  • 要么所有点的出度均等于入度;要么除了两个点之外，其余所有点的出度等于入度，剩余的两个点:一个满足出度比入度多 1 (起点)，另一个满足入度比出度多 1 (终点)
  • 存在欧拉回路的充分必要条件:所有点的出度均等于入度。

算法：dfs 后序遍历，用边判重。序列倒序为终点到起点的欧拉路径。

Author: Yixiang Zhang
Link: http://zxdfcv.github.io/2024/08/25/BUAA-%E7%A6%BB%E6%95%A3%E6%95%B0%E5%AD%A62-%E7%9F%A5%E8%AF%86%E7%82%B9%E6%95%B4%E7%90%86/
Reprint policy: All articles in this blog are used except for special statements CC BY 4.0 reprint policy. If reproduced, please indicate source Yixiang Zhang !
离散数学
评论
  TOC