收縮(圖論術語)

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

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

基本介紹

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

定義

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

性質

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

套用

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

相關詞條

熱門詞條

聯絡我們