收縮(圖論術語)

本詞條是多義詞,共4個義項
更多義項 ▼ 收起列表 ▲

中將關聯於一條邊的兩點用一個頂點代替,且該頂點關聯於所有被代替頂點的關聯的邊,該過程稱為該邊的收縮.

基本介紹

  • 中文名:收縮
  • 外文名:Edge Contraction 
  • 適用領域圖論 
  • 所屬學科數學 
定義,性質,套用,

定義

中,端點為
的收縮,就是用一個頂點代替
並且與該頂點關聯的邊包括除
之外所有與
的關聯的邊.所得到的圖一般記為
.

性質

收縮一條邊之後的圖
比原圖
少一條邊.

套用

遞歸計算生成樹棵數
為圖
的生成樹的棵數,若
不是,則
.
為圖
的邊集合.
遞歸計算染色多項式
簡單圖
的染色多項式,則
.
刪去邊
後得到的子圖.

相關詞條

熱門詞條

聯絡我們