邊著色圖中的異色和單色匹配.pdf

1、一個(gè)圖G=(V,E)稱為邊著色的，如果存在一個(gè)滿射C：E→{1，2，…，r}，即顏色集合。邊著色圖G的一個(gè)匹配稱之為是單色的，若它的所有邊都有相同的顏色，而G的一個(gè)匹配稱為是異色的，若它的任意兩邊的顏色均不相同。 在一般圖中，尋找最大匹配問題是多項(xiàng)式時(shí)間內(nèi)可以解決的，但與它不同的是，在邊著色圖中，最大異色匹配問題是NP-完備的。這就是說在邊著色圖中，無論是找一個(gè)“好的”完美異色匹配存在的充要條件，或是找到最大的異色匹配都是不容易

2、的。而對于邊著色圖中的單色匹配問題，則有較少的結(jié)果。 本文主要研究的是邊著色圖中的匹配問題，其中包括異色匹配，單色匹配及其與它們相應(yīng)的算法問題兩大部分。在第一章中，主要介紹了邊著色圖，異色子圖與單色子圖的歷史，以及異色子圖、單色子圖、異色匹配和單色匹配的基本概念。同時(shí)，為了更容易理解第二、三章所含內(nèi)容，在本章中也列出了一些常用的定義、等式、記號等等。 第二章中，首先給出了關(guān)于異色匹配的一系列新定義。通過這些新定義，我們給

3、出了：邊著色二部圖中，完美異色匹配存在的Hall-型的充分條件，一般邊著色圖中完美異色匹配存在的Tutte-型充分條件，以及邊著色二部圖中最大異色匹配的算法及其復(fù)雜性。然后，給出了一些與最大異色匹配有關(guān)的性質(zhì)。最后，我們分別給出完全二部圖K<,n,m>和完全圖K<,2n>的最大異色匹配。 鑒于Ramsey理論與2-邊著色圖的密切關(guān)系，在第三章中，我們考慮了2-邊著色二部圖的最大單色匹配問題，給出了最大單色匹配所含的邊數(shù)。最后，我