indüklenmiş yol - Induced path

Bir küpte dört uzunluğunda uyarılmış bir yol . Bir hiperküpte en uzun indüklenmiş yolu bulmak, kutudaki yılan problemi olarak bilinir .

Olarak matematiksel alan grafik teorisi , bir indüklenmiş yolu bir yönsüz grafikte G, a, yol bir bir indüklenmiş alt grafiğinin bölgesinin G . Kendisine, bu köşe noktalarının bir dizisi G sırayla her iki komşu noktalar bir kenar ile bağlı olduğu, örneğin , G , ve dizideki her iki komşu olmayan noktalar herhangi bir kenarı ile bağlı olmayan G . İndüklenmiş bir yola bazen yılan denir ve hiperküp grafiklerde uzun indüklenmiş yolları bulma problemi, kutudaki yılan problemi olarak bilinir .

Benzer şekilde, indüklenmiş bir döngü , G'nin indüklenmiş bir alt grafiği olan bir döngüdür ; indüklenen döngüler ayrıca kirişsiz döngüler veya (döngünün uzunluğu dört veya daha fazla olduğunda) delikler olarak adlandırılır . Bir antihole bir delik tamamlayıcı bir G , yani, bir antihole bir delik tamamlayıcıdır.

Bir grafikte en uzun indüklenen yolun uzunluğuna bazen grafiğin dolambaçlı yolu numarası denir ; için seyrek grafikler , sınırlı dolambaçlı sayısına sahip olan sınırlı olan eşdeğerdir ağaç derinliği . Kaynaklı yol sayısının bir grafik G grafik köşeler paylaştırıldı edilebilen indüklenen yolların küçük bir sayıdır ve yakın ilişkili yolu kapağı sayısı arasında G birlikte her köşe içerir neden yolların en küçük sayıdır G . Çevresi bir grafik olan en kısa döngüsünün uzunluğu olmakla birlikte, bu döngü bir akor daha kısa bir döngü oluşturmak için kullanılabilecek haliyle, indüklenmiş bir çevrim olması gerekir; benzer nedenlerle, bir grafiğin tek çevresi aynı zamanda en kısa tek indüklenmiş döngüsünün uzunluğudur.

Misal

1'den 4'e kadar n boyutları için kutudaki yılan probleminde maksimum yılan uzunlukları ( L s ) ve bobinler ( L c )

Şekil bir küpü, sekiz köşesi ve on iki kenarı olan bir grafiği ve bu grafikte dört uzunluğunda indüklenmiş bir yolu göstermektedir. Basit bir durum analizi, altı uzunlukta bir indüklenmiş döngüye sahip olmasına rağmen, küpte artık indüklenmiş yol olamayacağını gösterir. İlk olarak Kautz (1958) tarafından ortaya konan bir hiperküpte en uzun indüklenmiş yolu veya döngüyü bulma problemi, kutudaki yılan problemi olarak bilinir ve kodlama teorisi ve mühendisliğindeki uygulamaları nedeniyle kapsamlı bir şekilde çalışılmıştır. .

Grafik ailelerinin karakterizasyonu

Birçok önemli grafik ailesi, ailedeki grafiklerin indüklenmiş yolları veya döngüleri açısından karakterize edilebilir.

  • Önemsiz olarak, uzunluk iki indüklenmiş yolu olmayan bağlantılı grafikler tam grafiklerdir ve indüklenmiş çevrimi olmayan bağlı grafikler ağaçlardır .
  • Bir üçgen içermeyen grafik uzunluğunun üç hiçbir uyarılmış döngüsü ile bir grafiktir.
  • Cographs tam uzunlukta üç hiçbir neden yol ile grafiklerdir.
  • Kiriş grafikleri uzunluğu dört veya daha fazla herhangi bir neden döngüsü ile grafiklerdir.
  • Hatta delikli içermeyen grafikler köşe eşit sayısı ile indüklenen döngüleri ihtiva eden grafiklerdir.
  • Trivially mükemmel grafikleri uzunluğunun üç uyarılmış bir yolu, ne de uzunluğu dört uyarılmış bir döngüsü ne sahip grafiklerdir.
  • Güçlü mükemmel grafik teoremi ile mükemmel grafikler , tek delik ve tek anti delik olmayan grafiklerdir.
  • Mesafesi kalıtsal grafikler her neden yol bir en kısa yol olan grafikler ve aynı iki köşe arası her iki kaynaklı yolları aynı uzunluğa sahip olduğu grafiklerdir.
  • Blok grafikleri herhangi iki köşe arasındaki en fazla bir kaynaklı yolun orada olduğu grafiklerdir, ve bağlı blok grafikleri her iki köşe arasındaki tam bir neden yol var olduğu grafiklerdir.

Algoritmalar ve karmaşıklık

Bir G grafiği ve k parametresi için, grafiğin en az k uzunluğunda bir indüklenmiş yola sahip olup olmadığını belirlemek NP-tamamlanmıştır . Garey & Johnson (1979) bu sonucu Mihalis Yannakakis'in yayınlanmamış bir iletişimine borçludur . Bununla birlikte, bu sorun, asteroit-üçlü olmayan grafikler veya uzun delikleri olmayan grafikler gibi belirli grafik aileleri için polinom zamanında çözülebilir.

Ayrıca, bir grafiğin köşelerinin iki indüklenmiş yola mı yoksa iki indüklenmiş döngüye mi bölünebileceğini belirlemek için NP-tamamlanmıştır. Sonuç olarak, bir grafiğin indüklenen yol numarasının belirlenmesi NP-zordur.

En uzun indüklenmiş yol veya döngü problemlerine yaklaşmanın karmaşıklığı , aşağıdaki indirgeme ile grafiklerde büyük bağımsız kümelerin bulunmasıyla ilgili olabilir . Herhangi bir grafikten G ile N köşeler, başka bir grafik oluşturmak H birçok köşe iki katı ile G eklenerek, G , n ( n  - 1) / iki komşu her bir köşe her bir çifti için var olan 2 köşe G . Daha sonra, eğer G boyutu bağımsız bir kümesi vardır k , H uyarılmış bir yolu ve uzunluğu 2 bir indüklenmiş döngüsü olmalıdır k bağımsız setin köşeler alternatif oluşturduğu G köşeleri ile I . Tersine, H'nin k uzunluğunda bir indüklenmiş yolu veya döngüsü varsa , bu yol veya döngüden G'deki herhangi bir maksimum bitişik olmayan köşe kümesi, G boyutunda en az k /3 bağımsız bir küme oluşturur . Bu nedenle, maksimum bağımsız kümesinin boyutu G uzun kaynaklı yolun boyutu ve en uzun neden döngüsünün sabit bir faktörü dahilindedir H . Bu nedenle, Håstad'ın (1996) bağımsız kümelerin yaklaştırılamazlığı konusundaki sonuçlarına göre , NP=ZPP olmadıkça, en uzun indüklenen yolu veya en uzun indüklenen döngüyü O( n 1/) faktörü dahilinde yaklaşık olarak tahmin etmek için bir polinom zaman algoritması yoktur 2-ε ) optimal çözüm.

Köşe ve m, kenarları n bir grafikte (uzunluk 5 chordless Döngü olmayan grafiklerde ve antiholes) delikler zaman (n + m tespit edilebilir 2 ).

atomik döngüler

Atomik çevrimler, n -akor içermeyen akorsuz çevrimlerin bir genellemesidir . Bir döngü verildiğinde, bir n- koru, döngüdeki iki noktayı birbirine bağlayan n uzunluğunda bir yol olarak tanımlanır; burada n , bu noktaları birleştiren döngüdeki en kısa yolun uzunluğundan daha küçüktür. Bir çevrimde n- koru yoksa, daha küçük çevrimlere ayrıştırılamadığı için buna atomik çevrim denir. En kötü durumda, bir grafikteki atomik döngüler O( m 2 ) zamanında numaralandırılabilir , burada m grafikteki kenar sayısıdır.

Notlar

Referanslar