Bipartitní hypergraf - Bipartite hypergraph

v teorie grafů, termín bipartitní hypergraf popisuje několik souvisejících tříd hypergrafy, z nichž všechny jsou přirozené zobecnění a bipartitní graf.

Vlastnost B a 2barevnost

Hypergraf H = (PROTI, E) je nazýván 2 barvy pokud je jeho vrchol nastaven PROTI lze rozdělit na dvě sady, X a Y, takže každý hyperedge splňuje obojí X a Y. Rovnocenně vrcholy H může být dvoubarevný, takže žádný hyperedge není monochromatický. Každý bipartitní graf G = (X+Y, E) je 2barevný: každá hrana obsahuje přesně jeden vrchol X a jeden vrchol Y, takže např. X mohou být vybarveny modře a Y může být zbarven žlutě a žádný okraj není jednobarevný.

Vlastnost pro 2-barevnost byla poprvé představena Felix Bernstein v kontextu stanovených rodin;^[1] proto se také nazývá Majetek B.

Přesná 2barevnost

Hypergraf se nazývá bipartitní pokud je jeho vrchol nastaven PROTI lze rozdělit na dvě sady, X a Y, takže každý hyperedge obsahuje přesně jeden prvek X.^[2][3]

Abychom zjistili, že tento smysl je silnější než 2barevnost, pojďme H být hypergrafem na vrcholech {1, 2, 3, 4} s následujícími hyper-hranami:

{ {1,2,3} , {1,2,4} , {1,3,4} , {2,3,4} }

Tento H je 2barevný, například oddílem X = {1,2} a Y = {3,4}. Není to však přesně 2 barvy, protože každá sada X s jedním prvkem má prázdný průnik s jedním hyperedge a každou sadou X se dvěma nebo více prvky má průnik velikosti 2 nebo více s alespoň dvěma hyperedges.

Každý bipartitní graf G = (X+Y, E) je přesně-2-barevný.

Hallova věta o manželství byla zobecněna z bipartitních grafů na přesně 2barevné hypergrafy; vidět Hallovy věty pro hypergrafy.

n- zvláštnost a duhovou barevnost

Dáno celé číslo nse nazývá hypergraf n-jednotka, pokud všechny její hyperedge obsahují přesně n vrcholy. An n- volá se jednotný hypergraf n-část pokud je jeho vrchol nastaven PROTI lze rozdělit na n podmnožiny takové, že každý hyperedge obsahuje přesně jeden prvek z každé podmnožiny. ^[4] Alternativní termín je duhové barvy.^[5]

To vidět n-vlastnost je silnější než přesná-2-barevnost, řekněme H být hypergrafem na vrcholech {1, 2, 3, 4} s následujícími hyper-hranami;

{ {1,2,3} , {1,2,4} , {1,3,4} }

Tento H je 3 uniformní. Je přesně 2-barevný podle oddílu X = {1} a Y = {2,3,4}. Není to však 3-partite: v každém oddílu PROTI do 3 podmnožin, alespoň jedna podmnožina obsahuje dva vrcholy, a tedy alespoň jedna hyperedge obsahuje dva vrcholy z této podmnožiny.

Srovnání s jinými pojmy bipartitality

Existují i ​​další přirozená zobecnění bipartitních grafů. Hypergraf se nazývá vyrovnaný pokud je v podstatě 2-barevný a zůstává v podstatě 2-barevný po odstranění libovolného počtu vrcholů (viz Vyvážený hypergraf ).

Vlastnosti bipartitity a rovnováhy se navzájem neimplikují.

Bipartitita neznamená rovnováhu. Například nechte H být hypergrafem s vrcholy {1,2,3,4} a hranami:

{ {1,2,3} , {1,2,4} , {1,3,4} }

Oddíl je dvojdílný X={1}, Y= {2,3,4}. Ale není vyvážený. Například pokud je vrchol 1 odstraněn, dostaneme omezení H na {2,3,4}, která má následující hyperedge;

{ {2,3} , {2,4} , {3,4} }

Není 2-barevný, protože v jakémkoli 2-barvení jsou alespoň dva vrcholy se stejnou barvou, a tedy alespoň jeden z hyperedges je jednobarevný.

Další způsob, jak to vidět H není vyvážený je to, že obsahuje cyklus liché délky C = (2 - {1,2,3} - 3 - {1,3,4} - 4 - {1,2,4} - 2) a ne okraj C obsahuje všechny tři vrcholy 2,3,4 z C.

Rovnováha neznamená bipartititu. Nechat H být hypergrafem:^{[Citace je zapotřebí ]}

{ {1,2} , {3,4} , {1,2,3,4} }

je 2-barevný a zůstává 2-barevný po odstranění libovolného počtu vrcholů z něj. Není to však bipartitní, protože abychom měli přesně jeden zelený vrchol v každé z prvních dvou hyper-hran, musíme mít v poslední hyper-hraně dva zelené vrcholy.

Viz také

• Shoda v hypergrafech
• Vrcholový kryt v hypergrafech

Reference