Tvådelad hypergraf
I grafteorin beskriver termen tvådelad hypergraf flera relaterade klasser av hypergrafer , som alla är naturliga generaliseringar av en tvådelad graf .
Egenskap B och 2-färgbarhet
Den svagaste definitionen av tvådeladhet kallas också 2-färgbarhet . En hypergraf H = ( V , E ) kallas 2-färgbar om dess vertexuppsättning V kan delas upp i två uppsättningar, X och Y , så att varje hyperkant möter både X och Y. På motsvarande sätt kan hörn av H vara 2-färgade så att ingen hyperkant är monokromatisk. Varje tvådelad graf G = ( X + Y , E ) är 2-färgbar: varje kant innehåller exakt en vertex av X och en vertex av Y , så t.ex. X kan färgas blå och Y kan färgas gul och ingen kant är monokromatisk.
Egenskapen 2-färgbarhet introducerades först av Felix Bernstein i samband med uppsättningsfamiljer; därför kallas det även Fastighet B .
Exakt 2-färgbarhet
En starkare definition av bipartiteness är: en hypergraf kallas bipartite om dess vertexuppsättning V kan delas upp i två uppsättningar, X och Y , så att varje hyperedge innehåller exakt ett element av X . Varje tvådelad graf är också en tvådelad hypergraf.
Varje bipartit hypergraf är 2-färgbar, men bipartiteness är starkare än 2-färgbarhet. Låt H vara en hypergraf på hörnen {1, 2, 3, 4} med följande hyperkanter:
{ {1,2,3} , {1,2,4} , {1,3,4} , {2,3,4} }
Detta H är 2-färgbart, till exempel av partitionen X = {1,2} och Y = {3,4}. Den är dock inte tvådelad, eftersom varje uppsättning X med ett element har en tom skärning med en hyperkant, och varje uppsättning X med två eller flera element har en skärning av storlek 2 eller mer med minst två hyperkanter.
Halls äktenskapsteorem har generaliserats från tvådelade grafer till tvådelade hypergrafer; se Hall-typsatser för hypergrafer .
n -partiskhet och regnbågsfärgbarhet
En starkare definition är: givet ett heltal n kallas en hypergraf n -uniform om alla dess hyperkanter innehåller exakt n hörn. En n -uniform hypergraf kallas n -partit om dess vertexuppsättning V kan delas upp i n delmängder så att varje hyperedge innehåller exakt ett element från varje delmängd. En alternativ term är regnbågsfärgbar .
Varje n -partititetshypergraf är tvådelad, men n-partithet är starkare än tvådeladhet. Låt H vara en hypergraf på hörnen {1, 2, 3, 4} med följande hyperkanter;
{ {1,2,3} , {1,2,4} , {1,3,4} }
Detta H är 3-uniform. Den är tvådelad av partitionen X = {1} och Y = {2,3,4}. Det är dock inte 3-delad: i varje partition av V i 3 delmängder innehåller minst en delmängd två hörn, och således innehåller minst en hyperkant två hörn från denna delmängd.
En 3-delad hypergraf kallas ofta "trepartshypergraf". En 2-delad hypergraf är dock inte detsamma som en tvådelad hypergraf; det motsvarar en tvådelad graf .
Jämförelse med andra föreställningar om tvåpart
Det finns andra naturliga generaliseringar av tvådelade grafer. En hypergraf kallas balanserad om den är i huvudsak 2-färgbar, och förblir i huvudsak 2-färgbar vid radering av valfritt antal hörn (se Balanserad hypergraf ).
Egenskaperna för tvådeladhet och balans innebär inte varandra.
Tvåpartighet innebär inte balans. Låt till exempel H vara hypergrafen med hörn {1,2,3,4} och kanter:
{ {1,2,3} , {1,2,4} , {1,3,4} }
Den är tvådelad av partitionen X ={1}, Y ={2,3,4}. Men är inte balanserad. Till exempel, om vertex 1 tas bort, får vi begränsningen av H till {2,3,4}, som har följande hyperkanter;
{ {2,3} , {2,4} , {3,4} }
Den är inte 2-färgbar, eftersom det i vilken 2-färgning som helst finns minst två hörn med samma färg, och därför är minst en av hyperkanterna monokromatisk.
Ett annat sätt att se att H inte är balanserad är att den innehåller cykeln med udda längd C = (2 - {1,2,3} - 3 - {1,3,4} - 4 - {1,2,4} - 2), och ingen kant på C innehåller alla tre hörn 2,3,4 i C .
Balans innebär inte tvåsidighet. Låt H vara hypergrafen: [ citat behövs ]
{ {1,2} , {3,4} , {1,2,3,4} }
den är 2-färgbar och förblir 2-färgbar när du tar bort valfritt antal hörn från den. Det är dock inte tvådelat, eftersom för att ha exakt en grön vertex i var och en av de två första hyperkanterna måste vi ha två gröna hörn i den sista hyperedgen.
Se även
- ^ Bernstein, F. (1908), "Zur theorie der trigonometrische Reihen", Leipz. Ber. , 60 : 325-328 .
- ^ Aharoni, Ron; Kessler, Ofra (1990-10-15). "Om en möjlig utvidgning av Halls teorem till tvådelade hypergrafer" . Diskret matematik . 84 (3): 309–313. doi : 10.1016/0012-365X(90)90136-6 . ISSN 0012-365X .
- ^ Annamalai, Chidambaram (2015-12-21), "Finding Perfect Matchings in Bipartite Hypergraphs", Proceedings of the 2016 Annual ACM-SIAM Symposium on Discrete Algorithms , Proceedings, Society for Industrial and Applied Mathematics, s. 1814–1823, doi : 10.1137/1.9781611974331.ch126 , ISBN 978-1-61197-433-1
- ^ Aharoni, Ron (1985-12-01). "Matchningar inn-partiten-grafer". Grafer och kombinatorik . 1 (1): 303–304. doi : 10.1007/BF02582958 . ISSN 1435-5914 . S2CID 19258298 .
- ^ Guruswami, Venkatesan; Lee, Euiwoong (2018-06-01). "Starka resultat av otillräcklighet på balanserade regnbågsfärgade hypergrafer". Combinatorica . 38 (3): 547–599. doi : 10.1007/s00493-016-3383-0 . ISSN 1439-6912 . S2CID 53566425 .