典型タグ

単一サイクル成分とgraph core

連結成分の辺数と頂点数からcycle rankを判定し、必要なら葉を反復削除してcycle coreと削除順を得る。

この典型を扱う単元: 単一サイクル成分とgraph core

検索別名: 2-core、graph peeling、葉刈り

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

扱う対象
  • core
  • degree
  • graph
  • 辺数
  • 連結成分
  • 頂点数
使う手掛かり
  • E=V
  • 次数未満を除去
  • 葉を反復削除
  • 辺数と頂点数
保つ不変量
  • cycle rank
  • 削除queue
  • 現在次数
求めるもの
  • cycle core
  • 単一cycle
  • 残存頂点
適用しない条件
個別の除外条件の記載はありません。扱う対象と使う手掛かりから適用を判断してください。
分類・前提・学習成果

分類と直接の前提

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

    関連する典型

    学習成果と学習単位

    • 連結成分のE−V+1から独立な閉路数を判定し、E=Vなら唯一のcycleを持つことを示せる。必要なら次数1以下の頂点を反復削除し、残るcoreと削除順を求められる。

      単一サイクル成分とgraph coreで学ぶ

    代表問題

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

    関連問題

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