欧拉路径回顾

发布时间 2023-08-25 16:23:52作者: xishanmeigao

最近打模拟赛发现这东西忘得差不多了,赶紧补一下

Part 1:知识点

定义

  • 经过图中所有边恰好一次的路径叫作欧拉路径
  • 如果欧拉路径的起点和终点相同,则称其为欧拉回路

判定

  • 有向图欧拉路径:图中恰好存在一个点的出度比入度多 \(1\)(起点 \(S\)),恰好存在一个点的入度比出度多 \(1\)(终点 \(T\)),其它点入度=出度