Belirli bir grafiğin başka bir grafiğin alt çizgisi olup olmadığını belirlemenin kolay yolu?

Question

Belirli bir grafiğin belirli bir grafiğin alt grafiğini olup olmadığını kontrol etmek için bir algoritma arıyorum.

Ben

• grafikleri yaklaşık < 20 köşeleri bu .. bu NP tam problem biraz daha uygulanabilir hale getirmek için birkaç şartım var.
• Grafikler DAG'dir.
• Tüm köşe noktaları benzersiz olarak etiketlenmemiş ve ana grafikte ve alt grafikte karşılık gelen köşe noktaları aynı etikete sahip olmalıdır. Doğru terminolojileri kullanıp kullanmadığımı bilmiyorum (çünkü bir grafik teorisi dersi almadım ...). Şunun gibi bir şey olacaktır:

A - B çizgi grafiği A - B - A alt grafiğidir, ancak A - A A - B - A alt yazı değildir.

Herhangi bir öneri iyi. Bu bir ev ödevi soru değil btw. : D

Answer 1

Etiketler benzersiz ise, N boyutunda bir grafik için, O(N^2) kenarları vardır; her köşe çifti arasında kendiliğinden döngüler veya çoklu kenarlar olmadığı varsayılır. Kenar sayısı için E kullanalım. Üst grafikte grubu kenarları karma durumunda (ve istenirse uygun bir miktarda)

, her bir karma tablo olup olmadığını kontrol etmek, alt grafiğini kenarlarından ilerleyebilir. Bunu her kenar için bir kere yapıyorsunuz, bu nedenle, O(E).

en ( N köşeler ile) grafiği G ve ( M köşeler ile) mümkün subgraph G_1 diyelim ve G_1 is in G bulmak istiyorum. etiketler benzersiz olmadığından

, sen, Dinamik Programlama ile, örneğin bunun yerine altproblemleri inşa edebilirsiniz - yerine O(2^N) altproblemleri, her alt grafiği için bir sahip, sen O(M 2^N) altproblemleri var - G_1 her köşe için bir (M ile olası alt grafiklerin her biri ile). temel durum index = M olmak

isSubgraph(index, bitmask) = 
    for all vertex in G 
     if G[vertex] is not used (check bitmask) 
      and G[vertex]'s label is equal to G_1[index]'s label 
      and isSubgraph(index + 1, (add vertex to bitmask)) 
       return true 
    return false 

ve bit maskesi (ve örtük etiketlemeyi verilen kenarlar eşitlik için kontrol edebilirsiniz:

G_1 is in G = isSubgraph(0, empty bitmask)

ve devletler gibi ayarlanır eşleme). Alternatif olarak, eğer kontrol etme işlemini if ​​(if) ifadesi içinde de yapabilirsiniz - sadece geçerli index no.lu geçerli kontrol G_1[0..index]'un G[bitmask] (aynı örtük etiket eşlemeyle) olduğunu tekrar kontrol etmeden önce kontrol edin.

N = 20 için, bu yeterince hızlı olmalıdır.

(notunuzu ekleyin ya da aşağıdakini DP kullanarak yeniden yazabilirsiniz).

Answer 2

Tamam, açık soruyu sormak zorundayım. 1. Yirmi köşeniz var. Dizeleri almak için önce her bir grafiğin derinliklerine, kardeşler arasındaki alfabetik sıraya göre yürüyün. 2. Bir grafik başka bir iff bir dizenin diğerinin bir alt grafiğidir.Bu yapılamaz hale getirmek için sorun şartnamede saklandığını başka ne Yani

?

Answer 3

Bunu bir hizalama sorunu olarak görüntüleyebilirsiniz. Temel olarak, V_1'deki her tepe noktasını V_2'de bir köşe çizgisine eşleyen ve numaralı bir eşleme eşleştirmesi yapmak istiyorsunuz. Bir olarak puanlanır bir hizalama harita aşağıdaki gibidir:

s: (a) = \ toplamı _ {(V, W) \ E_1 içinde} \ sigma (v, w, bir (V), a() a) ,

burada \ sigma (v, w, bir (v), bir (w)), (a (h), (a:)) \ içinde E-2, aksi takdirde 0

ise = 1 Bunun bir tamsayı doğrusal program şeklinde formüle edilebileceğini düşünüyorum.