點核

點核(vertex core)圖論的一個重要概念.指圖的一個子圖.由圖G的基數與G的邊覆蓋數相等的所有獨立集的並所產生的節點導出子圖,稱為G的點核。

基本介紹

  • 中文名:點核
  • 外文名:vertex core
並非所有的圖都存在點核.由G的基數與G的點覆蓋數相等的所有邊獨立集的並所產生的邊導出子圖,稱為G的邊核.同樣,並非所有的圖都有邊核.但已證明:一個圖有點核若且唯若它有邊核;且它們都與存在外最小覆蓋等價.

相關詞條

熱門詞條

聯絡我們