匹配 (图论)

图论中,一个是一个匹配(或称独立边集)是指这个图之中,任意两条边都没有公共的顶点。这时每个顶点都至多连出一条边,而每一条边都将一对顶点相匹配。

严格定义

对于一个给定的图G=(V,E),这幅图的一个匹配M是图G的一个子图(由原来的图的一部分顶点和一部分边构成的图),其中每两条边都不相邻(没有公共顶点)。在匹配图中,一个顶点连出的边数至多是一条。如果这个顶点连出一条边,就称这个顶点是已匹配的

G的一个极大匹配是指这样一个匹配,它不可能是图G的任何一个匹配的真子图。换句话说,如果M是图G的一个极大匹配,那么不可能有另一个匹配包含M的全部边,而不等于M。如果一个子图包含了M,并且还有其它的边,那么必然不是匹配,也就是说一定有两条边有公共顶点。如果M是图G的一个极大匹配,那么G的每一条边都和M中的一条边相邻(否则可以加上这条边)。以下的三幅图是极大匹配的例子。

G的一个最大匹配是另一个概念,指边数最多的匹配。最大匹配可能有不止一个,但最大匹配的边数是确定的,并且不可能超过图中顶点数的一半。这是因为一个匹配中的一条边对应一对(两个)顶点,而不同边所对应的两对顶点是完全不同的,否则它们就是相邻的两条边了。最大匹配中的顶点数称为图的“配对数”,一般记作。最大匹配显然都是极大匹配,但极大匹配不一定是最大匹配。以下三幅图是最大匹配的例子。可以看出,在左起第一幅图中,最大匹配的顶点数是4,但在上面的极大匹配的例子中,存在着只有1条边的极大匹配。左起第二幅图中也是一样,最大匹配的顶点数是6,但在上面的极大匹配的例子中,存在着只有2条边的极大匹配。左起第三幅图则是一个“最大匹配必然是极大匹配”的例子。

G的一个完美匹配Perfect Match)是一个包括了图G中原来的所有顶点的匹配,是最大匹配的一种。一般来说,最大匹配不一定使用了原图的所有顶点,因此配对数小于等于原图的顶点数目,比如说上面左起第一和第三幅图。而第二幅图则是一个完美匹配的例子。完美匹配有时也叫做全局匹配或完全匹配。完美匹配同时也是一个原图的最小边数的边覆盖(即是用最少的边包括所有顶点的子图)。

一个准完美匹配则是当完美匹配不存在时的一个近似。准完美匹配中,原图只有一个顶点没有被使用,也就是说只差一个顶点达到完美匹配,这是因为原图的顶点数是奇数,完美匹配不可能存在。准完美匹配必然是最大匹配。

对一个给定的匹配M,定义:

  • 一条交替路径Alternating Path)是指这样一条路径,其中的每一条边交替地属于或不属于匹配M。比如说,第一、三、五条边属于M,而第二、四、六条不属于M,等等。
  • 一条增广路径Augmenting Path)是指从M中没有用到的顶点开始,并从M中没有用到的顶点结束的交替路径。

可以证明,一个匹配是最大匹配,当且仅当它没有任何增广路徑(这个结论有时被称为贝尔热英语Claude Berge引理)。

性质

任意图中,极大匹配的边数不少于最大匹配的边数的一半[1]

如果A和B是两个极大匹配,那么|A| ≤ 2|B||B| ≤ 2|A|。因为,在B \ A里的每条边最多与A \ B中的两条边相连。而且,根据极大性,在A \ B中的边一定与一条B \ A中的边相连。所以

因此我们可以得到:

特别地,这个结论告诉我们任何一个极大匹配都是最大匹配的2近似,也是最小的极大匹配的2近似。这个不等式是严格的。比如一个图G是一个4个点3条边的链,那么最小的极大匹配是1,最大匹配是2。

此外,霍爾婚配定理刻劃了二部圖中,何時能將一側全部頂點匹配到另一側。

匹配多项式

匹配多项式是一个图的k条边匹配的数量的生成函数。假定G是一个图,mkk条边匹配的数量。那么G的匹配多项式是

另一个匹配多项式的定义是

其中n是图中点的个数。每一种定义都有其作用,详情可以看匹配多项式的文章。

参考来源

  1. ^ Doratha E. Drake, Stefan Hougardy. A Simple Approximation Algorithm for the Weighted Matching Problem. Information Processing Letters. 

Read other articles:

Lokasi Provinsi Giresun Giresun adalah sebuah provinsi di Turki. Provinsi ini terletak di pantai Laut Hitam. Provinsi-provinsi yang terletak di sekitarnya adalah Trabzon di sebelah timur, Gumushane di barat daya, Erzincan di selatan, Sivas di tenggara, dan Ordu di sebelah barat. Ibu kota provinsi ini adalah Giresun. lbsDaftar provinsi Turki Adana · Adıyaman · Afyonkarahisar · Ağrı · Aksaray · Amasya · Ankara · Ant...

 

Purported pirate colony Captain Misson, described by Johnson as founder of Libertalia Part of a series onUtopias Mythical and religious Arcadia City of the Caesars Cloud cuckoo land Cockaigne Eden Elysium Fortunate Isles Garden of the gods Shangri-La Golden Age Satya Yuga Great Unity Ketumati Kingdom of God Opona Libertatia Mag Mell Mahoroba Merry England Mezzoramia Mount Penglai Most Great Peace New Jerusalem Zion Literature List The Republic Utopia Gulliver's Travels Dystopian literature Th...

 

Galeazzo Ciano Menteri Urusan Luar Negeri ItaliaMasa jabatan9 Juni 1936 – 6 Februari 1943Penguasa monarkiVictor Emmanuel IIIRaja ItaliaPerdana MenteriBenito Mussolini PendahuluBenito MussoliniPenggantiBenito Mussolini Informasi pribadiLahirGian Galeazzo Ciano(1903-03-18)18 Maret 1903Livorno, Toskana, ItaliaMeninggal11 Januari 1944(1944-01-11) (umur 40)Verona, Republik Sosial ItaliaPartai politikPartai Fasis Nasional (PFN)Suami/istriEdda Mussolini Ciano (1910-1944)AnakFabrizio ...

Don Bosco M. WanggeDrs., M.Si Bupati Ende 7Masa jabatan2009 – 2014WakilDrs. Achmad Mochdar PendahuluDrs. Paulinus DomiPenggantiIr. Marselinus Y. W. PetuPresidenSusilo Bambang Yudhoyono Joko WidodoGubernurFrans Lebu Raya Informasi pribadiLahir21 Juni 1954 (umur 69) Lela, Sikka, Nusa Tenggara TimurKebangsaanIndonesiaSuami/istriMasdiana BaliAnak1. Maria Gladilia Wangge2. Anastasia Dwi Yoga P. WanggeProfesiPolitisiSunting kotak info • L • B Drs. Don Bosco M. Wang...

 

Hull CityNama lengkapHull City Association Football ClubJulukanThe TigersBerdiri1904; 120 tahun lalu (1904)StadionKCOMKingston upon Hull(Kapasitas: 25.586[1])PemilikAcun MedyaKetuaAcun IlıcalıManajerLiam RoseniorLigaLiga Utama Inggris2015–16ke-4, Championship (promosi lewat play-off) Kostum kandang Kostum tandang Kostum ketiga Musim ini Hull City Association Football Club adalah sebuah klub sepak bola asal Inggris. Klub ini bermarkas di Kingston upon Hull dan didirikan pada t...

 

Kuwait (dettagli) (dettagli) (AR) لكل الكويت(IT) Per il Kuwait Kuwait - Localizzazione Dati amministrativiNome completoStato del Kuwait Nome ufficialeدولة الكويت Lingue ufficialiarabo CapitaleAl Kuwait  (3.925.000 ab. / 2014) PoliticaForma di governoMonarchia costituzionale (Emirato) EmiroMisha'al Al-Ahmad Al-Jaber Al Sabah Primo ministroMohammad Sabah Al-Salem Al-Sabah Indipendenza19 giugno 1961 dal Regno Unito Ingresso nell'ONU14 maggio 1963 Superficie...

Crusader fortress in Nabatieh Governorate, Lebanon Not to be confused with Beaufort Castle, Luxembourg. Beaufort Castleقلعة الشقيفNabatieh Governorate, Lebanon The remains of the ancient Beaufort Castle (The Beautiful Castle) also known locally as Qal'at Al-Shaqif in Arnoun, Lebanon.Beaufort CastleCoordinates33°19′28″N 35°31′55″E / 33.3244°N 35.5320°E / 33.3244; 35.5320TypeCastleSite historyBuilt12th centuryBuilt byCrusaders Beaufort or Belfo...

 

Pada nama Vietnam ini, nama keluarga-nya adalah Lê. Menurut kebiasaan Vietnam, tokoh ini dipanggil dengan nama pemberian-nya Duyệt. Lê Văn Duyệt黎文悅Patung perunggu Lê Văn Duyệt di makamnyaLahir1763 atau 1764Định Tường, Vietnam selatanMeninggal3 Juli 1832 (usia 68)Gia Định (sekarang Kota Hồ Chí Minh), VietnamDikebumikanMakam Lê Văn Duyệt, Kota Hồ Chí MinhPengabdianPenguasa NguyễnDinasti NguyễnLama dinas1789–1832PangkatJenderalPerang/pertempuranPert...

 

United States historic placeCalpak Plant No. 11U.S. National Register of Historic Places Calpak Plant No. 11 in 2015, showing the non-historic canopy addition at the main entryLocation1721 C StreetSacramento, CaliforniaCoordinates38°35′09″N 121°28′49″W / 38.585830°N 121.480407°W / 38.585830; -121.480407Area6 acres (2.4 ha)Built1925ArchitectBush, PhilipNRHP reference No.84000939[1]Added to NRHPMay 17, 1984 The Calpak Plant No. 11 in Sa...

Fictional character from American Psycho For the EP, see Patrick Bateman (EP). Fictional character Patrick BatemanChristian Bale as Patrick BatemanFirst appearanceThe Rules of Attraction (1987)Last appearanceLunar Park (2005)Created byBret Easton EllisPortrayed by Christian Bale (American Psycho) Dechen Thurman(This Is Not an Exit) Michael Kremko(American Psycho 2) Casper Van Dien(The Rules of Attraction, deleted scene) Matt Smith & Benjamin Walker(American Psycho: The Musical) Casey Cott...

 

Children's animated television series Tumble LeafGenreAnimationCartoon seriesChildren's animationEducationalFantasyStop motionCreated byDrew HodgesVoices ofChristopher DownsBrooke WolloffZak McDowellAlex TrugmanCountry of originUnited StatesOriginal languageEnglishNo. of seasons4No. of episodes52 (101 segments)ProductionExecutive producersKelli Bixler, Drew HodgesRunning time24 minutesProduction companiesAmazon StudiosBix Pix Entertainment[1]Original releaseNetworkAmazon VideoReleaseM...

 

この項目には、一部のコンピュータや閲覧ソフトで表示できない文字が含まれています(詳細)。 数字の大字(だいじ)は、漢数字の一種。通常用いる単純な字形の漢数字(小字)の代わりに同じ音の別の漢字を用いるものである。 概要 壱万円日本銀行券(「壱」が大字) 弐千円日本銀行券(「弐」が大字) 漢数字には「一」「二」「三」と続く小字と、「壱」「�...

Данио-рерио Научная классификация Домен:ЭукариотыЦарство:ЖивотныеПодцарство:ЭуметазоиБез ранга:Двусторонне-симметричныеБез ранга:ВторичноротыеТип:ХордовыеПодтип:ПозвоночныеИнфратип:ЧелюстноротыеГруппа:Костные рыбыКласс:Лучепёрые рыбыПодкласс:Новопёрые рыбыИн�...

 

Architectural feature of mosques For other uses, see Minaret (disambiguation). Minaret at the Umayyad Mosque in Damascus A minaret (/ˌmɪnəˈrɛt, ˈmɪnəˌrɛt/;[1] Arabic: منارة, romanized: manāra, or Arabic: مِئْذَنة, romanized: miʾḏana; Turkish: minare; Persian: گل‌دسته, romanized: goldaste) is a type of tower typically built into or adjacent to mosques. Minarets are generally used to project the Muslim call to prayer (adhan) from a muezz...

 

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article is written like a personal reflection, personal essay, or argumentative essay that states a Wikipedia editor's personal feelings or presents an original argument about a topic. Please help improve it by rewriting it in an encyclopedic style. (July 2019) (Learn how and when to remove this message) This article needs additional ci...

2022 mass shooting in Uvalde, Texas, US Uvalde school shootingPolice officers inside the school during the shooting, 17 minutes before Ramos was killedLocation of Robb Elementary School in Uvalde, TexasLocationRobb Elementary School,715 Old Carrizo RoadUvalde, Texas, U.S.Coordinates29°11′58″N 99°47′18″W / 29.19944°N 99.78833°W / 29.19944; -99.78833DateMay 24, 2022; 2 years ago (May 24, 2022) 11:28 a.m. – 12:50 p.m. (UTC−05:00)TargetStu...

 

Visualisasi hasil sintesis cDNA untai pertama DNA komplemen atau DNA pelengkap, atau jauh lebih dikenal dengan singkatannya cDNA (dari complementary DNA), merupakan DNA untai tunggal sintetik/buatan yang disalin dari untai mRNA menggunakan teknik PCR dengan memanfaatkan enzim transkriptase balik.[1] Penggunaan cDNA ini sangat luas, terutama dalam analisis ekspresi genetik dan transkriptomika.[1] mRNA berkas tunggal atau transkriptom bersifat tidak stabil karena mudah dicerna d...

 

العلاقات التشيكية السعودية التشيك السعودية   التشيك   السعودية تعديل مصدري - تعديل   العلاقات التشيكية السعودية هي العلاقات الثنائية التي تجمع بين التشيك والسعودية.[1][2][3][4][5] ويتبادل البلدين التمثيل الدبلوماسي من خلال سفارة المملكة العرب...

For the 2010 film, see Bursting Out (film). This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Bursting Out – news · newspapers · books · scholar · JSTOR (May 2021) (Learn how and when to remove this message) 1978 live album by Jethro TullBursting OutLive album by Jethro TullReleased22 September 1978Rec...

 

Canadian film production company Bron Media CorporationTrade nameBron StudiosIndustryMotion picturesFounded2010FounderAaron L. GilbertBrenda GilbertHeadquartersVancouver, British Columbia, CanadaKey peopleAaron L. Gilbert (CEO)Brenda Gilbert (Co-President)Joel Guralnick (CLO)Steven Thibault (COO)DivisionsBron AnimationBron Creative (JV)Bron StudiosBron ReleasingBron LifeBron DigitalSubsidiariesBron Venture I LLCMad SolarWebsitebronstudios.com Bron Studios (stylized as BRON) is a Canadian moti...