指定次数parityの部分グラフ構成
選択辺集合の奇数次数頂点を指定し、spanning forestの葉から必要辺を確定してT-join型の構成を行う。
この典型を扱う単元: 指定次数parityの部分グラフ構成
検索別名: T-join、degree parity subgraph、次数偶奇部分グラフ
未知問からこの典型を見つける手掛かり
- 扱う対象
- forest
- 選択辺集合
- 頂点次数
- 使う手掛かり
- 偶奇を指定
- 次数を奇数に
- 保つ不変量
- 奇数頂点数は偶数
- 葉から確定
- 求めるもの
- parity条件
- 辺集合構成
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: グラフモデルと構造
関連する典型
- cycle space・fundamental cycle basis: cycle spaceはincidence境界が0の辺集合全体であり、奇数次数頂点集合Tを固定したT-joinの解集合は、解が存在すればcycle spaceのaffine cosetになる。特に同じTを実現する二つの辺集合のXORはcycle spaceに属する。
学習成果と学習単位
選択辺集合の奇数次数頂点を指定し、spanning forestの葉から必要辺を確定してT-join型の構成を行う。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
指定次数parityの部分グラフ構成で学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
- ABC345 F「Many Lamps」 公式問題主題: 指定次数parityの部分グラフ構成 / 主タグ
関連問題
この典型が主タグまたは補助タグとして付いている問題です。
- ABC345 F「Many Lamps」 公式問題主題: 指定次数parityの部分グラフ構成 / 主タグ