Sığ küçük - Shallow minor

Olarak grafik teorisi , bir sığ küçük ya da sınırlı derinliği az bir kısıtlanmış bir şeklidir grafik minör minör oluşturmak üzere sözleşmelidirler subgraphs küçük sahip olduğu bir çapa . Sığ küçükler, buluşlarını Charles E. Leiserson ve Sivan Toledo'ya bağlayan Plotkin, Rao & Smith (1994) tarafından tanıtıldı .

Tanım

1 sığ minör olarak K 4 tam grafiğine sahip bir grafik . Kesikli dikdörtgenlerle gösterilen dört köşe alt kümesinin her biri, yarıçapı bir olan bağlantılı bir alt grafiği indükler ve her alt küme çifti arasında bir kenar vardır.

Bir yönsüz grafiği bir minör tanımlamanın bir yolu, G, bir alt grafiğinin belirterek olan , H ve G , ve ayrık alt-koleksiyonu S i köşeler G bir oluşturan, her biri, bağlı neden subgraph H ı arasında H . Küçük bir tepe vardır v ı Her bir alt-grup için S i , ve bir kenar v ı v j bir kenarı vardır her S i için S j ait H .

Bu formülasyonda, bir d -shallow minör (alternatif olarak derinlik sığ bir minör adı d Alt Graflar her birinin bir şekilde tanımlanabilir bir küçük) H i vardır çapındaki en d merkezi bir tepe noktasını içerir, yani c ı bu mesafe içinde d diğer tüm köşe H i . Bu mesafe de atlama sayısına göre ölçüldüğü Not H I ve çünkü mesafenin fazla büyük olabilir ve G .

Özel durumlar

Derinliği sıfır olan sığ küçükler, verilen grafiğin alt grafikleri ile aynı şeydir. Yeterince büyük d değerleri için (en az köşe sayısı kadar büyük tüm değerler dahil), belirli bir grafiğin d -sığ minörleri, tüm minörleriyle çakışır.

Grafik ailelerinin sınıflandırılması

Nešetřil ve Ossona de Mendez (2012) sonlu grafik ailelerini iki türe ayırmak için sığ minörler kullanır. Bunlar bir grafiktir aile olduğunu söylemek F olduğu yerde yoğun bir sonlu değer mevcutsa d olan D olarak grafikler -shallow küçükler F her sonlu grafik oluşur. Aksi takdirde, bir grafik ailesinin hiçbir yerde yoğun olmadığını söylüyorlar . Bu terminoloji, bu gerçeği ile haklı F (her £ değerinin> 0 için) daha sonra grafikler bir yerde yoğun sınıf, n, içinde -vertex grafikleri F sahip O ( n, 1 + ε ) kenarları; bu nedenle, yoğun olmayan grafikler seyrek grafiklerdir .

Benzer şekilde tanımlanan daha kısıtlayıcı bir grafik ailesi türü, sınırlı genişlemenin grafik aileleridir . Bunlar, bir fonksiyonu vardır olan grafik aileleri f her köşe kenarlarından oranı şekilde gün içindeki -shallow minör en olduğunu f ( d ). Bu fonksiyon varsa ve bir polinomla sınırlandırılmışsa , grafik ailesinin polinom genişlemesine sahip olduğu söylenir.

ayırıcı teoremler

Olarak Plotkin, Rao ve (1994) Smith gösterdi hariç sığ küçükler ile grafikleri benzer şekilde bölümlenmiş olabilir düzlemsel ayırma teoremi için düzlemsel grafikler . Tam Grafik Özellikle, K , H , bir değil, D , bir ait -shallow minör N -vertex grafik G , daha sonra, bir alt-kümesi vardır S ve G boyutu, O ( dh 2 log n + n / d ), örneğin her birinin G \ S'nin bağlı bileşeni en fazla 2 n /3 köşeye sahiptir. Sonuç yapıcıdır: ya böyle bir ayırıcı ya da bir d -sığ K h minör bulan bir polinom zaman algoritması vardır . Sonuç olarak, her küçük-kapalı grafik ailesinin, neredeyse düzlemsel grafikler için olan kadar güçlü bir ayırıcı teoreme uyduğunu gösterdiler.

Plotkin ve ark. bu sonucu sonlu elemanlar yöntemi ağlarının daha yüksek boyutlarda bölümlenmesine de uyguladı ; Bu genelleme için sığ minörler gereklidir, çünkü (derinlik kısıtlaması olmadan) üç veya daha fazla boyuttaki ağ ailesi tüm grafiklere minör olarak sahiptir. Teng (1998) , bu sonuçları daha geniş bir yüksek boyutlu grafikler sınıfına genişletir.

Daha genel olarak, bir kalıtsal grafik ailesi, ayırıcı boyutunun n'nin bir alt doğrusal kuvveti olduğu bir ayırıcı teoremine sahiptir, ancak ve ancak polinom genişlemesine sahipse.

Notlar

Referanslar

  • Dvořák, Zdeněk ; Norin, Sergey (2015), Kuvvetli sublineer ayırıcılar ve polinom açılımı , arXiv : 1504.04821 , Bibcode : 2015arXiv150404821D.
  • Plotkin, Serge; Rao, Satiş; Smith, Warren D. (1994), "Sığ dışlanmış küçükler ve geliştirilmiş grafik ayrıştırmaları", Proc. 5. ACM-SIAM Semptom. Ayrık Algoritmalar (SODA) üzerine , s. 462–470.
  • Teng, Shang-Hua (1998), "Geometrik grafiklerin kombinatoryal yönleri", Comput. Geom. , 9 (4): 277–287, doi : 10.1016/S0925-7721(96)00008-9 , MR  1609578.
  • Wulff-Nilsen, Christian (2011), "Minör-Serbest ve Sığ Minör-Serbest Grafikler için Ayırıcı Teoremler", Proc. 52. IEEE Semptom. Bilgisayar Biliminin Temelleri (FOCS) , s. 37–46, arXiv : 1107.1292 , doi : 10.1109/FOCS.2011.15.
  • Neşetil, Jaroslav ; Ossona de Mendez, Patrice (2012), Sparsity: Graphs, Structures and Algorithms , Algorithms and Combinatorics, 28 , Springer, doi : 10.1007/978-3-642-27875-4 , ISBN 978-3-642-27874-7, MR  2920058.