典型タグ

cycle space・fundamental cycle basis

無向graphで全頂点が偶数次数となる辺集合をF_2上のcycle space C(G)として扱い、連結成分数C、spanning forest F、各non-tree edge eが作る唯一のcycleからfundamental cycle basisとdim C(G)=M-N+Cを導く。連結graphではC=1なのでM-N+1となる。

この典型を扱う単元: cycle space・fundamental cycle basis

検索別名: cycle space、fundamental cycle basis、サイクル基底、サイクル空間

未知問からこの典型を見つける手掛かり

扱う対象
  • non-tree edge
  • s-t path
  • spanning forest
  • 無向graph
  • 辺集合
  • 連結成分
使う手掛かり
  • M-N\+Cが小さい
  • cycle族
  • simple path数を抑える
  • 辺集合をXOR
保つ不変量
  • P XOR P_0
  • dim C\(G\)=M-N\+C
  • 全頂点の次数が偶数
  • 対称差に関して閉じる
求めるもの
  • cycle basis構築
  • cycle空間の列挙
  • simple path数の上界
適用しない条件
個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果

分類と直接の前提

概念上の親: グラフモデルと構造

    関連する典型

    • 指定次数parityの部分グラフ構成: cycle spaceはincidence境界が0の辺集合全体であり、奇数次数頂点集合Tを固定したT-joinの解集合は、解が存在すればcycle spaceのaffine cosetになる。特に同じTを実現する二つの辺集合のXORはcycle spaceに属する。
    • XOR線形基底: 辺集合の対称差と整数のbitwise XORはどちらもF_2上の線形結合・独立性・基底で整理できるが、cycle spaceは偶数次数制約とfundamental cycleに固有の構成を持つ。

    学習成果と学習単位

    • spanning treeのroot-to-vertex XOR potentialで辺ラベルをfundamental cycleのXORへ変換し、cycle spaceの線形像が非木辺ごとのcycle XORのspanと一致することを示して、walkへ挿入できるXOR値をbasisで表せる。

      cycle space・fundamental cycle basisで学ぶ
    • 無向graphの全頂点が偶数次数となる辺集合を、対称差を加法とするF_2上のcycle spaceとして扱い、spanning forestと各non-tree edgeが作るfundamental cycleからbasisを構成して、連結成分数Cに対するdim C(G)=M-N+Cを導ける。連結graphではC=1となる。さらに同一連結成分内のs,tに対して固定したs-t path P_0を取ると、任意のs-t path PについてPhi(P)=P XOR P_0がcycle spaceに属し、Phi(P) XOR P_0=Pからこの写像が単射であることを示せる。したがってcycle-space dimensionを用いて、s-t path族の大きさを2^(dim C(G))以下に抑えられる。

      cycle space・fundamental cycle basisで学ぶ

    代表問題

    この典型の考え方を具体的な問題で確かめるための入口です。

    関連問題

    この典型が主タグまたは補助タグとして付いている問題です。