Valid Inequalities for the Maximal Matching Polytope

Authors : Mustafa Kemal Tural

Pages : 374-385

Doi:10.37094/adyujsci.540858

View : 17 | Download : 6

Publication Date : 2019-12-30

Article Type : Research Paper

Abstract :     Verilen bir G=(V,E) çiz gesinde, uçları kesişmeyen kenarlardan oluşan M k ümesine eşleme denir. Herhangi başka bir eşlemenin öz altkümesi olmayan bir eşlemeye maksimal eşleme denir. G çizgesindeki maksimal eşlemelerin insidans vektörlerinin konveks örtüsüne G kümesi ile ilişkili maksimal eşleme politopu adı verilir. Bu çalışmada, maksimal eşleme politopu için yeni geçerli eşitsizlik sınıfları sunulmaktadır.
Keywords : Eşleme, Maksimal Eşleme, Geçerli eşitsizlikler, Eşleme politopu, Maksimal eşleme politopu