Alt grafik izomorfizmi sorunu - Subgraph isomorphism problem - Wikipedia

İçinde teorik bilgisayar bilimi, alt grafik izomorfizmi problem hesaplamalı bir görevdir ve iki grafikler G ve H girdi olarak verilir ve birinin G içerir alt grafik yani izomorf -e HAlt grafik izomorfizmi, her ikisinin de bir genellemesidir. maksimum klik sorunu ve bir grafiğin bir Hamilton döngüsü ve bu nedenle NP tamamlandı.[1] Bununla birlikte, alt grafik izomorfizminin diğer bazı durumları polinom zamanında çözülebilir.[2]

Bazen isim alt grafik eşleştirme aynı problem için de kullanılır. Bu isim, çıplak karar probleminin aksine böyle bir alt grafiğin bulunmasına vurgu yapmaktadır.

Karar sorunu ve hesaplama karmaşıklığı

Alt grafik izomorfizminin NP-tamamlandığını kanıtlamak için, bir karar problemi. Karar probleminin girdisi bir çift grafiktir G ve H. Sorunun cevabı olumlu ise H bir alt grafiğine izomorfiktir Gaksi takdirde negatif.

Resmi soru:

İzin Vermek , grafikler olun. Alt grafik var mı öyle ki ? Örneğin, bir birebir örten öyle ki ?

Alt grafik izomorfizminin NP-tamamlandığının kanıtı basittir ve klik sorunu, girdinin tek bir grafik olduğu NP-tam karar problemi G ve bir sayı kve soru şu: G içerir tam alt grafik ile k köşeler. Bunu bir alt grafik izomorfizm problemine çevirmek için, izin verin H tam grafik ol Kk; sonra alt grafik izomorfizm probleminin cevabı G ve H klik sorununun cevabına eşittir G ve k. Klik sorunu NP-tamamlandığından, bu polinom zamanlı çok bir indirgeme alt grafik izomorfizminin de NP-tamamlandığını gösterir.[3]

Alternatif bir indirgeme Hamilton döngüsü problem bir grafiği çevirir G Hamiltonisite için grafik çiftinde test edilecek olan G ve H, nerede H aynı sayıda köşeye sahip bir döngüdür G. Çünkü Hamilton döngüsü problemi NP-tamamlandı düzlemsel grafikler bu, alt grafik izomorfizminin düzlemsel durumda bile NP-tamamlandığını gösterir.[4]

Alt grafik izomorfizmi, grafik izomorfizm problemi olup olmadığını soran G izomorfiktir H: grafik izomorfizm sorununun cevabı, ancak ve ancak G ve H her ikisi de aynı sayıda köşe ve kenara sahiptir ve alt grafik izomorfizm problemi G ve H doğru. Bununla birlikte, grafik izomorfizminin karmaşıklık-teorik durumu açık bir soru olarak kalır.

Bağlamında Aanderaa – Karp – Rosenberg varsayımı üzerinde sorgu karmaşıklığı monoton grafik özelliklerinin Gröger (1992) herhangi bir alt grafik izomorfizm probleminin sorgu karmaşıklığına sahip olduğunu gösterdi Ω (n3/2); diğer bir deyişle, alt grafik izomorfizminin çözülmesi, input (n3/2) grafikte farklı kenarlar.[5]

Algoritmalar

Ullmann (1976) alt grafik izomorfizm problemini çözmek için yinelemeli bir geri izleme prosedürünü açıklar. Çalışma süresi genel olarak üstel olmasına rağmen, herhangi bir sabit seçim için polinom zaman alır. H (seçimine bağlı olan bir polinom ile H). Ne zaman G bir düzlemsel grafik (veya daha genel olarak bir grafik sınırlı genişleme ) ve H düzeltildi, alt grafik izomorfizminin çalışma süresi azaltılabilir doğrusal zaman.[2]

Ullmann (2010) 1976 altgraf izomorfizm algoritma kağıdına yönelik önemli bir güncellemedir.

Cordella (2004) 2004 yılında, farklı buluşsal yöntemler kullanarak iyileştirme sürecini iyileştiren ve önemli ölçüde daha az bellek kullanan Ullmann's, VF2'ye dayanan başka bir algoritma önerdi.

Bonnici (2013) bazı buluşsal yöntemler kullanarak köşelerin başlangıç ​​sırasını iyileştiren daha iyi bir algoritma önerdi.

Büyük grafikler için, son teknoloji ürünü algoritmalar arasında CFL-Match ve Turboiso ve bunun üzerine DAF gibi uzantılar, Han (2019).

Başvurular

Alt grafik izomorfizmi alanında uygulandığı için şeminformatik kimyasal bileşikler arasındaki benzerlikleri yapısal formüllerinden bulmak; genellikle bu alanda terim alt yapı araması kullanıldı.[6] Bir sorgu yapısı genellikle bir yapı editörü programı; GÜLÜMSEME tabanlı veritabanı sistemleri tipik olarak sorguları tanımlar. AKILLI, bir GÜLÜMSEME uzantı.

Bir grafiğin izomorfik kopya sayısını sayma ile yakından ilgili problem H daha büyük bir grafikte G veritabanlarında model keşfine uygulanmıştır,[7] biyoinformatik protein-protein etkileşim ağlarının[8] ve üstel rastgele grafik matematiksel modelleme yöntemleri sosyal ağlar.[9]

Ohlrich vd. (1993) alt grafik izomorfizminin bir uygulamasını tanımlayın Bilgisayar destekli tasarım nın-nin elektronik devreler. Alt grafik eşleştirme de bir alt adımdır grafiği yeniden yazma (en yoğun çalışma zamanı) ve bu nedenle, grafiği yeniden yazma araçları.

Sorun aynı zamanda ilgi çekici yapay zeka, bir dizinin parçası olarak kabul edilir desen eşleştirme grafik problemlerinde; olarak bilinen alt grafik izomorfizminin bir uzantısı grafik madenciliği o alanla da ilgileniyor.[10]

Ayrıca bakınız

Notlar

  1. ^ Orijinal Aşçı (1971) kanıtlayan kağıt Cook-Levin teoremi alt grafik izomorfizminin NP-tamamlandığını gösterdi, 3-SAT klikler içeren.
  2. ^ a b Eppstein (1999); Nešetřil ve Ossona de Mendez (2012)
  3. ^ Wegener, Ingo (2005), Karmaşıklık Teorisi: Etkili Algoritmaların Sınırlarını Keşfetmek, Springer, s. 81, ISBN  9783540210450.
  4. ^ de la Higuera, Colin; Janodet, Jean-Christophe; Samuel, Émilie; Damiand, Guillaume; Solnon Christine (2013), "Açık düzlem grafik ve alt grafik izomorfizmleri için polinom algoritmaları" (PDF), Teorik Bilgisayar Bilimleri, 498: 76–99, doi:10.1016 / j.tcs.2013.05.026, BAY  3083515, 70'lerin ortalarından beri, izomorfizm probleminin düzlem grafikler için polinom zamanında çözülebilir olduğu bilinmektedir. Bununla birlikte, aynı zamanda, subizomorfizm probleminin, özellikle Hamilton döngüsü probleminin düzlemsel grafikler için NP-tamamlanmış olması nedeniyle hala NP-tam olduğu da kaydedilmiştir.
  5. ^ Burada Ω çağrılar Büyük Omega gösterimi.
  6. ^ Ullmann (1976)
  7. ^ Kuramochi ve Karypis (2001).
  8. ^ Pržulj, Corneil ve Jurisica (2006).
  9. ^ Snijders vd. (2006).
  10. ^ http://www.aaai.org/Papers/Symposia/Fall/2006/FS-06-02/FS06-02-007.pdf; genişletilmiş sürüm https://e-reports-ext.llnl.gov/pdf/332302.pdf

Referanslar