推 springgo :感寫解答 08/31 16:41
※ 引述《hanabiz (死神的精準度)》之銘言：
: ※ 引述《springgo (春哥)》之銘言：
: : 先給定1個 n-cube的圖 B
: : 現有一圖形A,
: : A的vertex數小於2^n 且 A任一個vertex的degree均小於等於n
: : 請問要如何證明A是否為B的子圖?
目前找到最好的 citation:
Embedding trees in a hypercube is NP-complete,
A Wagner, DG Corneil - SIAM Journal on Computing, 1990 http://0rz.tw/oTsd5
換句話說，對於一棵樹 T 要判斷是不是 n-cube 的子圖是一件很難的事...
更不用說對於一般圖 A 了。
不過，對於可以放進一個 n-cube 的圖，已經有人證明了 iff conditions:
B-valuations of graphs,
I Havel, J Moravek - Czech. Math. J, 1972 http://dml.cz/dmlcz/101102
例如 trees 都可以放進 n-cube 中。
最後是一篇 survey:
Embeddings in Hypercubes,
M Livingston - 1988 http://www.eecs.umich.edu/~qstout/pap/hypembed.pdf
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.133.15.15