オイラー(閉)路についてまとめた

f:id:peroon:20210429001358p:plain

動機

  • trail, pathの違い、circuit, cycleの違いが曖昧で「オイラーパス」などという存在しない用語を発することがないようにまとめた
  • 頂点に注目した時の用語が path, cycle
  • 辺に注目した時の用語が trail, circuit
  • なのでオイラー路 = Eulerian-Trail である

オイラー(閉)路の計算量

参考

オイラー路の復元はdfsして帰りがけ順

  • 具体例として4頂点の完全有向グラフのオイラー(閉)路を求めてみる
  • 0を始点とし、まず0->0の辺を使い、次に0->1の辺を使い、1->0の辺を使い... という風に今まで使っていない辺を使ってdfsし、帰りがけ順に頂点を見るとオイラー(閉)路になっている
  • 下記画像のように実際に書いて確認した

f:id:peroon:20210429021658p:plain

int n, k;
int cur[26];
vector<int> path;

void dfs(int v) {
  while (cur[v] < k) {
    int u = cur[v]++;
    dfs(u);
    path.push_back(u); // dfsしてからリストに足すのは「帰りがけ順」
  }
}

int main() {
  scanf("%d%d", &n, &k);

  // k=4の場合

  dfs(0);
  debug(path); // => {0, 3, 3, 2, 2, 3, 1, 2, 1, 1, 3, 0, 2, 0, 1, 0}

  printf("a");
  for (int i = 0; i < n - 1; ++i)
    printf("%c", path[i % path.size()] + 'a');
  printf("\n");
}

追記

  • 辺を頂点とみてdfsしたと考えるほうが正しいか

f:id:peroon:20210807063636p:plain

オイラー(閉)路を使う問題