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で学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。