Faktör açısından kritik grafik - Factor-critical graph
Olarak grafik teorisi , matematiksel bir disiplin, bir faktör kritik grafik (veya hypomatchable grafik ) a, grafik ile , n , her alt grafiğinin olan köşe n 1 - noktaların bir sahiptir mükemmel uyum . (Bir grafikte mükemmel bir eşleşme, köşelerinin her birinin alt kümedeki kenarlardan birinin tam olarak bitiş noktası olması özelliğiyle, kenarlarının bir alt kümesidir.)
Grafiğin bir köşesi hariç tümünü kapsayan eşleşmeye mükemmele yakın eşleşme denir . Aynı şekilde, faktör açısından kritik bir grafik, olası her köşeyi önleyen mükemmele yakın eşleşmelerin olduğu bir grafiktir.
Örnekler
Herhangi bir tek uzunluktaki döngü grafiği , tek sayıda köşesi olan herhangi bir tam grafik gibi, faktör açısından kritiktir . Daha genel olarak, tek sayıda köşesi olan her Hamilton grafiği faktör açısından kritiktir. Dostluğu grafikleri (tek bir ortak bir tepe noktasına üçgen bir koleksiyon bağlanması sureti ile meydana grafikler) faktör kritik ama Hamilton olmayan grafikler örneklerini temin etmektedir.
Bir G grafiği faktör açısından kritikse , G'nin Mycielskian'ı da öyledir . Örneğin, beş köşeli bir döngü grafiğinin Mycielskian'ı olan Grötzsch grafiği , faktör açısından kritiktir.
Tek sayıda köşeye sahip her 2 köşe bağlantılı pençesiz grafik faktör açısından kritiktir. Örneğin, normal ikosahedrondan bir tepe noktasının çıkarılmasıyla oluşturulan 11 köşe grafiği ( jiro-uzun beşgen piramidin grafiği ) hem 2 bağlantılı hem de pençesizdir , bu nedenle faktör açısından kritiktir. Bu sonuç, doğrudan, çift sayıda köşesi olan her bağlı pençesiz grafiğin mükemmel bir eşleşmeye sahip olduğu daha temel teoremden çıkar.
Karakterizasyonlar
Faktör açısından kritik grafikler, her bir köşe silme işleminin mükemmel bir eşleşmeye izin verdiği grafikler olarak tanımlanmaları dışında birkaç farklı yolla karakterize edilebilir:
- Tibor Gallai bu ancak ve ancak, eğer bir grafiktir faktörü kritik olduğunu kanıtlamıştır bağlı her düğüm için, ve v grafik, bir vardır , maksimum karşılaştırma içermez v . Bu özelliklerden, grafiğin tek sayıda köşeye sahip olması gerektiği ve her maksimum eşleşmenin bir köşe hariç tümü ile eşleşmesi gerektiği sonucu çıkar.
- László Lovász , bir grafiğin yalnızca ve yalnızca tek bir kulak ayrışmasına sahip olması durumunda faktör açısından kritik olduğunu kanıtladı , kenarlarının, her biri tek uzunlukta bir yol veya döngü olan bir dizi alt grafa bölünmesi ve ilki sırayla bir döngüdür, dizideki her yolun her iki bitiş noktası vardır, ancak önceki alt grafiklerde köşelerde iç noktalar yoktur ve dizideki ilk dışındaki her döngü, önceki alt grafiklerde tam olarak bir tepe noktasına sahiptir. Örneğin, çizimdeki grafik bu şekilde beş kenarlı bir döngü ve üç kenarlı bir yola bölünebilir. Faktör açısından kritik grafiğin mükemmele yakın bir eşleşmesinin de verilmesi durumunda, kulak ayrışması, her bir kulak eşleşen ve eşleşmeyen kenarlar arasında geçiş yapacak şekilde seçilebilir.
- Bir grafik, aynı zamanda, yalnızca ve yalnızca , tek uzunluktaki döngülerin bir dizi kasılmasıyla tek bir tepe noktasına indirgenebiliyorsa, faktör açısından kritiktir . Ayrıca bu karakterizasyonda dizideki her bir çevrimi bir önceki çevrimin daralmasıyla oluşan tepe noktasını içerecek şekilde seçmek mümkündür. Örneğin, bir kişi bir kulak ayrışmasının kulaklarını, ayrışma tarafından verilen sırayla kasılırsa, o zaman her kulak kasıldığında tek bir döngü oluşturur, bu nedenle kulak ayrışma karakterizasyonu, bir tek döngü dizisini bulmak için kullanılabilir. anlaşmak. Tersine, her biri önceki kasılmadan oluşturulan tepe noktasını içeren bir dizi tek döngü kasılmasından, kulakların her adımda büzülen kenar kümeleri olduğu bir kulak ayrışması oluşturulabilir.
- Bir grafiktir Varsayalım ki G, bir köşe bir seçimi ile birlikte verilir v ve eşleşen bir M dışındaki kapaklar bütün çıkıntılar v . O zaman G faktör açısından kritiktir, ancak ve ancak G içinde , v'yi G'deki diğer köşelerin her birine bağlayan, eşleşen ve eşleşmeyen kenarlar arasında değişen bir dizi yol varsa . Bu özelliğe dayanarak, belirli bir mükemmele yakın eşleşmeye sahip bir G grafiğinin faktör açısından kritik olup olmadığını doğrusal zamanda belirlemek mümkündür .
Özellikleri
Faktör açısından kritik grafikler her zaman tek sayıda köşeye sahip olmalı ve 2 kenar bağlantılı olmalıdır (yani, herhangi bir köprüleri olamaz ). Ancak, mutlaka 2-köşe bağlantılı değildirler ; dostluk grafikleri bir karşı örnek sağlar. Faktör açısından kritik bir grafiğin iki parçalı olması mümkün değildir , çünkü mükemmele yakın bir eşleşmeye sahip iki parçalı bir grafikte, mükemmel bir şekilde eşleştirilebilir bir grafik üretmek için silinebilecek tek köşeler, ikili bölümün daha büyük tarafında olanlardır.
m kenarlı her 2-köşe bağlantılı faktör kritik grafiğin en az m farklı mükemmele yakın eşleşmesi vardır ve daha genel olarak m kenarlı ve c bloklu (2 köşe bağlantılı bileşen) her faktör kritik grafiğin en az m − c + 1 farklı mükemmele yakın eşleşme. Bu sınırların sıkı olduğu grafikler, belirli bir biçimde tek kulak ayrışmalarına sahip olarak karakterize edilebilir.
Herhangi bağlı grafik bir faktör kritik grafik haline transforme edilebilir yakalanma kenarlarından yeterince fazla. En az taahhütlü gereken kenarların setleri, belirli bir grafik yapmak için G faktörü kritik formu, bir tabanları matroid bir ima bir gerçek Algoritma bir hale getirmek için sözleşme kenarların minimum ağırlık kümesini bulmak için kullanılabilmektedir grafik faktörü kritik, polinom zamanında .
Uygulamalar
Bir çiçek , daha büyük bir grafiğin faktör açısından kritik bir alt grafiğidir. Çiçeği anahtar rol oynamaktadır Jack Edmonds'un ' algoritmaları için maksimum eşleşme olmayan ikili grafiklerinde ve minimum ağırlık mükemmel uyum.
Olarak çok yüzlü kombinatorik , faktör kritik grafikler yönleriyle tarif önemli bir rol oynamaktadır uygun politop belirli bir grafik.
n - k köşelerinin her alt kümesinin mükemmel bir eşleşmesi varsa , bir grafiğin k -faktörü açısından kritik olduğu söylenir . Bu tanım altında, hipo-eşleşmeyen bir grafik 1 faktör açısından kritiktir. Daha da genel olarak, bir grafiktir ( a , b ) a-faktör kritik her alt küme halinde N - k köşe bir sahiptir r faktörünü olduğunu, bu bir tepe dizi r -Ücretli alt grafiği verilen grafik.
Bir kritik grafiktir (koşul olmaksızın), genellikle bir ihtiyacı renk sayısını azaltır ve köşelerin her biri ve bundan da bir grafik anlamına geldiği varsayılır grafik boyama . Kritiklik kavramı, grafik teorisinde çok daha genel olarak, olası her bir tepe noktasının kaldırılmasının grafiğin ilgili bazı özelliklerini değiştirdiği veya değiştirmediği grafiklere atıfta bulunmak için kullanılmıştır. Bir uygun kritik grafik bir tepe çıkarılması boyutunu değiştirmez olan bir grafiktir , maksimum karşılaştırma ; Gallai'nin karakterizasyonuna göre, eşleşen kritik grafikler tam olarak her bağlı bileşenin faktör açısından kritik olduğu grafiklerdir. Tamamlayıcı grafik kritik grafik mutlaka uygun kritik, kritik bir grafikte nokta sayısı ile ilgili alt sınır kanıtlamak için Gallai tarafından kullanılan bir gerçektir.
Grafik teorisinin ötesinde, faktör-kritiklik kavramı, matroidler üzerinde bir tür kulak ayrışması tanımlayarak ve tüm kulakların tuhaf olduğu bir kulak ayrışması varsa, bir matroidi faktör-kritik olarak tanımlayarak matroidlere genişletilmiştir .