Grup Tuplelar öyle ki diğer üyeleri

Question

ile hiçbir ortak unsurlar Yani bu böyle gider gerçek bir dünya sorunla karşılaştık bir grup paylarında her öğe: biz gruba sıralamak gerekir çiftlerinin bir listesi var. Toplam sahip olduğumuz grup sayısını en aza indirmek istiyoruz; bir grubun herhangi bir üyesinin grubun diğer üyeleriyle bir öğeyi paylaşamaması. İşte

bir örnektir. Tuples listemiz (A, B), (B, C), (C, A), (D, E), (F, G) dir. [(A, B), (D, E), (F, G)], [(B, C)], [(C, A)] yaparak üç grup oluşturabiliriz.

optimum polinom zamanda bu sorunu çözmek mümkün mü? Açgözlü çözüm ne kadar kötü? Bunun farklı bir sorun olarak ortaya çıkmış olması muhtemeldir, ancak başka bir şeye nasıl indirgeyeceğimi tam olarak anlayamıyorum (grafik rengi akla geliyor). Her demet girişi bir düğümdür ve kenarları dizilerini tarafından verilen bir grafik bulunmaktadır: edge-coloring problem olarak düşünülebilir belirtildiği gibi

Answer 1

sorunu. Tuplleri gruplara ayırmak, daha sonra uç noktaları paylaşmayan (daha sonra eşleştirmeler) kenar gruplarının bulunmasına karşılık gelir; Diğer bir deyişle, her bir kenar boyaması size bir küme sağlar ve her bir küme, size bir kenar boyama sağlar. Ne yazık ki, en iyi kenar renklendirme bulmak için NP -Zor, yani senin sorunun genel NP -Zor içindedir. Sabit faktör yaklaşımları üreten bu problem için yaklaşık algoritmalar vardır, ancak P = NP hiçbir kesin algoritma olmadıkça. Eğer başlığın başına elemanların herhangi bir sayıda izin vermek için bu sorunu genelleştirirsek

, o zaman bu sorun çok daha zor olur. Bu sorun genel versiyon gerçekten NP -Sert ve grafik boyama gelen bir azalma ile, yaklaştığı çok zordur. Belirli bir vakadaki azalmanın bir örneğini göstereceğim, ancak oldukça güzel bir şekilde genelleştiriyor.

bu gibi bir grafik verilen:

A -- B -- C 
| | | 
D -- E -- F 

Biz dizilerini, bir dizi demet içinde her bir giriş bu düğüme bitişik kenarların grubu her düğüm için bir oluşturmak gerekir. Örneğin, yukarıdaki grafikte, bu dizilerini oluşturacak ediyorum:

(AB, AD) 
(AB, BC, BE) 
(CB, CF) 
(AD, DE) 
(BE, DE, EF) 
(CF, EF) 

Artık bu dizilerini iki örtüşmeyen düşünün. Bu, bu tupllere karşılık gelen iki düğümün bitişik olmaması gerektiği anlamına gelir, çünkü eğer öyleyse, aralarındaki kenar tupllerde ortak bir unsur olur ve bu nedenle kümelenemezler. Öte yandan, eğer iki düğüm bitişik değilse, o zaman onların tuplleri aynı kümede bir araya getirilebilir, çünkü bir tupüldeki hiçbir kenar diğerinde bulunmaz.

Bu kurulumda, orijinal grafiğin herhangi bir rengi, tuplleri kümelendirmenin bir yolunu verir (aynı renkte verilen düğümler için tüm tuplleri aynı kümeye yerleştirir; hiçbiri bitişik değildir, bu nedenle çakışma yapmazlar), ve tuplleri kümelemenin herhangi bir şekilde bir rengi (bir küme içindeki aynı renkteki her bir tuple karşılık gelen tüm düğümleri renklendirir) verir. Bu nedenle, asgari sayıda kümenin bulunması, orijinal grafiğin kromatik sayısını bulmakta, yani NP -hard'dır ve gerçek değere yakın olan herhangi bir yaklaşma algoritmasını kabul etmemektedir.