※ 引述《hcsoso (索索)》之銘言：
: ※ 引述《hanabiz (死神的精準度)》之銘言：
: 目前找到最好的 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
感謝強者的回應.
如果我現在把圖A再加入2個條件限制
constrain 1: 圖A為數個任意維度的cube {k1, k2, ... , km }的圖所交集而成.
constrain 2: 設 ki,kj∈{k1, k2, ..., km }, 在圖A中, 若 ki∩kj≠ Ø,
則 ki∩kj 也必定為cube.
圖例 http://0rz.tw/tLVLO
這樣的話有辦法證明圖A也是 n-cube的子圖嗎?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.116.82.30