Re: [圖論] 如何證明A是否為B的子圖?

[hanabiz (死神的精準度)]

※ 引述《springgo (春哥)》之銘言：
: 先給定1個 n-cube的圖 B
: 現有一圖形A,
: A的vertex數小於2^n 且 A任一個vertex的degree均小於等於n
: 請問要如何證明A是否為B的子圖?



let n = 2

正方形B  .    .   (線請自行補上)

         .    .


三角形A  .    .   (線請自行補上)

         .

所以A不是B的subgraph


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.224.105.50
推 hcsoso      :如果把題目改成，請問什麼樣的條件A才為B的子圖呢？
→ hanabiz     :粗略地說 A的所有edge所形成的集合 必須
→ hanabiz     :包含於 B所有的edge所形成的集合
→ hanabiz     :也就是A不能有B沒有的邊囉
→ springgo    :檢查三角形的存在只是其中一個檢驗的方法, 當n值越高
→ springgo    :就需要其他條件來判別了.
推 hcsoso      :不曉得有沒有版大知道subgraph isomorphism problem
→ hcsoso      :在 bipartite 的狀況下有沒有多項式時間演算法呢？
→ hanabiz     :高維度也是可以有三角形的吧？
→ hanabiz     :反正你條件太鬆。