作者MOONY135 (柳生劍影)
看板Math
標題[圖論] degree sequence的定義不懂..
時間Fri Oct 21 23:00:58 2011
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
1F：推 chuo :就是給一串數字 他可不可以是一個simple graph各個 10/22 00:40
2F：→ chuo :頂點的degree (數字要由大排到小) 10/22 00:41
3F：→ chuo :定理是說 如果這一串數字是degree sequence <=> 10/22 00:42
4F：→ chuo :第一個數字扣掉 然後第二個數字開始每個扣一 10/22 00:42
5F：→ chuo :總共扣了d_1這麼多個 10/22 00:43
6F：→ chuo :扣完後也是degree sequence 10/22 00:43
7F：→ chuo :EX: 現在有一串數列 (5 5 4 4 4 3 3 2) 10/22 00:43
8F：→ chuo :(5 5 4 4 4 3 3 2)是deg.sq.<=> (4 3 3 3 3 2 2)也是 10/22 00:44
9F：→ MOONY135 :那他可以幹嘛呢? 搞不太懂... 10/22 22:22
10F：推 suhorng :判定所給的任意圖的degree 是否是能夠是某張簡單圖 10/22 22:31
11F：→ suhorng :的degree sequence 10/22 22:31
12F：→ suhorng :同時你可以注意到 照著他的步驟一步步遞迴(可以寫成 10/22 22:31
13F：→ suhorng :遞推...) 下去 其實可以順便給出一張(若存在)符合所 10/22 22:31
14F：→ suhorng :給定的degree sequence的簡單圖~ 10/22 22:31
15F：→ suhorng :注意他每次左邊推到右邊時 degree seq.項數都會少一 10/22 22:33