単一サイクル成分とgraph core
連結成分の辺数と頂点数からcycle rankを判定し、必要なら葉を反復削除してcycle coreと削除順を得る。
この典型を扱う単元: 単一サイクル成分とgraph core
検索別名: 2-core、graph peeling、葉刈り
未知問からこの典型を見つける手掛かり
- 扱う対象
- core
- degree
- graph
- 辺数
- 連結成分
- 頂点数
- 使う手掛かり
- E=V
- 次数未満を除去
- 葉を反復削除
- 辺数と頂点数
- 保つ不変量
- cycle rank
- 削除queue
- 現在次数
- 求めるもの
- cycle core
- 単一cycle
- 残存頂点
- 適用しない条件
- 個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果
分類と直接の前提
概念上の親: グラフモデルと構造
関連する典型
- 有向cycle検出・sink/source peeling: 局所次数条件を満たさない頂点をqueueで除き、残存核の不変条件を読む発想が共通する。
学習成果と学習単位
連結成分のE−V+1から独立な閉路数を判定し、E=Vなら唯一のcycleを持つことを示せる。必要なら次数1以下の頂点を反復削除し、残るcoreと削除順を求められる。
単一サイクル成分とgraph coreで学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。