Robertson-Seymour teoremi - Robertson–Seymour theorem

Olarak grafik teorisi , Robertson-Seymour teoremi (ayrıca grafik minör teoremi ) bildiren yönsüz grafikleri , kısmi sıralı tarafından grafik küçük bir ilişki, bir formu iyi yarı-sırası . Eşdeğer, çocuklar altında kapalı olan grafikler her aile sonlu bir dizi tanımlanabilir yasak küçükler , aynı şekilde, Wagner teoremi karakterize düzlemsel grafik yok grafikleri olarak tam grafik K 5 ya da tam ikili grafik K 3,3 küçükler olarak.

Robertson-Seymour teoremi matematikçiler adını taşımaktadır Neil Robertson ve Paul D. Seymour onun kanıtı önce 1983'ten 2004'e kadar üzerinde 500 sayfaları kapsayan yirmi kağıtları bir dizi de gösterdik, teoremin ifadesi olarak biliniyordu Wagner'in varsayım sonra Alman matematikçi Klaus Wagner , Wagner bunu asla tahmin etmediğini söylese de.

Ağaçlar için daha zayıf bir sonuç , 1937'de Andrew Vázsonyi tarafından tahmin edilen ve 1960'da Joseph Kruskal ve S. Tarkowski tarafından bağımsız olarak kanıtlanan Kruskal'ın ağaç teoremi tarafından ima edilir .

Beyan

Bir küçük bir bir yönsüz grafik G elde edilebilir herhangi bir grafiktir G kenarlarından sıfır ya da daha fazla kasılma bir dizisi ile G ve kenarlar ve köşeler silme G . Küçük ilişki oluşturur kısmi düzeni kısmi siparişlerin üç belitleri uymak kaydıyla, tüm farklı sonlu yönsüz grafikler setinde: o dönüşlü , (her grafik bir kendini küçük) geçişli (bir minör küçük bir G olduğu kendisi G 'nin minörü ) ve antisimetrik (eğer iki grafik G ve H birbirinin minör ise, o zaman bunlar izomorfik olmalıdır ). Bununla birlikte, izomorfik olan grafikler yine de ayrı nesneler olarak kabul edilebilirse, o zaman grafiklerdeki küçük sıralama bir ön sıralama oluşturur , dönüşlü ve geçişli ancak antisimetrik olması zorunlu olmayan bir ilişki.

Bir ön siparişin , ne sonsuz bir azalan zincir ne de sonsuz bir zincir karşıtı içermiyorsa , iyi bir yarı sipariş oluşturduğu söylenir . Örneğin, negatif olmayan tamsayılar üzerindeki olağan sıralama iyi bir sıralamadır, ancak tüm tamsayılar kümesindeki aynı sıralama, 0, -1, -2, -3 sonsuz azalan zinciri içerdiğinden değildir. ...

Robertson-Seymour teoremi, sonlu yönsüz çizgelerin ve küçük çizgelerin iyi bir yarı-sıralama oluşturduğunu belirtir. Grafiğin küçük ilişkisi, herhangi bir sonsuz azalan zincir içermez, çünkü her daralma veya silme, grafiğin kenar ve köşelerinin sayısını azaltır (negatif olmayan bir tam sayı). Teoremin önemsiz kısmı, sonsuz zincir karşıtı, küçük sıralama ile birbiriyle ilişkisiz sonsuz grafik kümeleri olmamasıdır. Eğer S grafikler bir dizi ve M bir alt kümesidir S her denklik sınıfı için temsili bir grafik olan en az elemanları (aittir grafikleri S fakat herhangi bir uygun küçük ait için S ), daha sonra E bir antichain oluşturur; bu nedenle, teoremi ifade etmenin eşdeğer bir yolu, herhangi bir sonsuz S grafik kümesinde , yalnızca sonlu sayıda izomorfik olmayan minimal öğenin olması gerektiğidir.

Teoremin bir başka eşdeğer biçimi, herhangi bir sonsuz S grafik kümesinde , biri diğerinin küçük olan bir çift grafiğin olması gerektiğidir. Her sonsuz kümenin sonlu sayıda minimal öğeye sahip olduğu ifadesi, teoremin bu biçimini ima eder, çünkü yalnızca sonlu sayıda minimal öğe varsa, kalan grafiklerin her biri minimum öğelerden biriyle bu türden bir çifte ait olmalıdır. Ve diğer yönde, teoremin bu biçimi, sonsuz bir zincirleme zincir olmadığı için sonsuz bir zincir zincirinin küçük ilişki ile ilişkili herhangi bir çift içermeyen bir küme olduğu ifadesine işaret eder.

Yasak küçük karakterizasyonlar

Bir aile F grafiklerinin olduğu söylenen kapalı bir grafik her bir küçük ise küçükleri alma işlemi altında F de aittir F . Eğer F küçük kapalı bir ailedir, daha sonra izin S olmayan grafikler kümesi F ( tamamlayıcı ait F ). Robertson-Seymour teoremine göre, S'de minimal elemanlardan oluşan sonlu bir H kümesi vardır . Bu en az elemanlar meydana yasak grafik karakterizasyonu arasında F grafikler: F herhangi bir grafik yok tam grafiklerdir H Küçük bir çocuk gibi. H üyeleri, F ailesi için hariç tutulan küçükler (veya yasak küçükler veya küçük-minimal engeller ) olarak adlandırılır .

Örneğin, düzlemsel grafikler minörler alarak kapalıdır: düzlemsel bir grafikte bir kenarı daraltmak veya grafikten kenarları veya köşeleri kaldırmak, düzlemselliğini bozamaz. Bu nedenle, düzlemsel grafikler, bu durumda Wagner teoremi tarafından verilen yasaklanmış bir minör karakterizasyonuna sahiptir : küçük-minimal düzlemsel olmayan grafiklerin H kümesi tam olarak iki grafik içerir, tam grafik K 5 ve tam iki parçalı grafik K 3,3 , ve düzlemsel grafikler tam olarak { K 5 ,  K 3,3 } kümesinde minörü olmayan grafiklerdir .

Tüm minör-kapalı çizge aileleri için yasaklanmış minör karakterizasyonların varlığı, Robertson-Seymour teoremini ifade etmenin eşdeğer bir yoludur. Çünkü, her küçük-kapalı F ailesinin sonlu bir H kümesine sahip olduğunu varsayalım ve S'nin herhangi bir sonsuz grafik kümesi olmasına izin verin . Define F den S içinde bir çocuğu yok grafikler aile olarak S . O zaman F minör-kapalı ve sonlu bir H minimal yasaklanmış minör kümesine sahiptir . F'nin tümleyeni C olsun . S ve F ayrık olduğundan ve H , C'deki minimum grafikler olduğundan S , C'nin bir alt kümesidir . Bir grafiktir düşünün G olarak H . G, uygun bir ufak olamaz S yana G minimaldir C . Aynı zamanda, G'nin S'de bir minör olması gerekir , çünkü aksi takdirde G , F'de bir eleman olurdu . Bu nedenle, G, bir elementtir S , yani H bir alt kümesidir S ve tüm diğer grafikleri S grafiklerde arasında minör sahip H , yani H minimal elemanlarının sonlu dizi S .

Diğer çıkarım için, her grafik kümesinin sonlu bir minimal grafik alt kümesine sahip olduğunu varsayalım ve küçük-kapalı bir küme F verilsin. Bir grafik F'de olacak şekilde bir H grafik kümesi bulmak istiyoruz, ancak ve ancak H'de minör yoksa . F'deki herhangi bir grafiğin minör olmayan grafikleri E olsun ve H , E'deki minimum grafiklerin sonlu kümesi olsun . Şimdi, keyfi bir G grafiği verilsin. İlk varsayalım G olduğu F . G, bir yan dal olamaz H yana G olduğu F ve H bir alt kümesi E . Şimdi G'nin F'de olmadığını varsayalım . O zaman G , F'deki herhangi bir grafiğin minör değildir , çünkü F minör-kapalıdır. Bu nedenle G , E'dedir , dolayısıyla G'nin H'de bir minörü vardır .

Küçük-kapalı aile örnekleri

Ana madde: Yasak grafik karakterizasyonu

Aşağıdaki sonlu grafik kümeleri minör-kapalıdır ve bu nedenle (Robertson-Seymour teoremi tarafından) minör karakterizasyonları yasaklamıştır:

Engel setleri

Petersen ailesi , linkless katıştırma için engel seti.

Robertson-Seymour teoremi kanıtlanmadan önce, belirli grafik sınıfları için sonlu engel kümelerinin bazı örnekleri zaten biliniyordu. Örneğin, tüm ormanlar kümesinin önündeki engel, döngü grafiğidir (veya basit grafiklerle sınırlandırılırsa , üç köşeli döngü). Bu, bir grafiğin, ancak ve ancak minörlerinden hiçbiri döngü (veya sırasıyla üç köşeli döngü) değilse bir orman olduğu anlamına gelir. Yol kümesi için tek engel, biri derece 3 olan dört köşeli ağaçtır. Bu durumlarda, engel kümesi tek bir öğe içerir, ancak genel olarak durum böyle değildir. Wagner teoremi , bir grafiğin yalnızca ve yalnızca ne K 5 ne de K 3,3'ün minör olarak olmaması durumunda düzlemsel olduğunu belirtir . Başka bir deyişle, { K 5 ,  K 3,3 } kümesi, tüm düzlemsel grafikler kümesi için bir engel kümesidir ve aslında benzersiz minimum engel kümesidir. Benzer bir teoremi bildiren K 4 ve K 2,3 outerplanar grafikler grubu yasaktır çocuk yaştadır.

Robertson-Seymour teoremi bu sonuçları keyfi küçük-kapalı grafik ailelerine genişletse de, bu sonuçların tam bir ikamesi değildir, çünkü herhangi bir aile için engel kümesinin açık bir tanımını sağlamaz. Örneğin, bize toroidal grafikler kümesinin sonlu bir engel kümesine sahip olduğunu söyler , ancak böyle bir küme sağlamaz. Toroidal grafikler için yasaklanmış küçüklerin tam seti bilinmiyor, ancak en az 17.535 grafik içeriyor.

Polinom zaman tanıma

Robertson-Seymour teoremi, Robertson ve Seymour'un, her sabit grafik G için , daha büyük grafiklerin küçük olarak G'ye sahip olup olmadığını test etmek için bir polinom zaman algoritması olduğunu kanıtlamasına bağlı olarak, hesaplama karmaşıklığında önemli bir sonuca sahiptir . Bu algoritmanın çalışma süresi , daha büyük grafiğin boyutunda bir kübik polinom olarak ifade edilebilir (bu polinomda süperpolinom olarak G 'nin boyutuna bağlı sabit bir faktör olmasına rağmen ), Kawarabayashi tarafından ikinci dereceden zamana iyileştirilmiştir, Kobayashi ve Reed. Sonuç olarak, her küçük-kapalı aile F için , bir grafiğin F'ye ait olup olmadığını test etmek için bir polinom zaman algoritması vardır : basitçe, F için yasaklanmış minörlerin her biri için , verilen grafiğin bu yasaklanmış minörü içerip içermediğini kontrol edin.

Bununla birlikte, bu yöntemin çalışması için belirli bir sonlu engel kümesi gerekir ve teorem bir tane sağlamaz. Teorem, böyle bir sonlu engel kümesinin var olduğunu kanıtlar ve bu nedenle yukarıdaki algoritma nedeniyle problem polinomdur. Ancak, algoritma pratikte ancak böyle bir sonlu engel kümesi sağlanırsa kullanılabilir. Sonuç olarak, teorem, problemin polinom zamanında çözülebileceğini kanıtlar, ancak bunu çözmek için somut bir polinom-zaman algoritması sağlamaz. Bu tür polinomsallık kanıtları yapıcı değildir : açık bir polinom-zaman algoritması sağlamadan problemlerin polinomluğunu kanıtlarlar. Birçok özel durumda, bir grafiğin belirli bir küçük-kapalı ailede olup olmadığını kontrol etmek daha verimli bir şekilde yapılabilir: örneğin, bir grafiğin düzlemsel olup olmadığını kontrol etmek doğrusal zamanda yapılabilir.

Sabit parametreli izlenebilirlik

İçin grafik değişmezler her biri için, özellik ile k , en fazla değişmez olan grafikler k küçük kapalı olan, aynı yöntem uygulanır. Örneğin, bu sonuca göre, ağaç genişliği, dal genişliği ve yol genişliği, tepe örtüsü ve bir yerleştirmenin minimum cinsinin tümü bu yaklaşıma uygundur ve herhangi bir sabit k için bu değişmezlerin en fazla olup olmadığını test etmek için bir polinom zaman algoritması vardır. k , burada algoritmanın çalışma süresindeki üs k'ye bağlı değildir . Herhangi bir sabit, polinom zamanda çözülebileceğini bu özelliği ile ilgili bir problem, k bağlı değildir bir üst ile k olarak bilinen sabit parametreli izlenebilir .

Ancak, bu yöntem, k bilinmeyenli belirli bir grafiğin parametre değerini hesaplamak için doğrudan tek bir sabit parametreli izlenebilir algoritma sağlamaz , çünkü yasaklı küçükler kümesini belirlemenin zorluğundan dolayı. Ek olarak, bu sonuçlarda yer alan büyük sabit faktörler, onları oldukça pratik hale getirir. Bu nedenle, bu problemler için k'ye daha fazla bağımlı olan açık sabit parametreli algoritmaların geliştirilmesi , önemli bir araştırma konusu olmaya devam etmiştir.

Graf minör teoreminin sonlu formu

Friedman, Robertson ve Seymour (1987) kuram sergilediğini göstermiştir bağımsız olarak olgusunu kanıtlanamayan daha güçlü olan çeşitli resmi sistemlerde Peano aritmetik , henüz edilebilir kanıtlanabilir çok daha zayıf sistemlerde ZFC :

Teorem : Her n pozitif tamsayı için , o kadar büyük bir m tamsayısı vardır ki, G 1 , ..., G m bir sonlu yönsüz grafikler dizisiyse,
Her burada G, I en boyutuna sahiptir , n + ı , o G j ≤ G k bazı j < k .

(Burada bir grafiğin boyutu , köşelerinin ve kenarlarının toplam sayısıdır ve ≤ küçük sıralamayı belirtir.)

Ayrıca bakınız

Notlar

Referanslar

  • Bienstock, Daniel; Langston, Michael A. (1995), "Grafik minör teoreminin algoritmik çıkarımları", Ağ Modelleri (PDF) , Yöneylem Araştırması ve Yönetim Biliminde El Kitapları, 7 , s. 481–502, doi : 10.1016/S0927-0507(05 )80125-2.
  • Diestel, Reinhard (2005), "Küçükler, Ağaçlar ve WQO", Grafik Teorisi (PDF) (Electronic Edition 2005 ed.), Springer, s. 326–367.
  • Arkadaşlar, Michael R. ; Langston, Michael A. (1988), "Polinom zamanlı karar verilebilirliği kanıtlamak için yapısal olmayan araçlar", Journal of the ACM , 35 (3): 727–739, doi : 10.1145/44483.44491.
  • Friedman, Harvey ; Robertson, Neil ; Seymour, Paul (1987), "Grafik minör teoreminin metamathematics", Simpson, S. (ed.), Logic and Combinatorics , Contemporary Mathematics, 65 , American Mathematical Society , s. 229–261.
  • Kawarabayashi, Ken-ichi ; Kobayashi, Yusuke; Reed, Bruce (2012), "İkinci dereceden zamanda ayrık yollar sorunu" (PDF) , Kombinatoryal Teori Dergisi, B Serisi , 102 (2): 424–435, doi : 10.1016/j.jctb.2011.07.004.
  • Lovász, László (2005), "Graph Minor Theory", Bülten of the American Mathematical Society , Yeni Seri, 43 (1): 75–86, doi : 10.1090/S0273-0979-05-01088-8.
  • Myrvold, Wendy ; Woodcock, Jennifer (2018), "Büyük Bir Torus Obstrüksiyonu Seti ve Nasıl Keşfedildiler" , The Electronic Journal of Combinatorics , 25 (1) : P1.16 , doi : 10.37236/3797.
  • Robertson, Neil ; Seymour, Paul (1983), "Graph Minors. I. Bir orman hariç", Journal of Kombinatory Theory, Series B , 35 (1): 39–61, doi : 10.1016/0095-8956(83)90079-5.
  • Robertson, Neil ; Seymour, Paul (1995), "Graph Minors. XIII. The disjoint paths problemi", Journal of Combinatory Theory, Series B , 63 (1): 65–110, doi : 10.1006/jctb.1995.1006.
  • Robertson, Neil ; Seymour, Paul (2004), "Graph Minors. XX. Wagner'in varsayımı", Journal of Combinatory Theory, Series B , 92 (2): 325–357, doi : 10.1016/j.jctb.2004.08.001.

Dış bağlantılar