Haven (grafik teorisi) - Haven (graph theory)

İçinde grafik teorisi, bir cennet kümelerdeki belirli bir işlev türüdür köşeler içinde yönsüz grafik. Bir sığınak varsa, bir kaçakçı tarafından bir kazanmak için kullanılabilir. peşinde koşma Oyunun her adımında işleve bakarak taşınacak güvenli bir köşe kümesi belirlemek için grafikte oyun. Limanlar ilk olarak Seymour ve Thomas (1993) bir araç olarak ağaç genişliği grafiklerin.^[1] Diğer uygulamaları arasında küçük ayırıcılar açık küçük kapalı grafik aileleri,^[2] ve karakterize etmek biter ve klik küçükler nın-nin sonsuz grafikler.^[3][4]

Tanım

Eğer G yönsüz bir grafiktir ve X bir köşe noktası kümesidir, sonra bir X-flap boş değildir bağlı bileşen alt grafiğinin G silerek oluşturuldu X. Bir cennet düzenin k içinde G bir işlev β atayan X-kapak β(X) her sete X daha az k köşeler. Bu işlev, farklı yazarlar tarafından farklı şekilde verilen ek kısıtlamaları da karşılamalıdır. k denir sipariş cennetin.^[5]

Seymour ve Thomas'ın orijinal tanımında,^[1] Her iki kanatta bir özelliği tatmin etmek için bir sığınak gereklidir. β(X) ve β(Y) birbirine dokunmalıdır: ya ortak bir tepe noktasını paylaşırlar ya da her kanatta bir uç noktası olan bir kenar vardır. Daha sonra Alon, Seymour ve Thomas tarafından kullanılan tanımda,^[2] sığınaklar daha zayıf olanı tatmin etmek için gereklidir monotonluk özellik: eğer X ⊆ Y, ve ikisi X ve Y daha az var k köşeler, sonra β(Y) ⊆ β(X). Dokunma özelliği, monotonluk özelliğini ifade eder, ancak bunun tam tersi geçerli değildir. Ancak, Seymour ve Thomas'ın sonuçlarından kaynaklanmaktadır.^[1] sonlu grafiklerde, monotonluk özelliğine sahip bir sığınak varsa, o zaman aynı sıraya ve dokunma özelliğine sahip olan da vardır.

Dördüncü dereceden bir yığın. Her sette bu bramble haritalarından türetilmiş bir sığınak X benzersiz bağlantılı bileşeninin üç veya daha az köşesi G  X bu, bramble'dan en az bir alt grafik içerir.

Dokunma tanımına sahip limanlar ile yakından ilgilidir Brambles, belirli bir grafiğin birbirine değen bağlı alt grafik aileleri. Bir engebeliğin sırası, ailedeki tüm alt grafiklere çarpan bir köşe kümesinde ihtiyaç duyulan minimum köşe sayısıdır. Kanat seti β(X) bir düzen cenneti için k (dokunma tanımıyla) en azından bir düzen dalgası oluşturur kçünkü herhangi bir set Y daha az k köşeler alt grafiğe ulaşamıyor β(Y). Tersine, herhangi bir düzenden k, tanımlanarak aynı düzende bir sığınak inşa edilebilir β(X) (her seçim için X) olmak X-bramble'daki tüm alt grafikleri içeren flapX. Çamurdaki alt grafiklerin hepsinin birbirine değmesi gerekliliği, bunu göstermek için kullanılabilir. X-flap var ve tüm flaplar β(X) bu şekilde seçilen birbirine dokunun. Böylece, bir grafikte bir düzen dalgası vardır k eğer ve sadece bir düzen cenneti varsak.

Misal

Örnek olarak G dokuz köşe olmak ızgara grafiği. 4. düzen cenneti tanımlayın G, her seti eşleme X üç veya daha az köşeden bir X-kapak β(X), aşağıdaki gibi:

• Eşsiz varsa Xdiğerlerinden daha büyük olan kanat X-flaps, bırak β(X) bu kadar eşsiz büyük X-kapak.
• Aksi takdirde seçin β(X) keyfi olarak herhangi biri olmak X-kapak.

Bir ile doğrulamak kolaydır vaka Analizi bu işlev β bir sığınağın gerekli monotonluk özelliğini karşılar. Eğer X ⊆ Y ve X ikiden az köşesi var veya X ızgaranın köşe tepe noktasının iki komşusu olmayan iki köşesi vardır, o zaman yalnızca bir X-flap ve her şeyi içerir Y-kapak. Kalan durumda, X bir köşe tepe noktasının iki komşusundan oluşur ve iki X-flaplar: biri o köşe tepe noktasından oluşur ve diğeri ( β(X)) kalan altı köşeden oluşur. Hangi köşeye eklendiğinin önemi yok X oluşturmak üzere Yorada olacak Yen az dört köşeli kanatçık, içinde olmayan köşelerin yarısından fazlasını içerdiğinden, benzersiz en büyük kanatçık olmalıdır. Y. Bu büyük Y-flap şu şekilde seçilecektir β(Y) ve bir alt kümesi olacak β(X). Böylece her durumda monotonluk geçerlidir.

Takip-kaçınma

Havens, bir kaçak için belirli bir strateji sınıfını modeller. peşinde koşma daha az olan oyun k takipçiler tek bir kaçışçıyı yakalamaya çalışır, takipçiler ve kaçanlar belirli bir yönsüz grafiğin köşeleriyle sınırlıdır ve takipçilerin ve kaçanın konumları her iki oyuncu tarafından da bilinir. Oyunun her hamlesinde, grafiğin keyfi bir tepe noktasına yeni bir takipçi eklenebilir ( k takipçiler herhangi bir zamanda grafiğe yerleştirilir) veya önceden eklenmiş takipçilerden biri grafikten çıkarılabilir. Bununla birlikte, yeni bir takipçi eklenmeden önce, kaçakçı ilk olarak yeni konumu hakkında bilgilendirilir ve grafiğin kenarları boyunca herhangi bir boş köşeye hareket edebilir. Kaçış, hareket ederken, takipçilerden herhangi birinin zaten işgal ettiği herhangi bir tepe noktasından geçemez.

Eğer bir k-haven (monotonluk özelliği ile) mevcutsa, o zaman kaçakçı süresiz olarak yakalanmaktan kaçınabilir ve her zaman bir tepe noktasına geçerek oyunu kazanabilir. β(X) nerede X hareketin sonunda takipçiler tarafından işgal edilecek köşe kümesidir. Bir cennetin monotonluk özelliği, grafiğin bir tepe noktasına yeni bir takipçi eklendiğinde, β(X) her zaman evader'ın mevcut konumundan ulaşılabilir.^[1]

Örneğin, bir kaçak bu oyunu üç takipçiye karşı bir 3 × 3 Örnekte açıklanan 4. sıra cenneti ile bu stratejiyi takip ederek. Bununla birlikte, aynı grafikte, dört takipçi, önce ızgarayı iki üç tepe yoluna bölen üç tepe noktasına hareket ederek, ardından kaçışçıyı içeren yolun ortasına hareket ederek, kaçağı her zaman yakalayabilir. köşe köşeleri ve nihayet bu köşeye bitişik olmayan takipçilerden birini kaldırıp kaçak üzerine yerleştiriyor. bu yüzden 3 × 3 grid 5 düzen cennetine sahip olamaz.

Dokunma özelliğine sahip limanlar, kaçakçının oyunu, bir dizi işgal edilmiş köşeden diğerine aynı anda atlayabilen daha güçlü takipçilere karşı kazanmasına izin verir.^[1]

Ağaç genişliği, ayırıcılar ve küçüklere bağlantılar

Limanlar, ağaç genişliği Grafikler: bir grafiğin bir düzen cenneti vardır k ancak ve ancak en azından ağaç genişliğine sahipse k − 1. Aynı takip-kaçırma oyununda takipçiler için kazanma stratejisini tanımlamak için bir ağaç ayrıştırması kullanılabilir, bu nedenle bir grafiğin bir düzen cenneti olduğu da doğrudur. k ancak ve ancak kaçan oyuncu en iyi oyunla kazanırsa k takipçiler. Kaçakçı tarafından kazanılan oyunlarda, bir sığınak tarafından tanımlanan biçimde her zaman optimal bir strateji vardır ve takipçinin kazandığı oyunlarda, bir ağaç ayrıştırmasıyla tanımlanan biçimde her zaman en uygun strateji vardır.^[1] Örneğin, çünkü 3 × 3 grid 4. mertebeden bir cennete sahiptir, ancak 5. mertebeden bir cenneti yoktur, tam olarak 3 ağaç genişliğine sahip olmalıdır. Aynı min-maks teoremi için genelleştirilebilir sonsuz grafikler altta yatan ağacın ışınsız olması gereken (yani, hiçbir biter ).^[1]

Limanlar da yakın akrabadır. ayırıcılar, küçük setler X içindeki köşelerin n-vertex grafiği öyle ki her X-flapta en fazla 2n/ 3 köşe. Bir grafik G yok k-vertex ayırıcı, sonra her set X en fazla k vertices bir (benzersiz) X2'den fazla kanatlın/ 3 köşe. Bu durumda, G düzen cenneti var k + 1içinde β(X) bu benzersiz büyüklük olarak tanımlanır X-kapak. Yani, her grafiğin küçük bir ayırıcısı veya yüksek bir düzen sığınağı vardır.^[2]

Bir grafik G düzen cenneti var k, ile k ≥ h^3/2n^1/2 bir tam sayı için h, sonra G ayrıca sahip olmalı tam grafik K_h olarak minör. Başka bir deyişle, Hadwiger numarası bir ndüzen cenneti ile -vertex grafiği k en azından k^2/3n^−1/3. Sonuç olarak, K_h-minor-free grafiklerin ağaç genişliği daha azdır h^3/2n^1/2 ve daha küçük boyutta ayırıcılar h^3/2n^1/2. Daha genel olarak bir O (√n) ağaç genişliğine bağlı ve ayırıcı boyutu, aşağıdakilerle karakterize edilebilecek önemsiz olmayan grafik ailesi için geçerlidir. yasak küçükler çünkü böyle bir aile için sabit bir h aile içermeyecek şekilde K_h.^[2]

Sonsuz grafiklerde

Bir grafik G bir ışın, başlangıç ​​noktası olan ancak bitiş noktası olmayan yarı sonsuz basit bir yol içerir, o zaman bir düzen cenneti vardır ℵ₀: yani bir işlev β her sonlu kümeyi eşleyen X köşelerin bir X-flap, sığınaklar için tutarlılık koşulunu sağlar. Yani tanımla β(X) benzersiz olmak X-işının sonsuz sayıda köşesini içeren flap. Böylece, sonsuz grafikler söz konusu olduğunda, ağaç genişliği ile cennetler arasındaki bağlantı kopar: Tek bir ışın, kendisi bir ağaç olmasına rağmen, tüm sonlu düzenlere ve daha da güçlü bir şekilde bir düzen cennetine sahiptir ℵ₀. Sonsuz bir grafiğin iki ışını, sonlu bir köşe kümesi yoksa eşdeğer kabul edilir. ayırır diğer ışının sonsuz sayıda köşesinden gelen bir ışının sonsuz sayıda köşesi; bu bir denklik ilişkisi, ve Onun denklik sınıfları arandı biter grafiğin.

Herhangi bir grafiğin uçları, düzen sığınakları ile bire bir yazışmalar halindedir ℵ₀. Çünkü her ışın bir sığınağı, her iki eşdeğer ışın da aynı cenneti belirler.^[3] Tersine, aşağıdaki vaka analizinde de görülebileceği gibi, her sığınak bu şekilde bir ışın tarafından belirlenir:

• Cennet, kesişme noktasının ${displaystyle S = igcap _ {X} kaldı (eta (X) fincan Xight)}$ (kesişimin tüm sonlu kümeler boyunca değiştiği X) kendisi sonsuz bir kümedir S, sonra bir tepe noktasıyla biten her sonlu basit yol S ek bir tepe noktasına ulaşmak için genişletilebilir Sve bu uzatma işleminin tekrarlanması, sonsuz sayıda köşeden geçen bir ışın üretir. S. Bu ışın, verilen cenneti belirler.
• Öte yandan, eğer S sonludur, o zaman (alt grafikte çalışarak G  S) boş olduğu varsayılabilir. Bu durumda, her sonlu küme için X_ben köşe noktalarının sonlu bir küme vardır X_ben + 1 özelliği ile X_ben ayrık ${displaystyle X_ {i + 1} fincan etası (X_ {i + 1})}$. Bir soyguncu, sığınak tarafından belirlenen kaçınma stratejisini takip ederse ve polis bu dizi dizisiyle verilen bir strateji izlerse, o zaman soyguncu tarafından izlenen yol, sığınağı belirleyen bir ışın oluşturur.^[4]

Bu nedenle, her eşdeğer ışın sınıfı benzersiz bir sığınağı tanımlar ve her sığınak, ışınların eşdeğerlik sınıfı ile tanımlanır.

Herhangi asıl sayı ${displaystyle kappa geq aleph _ {1}}$sonsuz bir grafik G bir düzen cenneti vardır ancak ve ancak bir klik minör siparişin κ. Yani, sayılamayan kardinaliteler için, bir cennetin en büyük düzeni G ... Hadwiger numarası nın-nin G.^[3]

Referanslar