[圖論] degree sequence的定義不懂..

[MOONY135 (柳生劍影)]

A graphic sequence is a sequence of numbers which can be the
degree sequence of some graph.

看不太懂這個定義是在敘述甚麼?

Havel and Hakimi proved that (d_1, d_2, ..., d_n) is a degree sequence of a
simple graph if and only if (d_2-1,d_3-1,...d_d1+1-1,.....d_n) is



--
█◤◢█  ◢█◣ ◤◢█◣◥█◤ ◢█◣◥█ ◢█  ◢◣◥ █◣◥█◣◥█
█  █◤◢███ ◢███◣◥ ◢███◣◥ █◤◢██   ██  ██  █
█  █◢████ ██◤  █◣ ██◤  █◣ █◢███ ◣◥█◣█◤◢█
█◣◥█◤█◤█ ██    ██ ██    ██ ◥█◤  █ ◤  ███◤◢█
█◤◢█◢█◢█ ◥█  ◢█◤ ◥█  ◢█◤ ◢█  ◢█ ◢◤◥█◤◢██
█  █◤█◤█◤ ◣◥██◤◢◣ ◥██◤◢ █◤  █◤ ◥██◤ ωRyoko          

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.135.28.84
推 chuo        :就是給一串數字 他可不可以是一個simple graph各個
→ chuo        :頂點的degree  (數字要由大排到小)
→ chuo        :定理是說 如果這一串數字是degree sequence <=>
→ chuo        :第一個數字扣掉 然後第二個數字開始每個扣一
→ chuo        :總共扣了d_1這麼多個
→ chuo        :扣完後也是degree sequence
→ chuo        :EX: 現在有一串數列 (5 5 4 4 4 3 3 2)
→ chuo        :(5 5 4 4 4 3 3 2)是deg.sq.<=> (4 3 3 3 3 2 2)也是
→ MOONY135    :那他可以幹嘛呢?  搞不太懂...
推 suhorng     :判定所給的任意圖的degree 是否是能夠是某張簡單圖
→ suhorng     :的degree sequence
→ suhorng     :同時你可以注意到 照著他的步驟一步步遞迴(可以寫成
→ suhorng     :遞推...) 下去 其實可以順便給出一張(若存在)符合所
→ suhorng     :給定的degree sequence的簡單圖~
→ suhorng     :注意他每次左邊推到右邊時 degree seq.項數都會少一