VF2 algoritmasının çalışan herhangi bir örneği?

Question

İki grafik izomorfik olup olmadığını bulmak için VF2 algorithm okuyorum ama bir şekilde büyük resmi eksik. Bu alandaki ilgili arka planı kaçırıyor olabilirim ama gördüğüm her adımda, adımların neden uygulandığına dair sezgisel bir açıklama görmeden, her adımda kullanmam gereken bir dizi kural var. Temel Googling'ten, bu iki grafiğin izomorfik olup olmadığını bulmak için de facto algoritmalardan biri olarak kabul edilir, ancak bir nedenden ötürü yüksek bir seviyede anlaşılması için yeterince basit bir açıklama bulamamış gibi görünmektedir. Yoksa bu algoritma farklı bir adla mı biliniyor?

Her durumda, bu algoritmanın nasıl çalıştığına dair çalışan örneklerden haberdar olan biri var mı?

Answer 1

Aradığın şeyin bu olduğundan emin değilim, ancak VF2 algoritması aşağıdaki gibi devam ediyor.

let size 2 grafikleri olduğunu varsayalım: V ve V 've V ile V eşleştirmek istiyorum'

algoritma her adımda size biriyle V'in bir sonraki eleman maç çalışır, bir ağaca inmek V 've V' deki tüm düğümleri geçtiğinizde durursunuz (bir yaprak bulduğunuzda).

Algoritma:

• Birinci adım: 'boş grafik V ile boş V maç.
• İkinci adım: V'de bir düğüm ile matematik için V'de bir düğüm deneyin '
• ...
• N. adım: V'de bir yeni düğüm ile V'de bir düğüm maç çalışır' bunu yapamıyorsanız, ...
• ...
• END bir adım geriye ağacında gidip .. önceki adımda yeni bir maç denemek ve tekrar vb geri gidemem eğer: bir yaprak, yani sizi bulduğunda V ' tüm düğümleri ile gitti ya da bir yaprak bulamadan tüm ağaçtan geçerken. İşte

Örnek bir örnektir, algoritma ağacının soldan sağa doğru devam edin.

"Bir < -> B" V B düğümü'

Hope Daha net anlamak ve bu aradığın ne ile V'in Maç düğüm A anlamına gelir.

Answer 2

high-level overview of VF2 ve ayrıca oldukça kompakt bir from-scratch Java implementation for cheminformatics yazdım.