Vyvážený hypergraf - Balanced hypergraph

v teorie grafů, a vyvážený hypergraf je hypergraf který má několik vlastností analogických vlastnostem a bipartitní graf.

Vyvážené hypergrafy představil Berge[1] jako přirozené zobecnění bipartitních grafů. Poskytl dvě rovnocenné definice.

Definice podle 2-barevnosti

Hypergraf H = (PROTI, E) je nazýván 2-barevný jestliže jeho vrcholy mohou 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 lze obarvit modře a Y může být zbarven žlutě a žádný okraj není jednobarevný.

Hypergraf, ve kterém jsou některé hyper-hrany singletony (obsahují pouze jeden vrchol), zjevně není 2barevný; abychom se vyhnuli takovým triviálním překážkám 2barevnosti, je běžné uvažovat o hypergrafech, které jsou v podstatě 2-barevný, tj. stanou se 2-barevnými po odstranění všech svých singletonových hyperedges.[2]:468

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ů. Formálně pro každou podmnožinu U z PROTI, definovat omezení z H na U jako hypergraf HU = (U, EU) kde . Pak H se nazývá vyvážený iff HU je v podstatě 2-barevný pro každou podskupinu U z PROTI. Jednoduchý graf je bipartitní, pokud je dvoubarevný, pokud je vyvážený.

Definice lichými cykly

A cyklus (nebo a obvod) v hypergrafu je cyklická střídavá sekvence odlišných vrcholů a hyper-hran:proti1, E1, proti2, E2, ..., protik, Ek, protik+1=proti1), kde každý vrchol protii je obsažen v obou Ei−1 a Ei. Číslo k se nazývá délka cyklu.

Hypergrafie je vyrovnaný pokud každý lichý cyklus C v H má hranu obsahující alespoň tři vrcholy C.[3]

Všimněte si, že v jednoduchém grafu obsahují všechny hrany pouze dva vrcholy. Jednoduchý graf je tedy vyvážený, pokud neobsahuje vůbec žádné liché cykly, což platí, pokud je bipartitní.

Berge[1] dokázal, že obě definice jsou rovnocenné; důkaz je k dispozici také zde.[2]:468–469

Vlastnosti

Některé věty o bipartitních grafech byly zobecněny na vyvážené hypergrafy.[4][2]:468–470

  • V každém vyváženém hypergrafu je minimum vrcholový kryt má stejnou velikost jako jeho maximum vhodný. Tím se zobecňuje Kőnig-Egervaryova věta na bipartitních grafech.
  • V každém vyváženém hypergrafu je stupeň (= maximální počet hyperhranů obsahujících jeden vrchol) se rovná chromatický index (= nejmenší počet barev potřebných pro vybarvení hyper-hran, takže žádné dvě hyper-hrany se stejnou barvou nemají společný vrchol).[5] Tím se zevšeobecní Konigova věta o bipartitních grafech.
  • Každý vyvážený hypergraf splňuje zobecnění Hallova věta o manželství:[3] připouští perfektní shodu iff pro všechny nesouvislé sady vrcholů PROTI1, PROTI2, pokud pro všechny hrany E v E, pak |PROTI2| ≥ |PROTI1|. Vidět Hallovy věty pro hypergrafy.
  • Každý vyvážený hypergraf s maximálním stupněm D, lze rozdělit na D okrajové disjunktní shody.[1]:Kapitola 5[3]:Dodatek 3

A k-násobný příčný člen vyváženého hypergrafu lze vyjádřit jako spojení k dvojice-disjunktní příčné a takové rozdělení lze získat v polynomiálním čase.[6]

Srovnání s jinými pojmy bipartitality

Kromě rovnováhy existují alternativní zobecnění bipartitních grafů. 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 (vidět bipartitní hypergraf ). Je zřejmé, že každý bipartitní graf je dvoubarevný.

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

Rovnováha neznamená bipartititu. Nechat H být hypergrafem:[7]

{ {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.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 žádná hrana C obsahuje všechny tři vrcholy 2,3,4 z C.

Trojstrannost neznamená rovnováhu. Například nechte H být tripartitní hypergraf s vrcholy {1,2}, {3,4}, {5,6} a hranami:

{ {1,3,5}, {2,4,5}, {1,4,6} }

Není to vyvážené, protože pokud odstraníme vrcholy 2,3,6, zbytek je:

{ {1,5}, {4,5}, {1,4} }

který není barevný, protože se jedná o 3-cyklus.

Jiným způsobem, jak zjistit, že není vyvážený, je to, že obsahuje cyklus liché délky C = (1 - {1,3,5} - 5 - {2,4,5} - 4 - {1,4,6} - 1) a žádná hrana C obsahuje všechny tři vrcholy 1,4,5 z C.

Související vlastnosti

Úplně vyvážené hypergrafy

Hypergraf se nazývá naprosto vyvážený pokud každý cyklus C v H o délce alespoň 3 (nemusí to být nutně lichá délka) má hranu obsahující alespoň tři vrcholy C.[8]

Hypergraf H je zcela vyvážený, pokud je každý subhypergraf H stromový hypergraf.[8]

Normální hypergrafy

The Konig majetek hypergrafu H je vlastnost, že jeho minimum vrcholový kryt má stejnou velikost jako jeho maximum vhodný. The Kőnig-Egervaryova věta říká, že všechny bipartitní grafy mají vlastnost Konig.

Vyvážené hypergrafy jsou přesně hypergrafy H takové, že každý částečný subhypergraph z H má vlastnost Konig (tj. H má vlastnost Konig i po odstranění libovolného počtu hyperedges a vrcholů).

Pokud každý částečný hypergraf H má vlastnost Konig (tj. H má vlastnost Konig i po odstranění libovolného počtu hyper-hran - ale ne vrcholů), pak H se nazývá a normální hypergraf.[9]

Totálně vyvážený tedy znamená vyvážený, což znamená normální.

Reference

  1. ^ A b C Berge, Claude (1970). "Sur certains hypergraphes généralisant les graphes bipartites". Kombinatorická teorie a její aplikace. 1: 119–133.
  2. ^ A b C Lovász, László; Plummer, M. D. (1986), Teorie shody, Annals of Discrete Mathematics, 29, Severní Holandsko, ISBN  0-444-87916-1, PAN  0859549
  3. ^ A b C Conforti, Michele; Cornuéjols, Gérard; Kapoor, Ajai; Vušković, Kristina (01.09.1996). "Perfektní shoda ve vyvážených hypergrafech". Combinatorica. 16 (3): 325–329. doi:10.1007 / BF01261318. ISSN  1439-6912. S2CID  206792822.
  4. ^ Berge, Claude; Vergnas, Michel LAS (1970). „Sur Un Theorems Du Type König Pour Hypergraphes“. Annals of the New York Academy of Sciences. 175 (1): 32–40. doi:10.1111 / j.1749-6632.1970.tb56451.x. ISSN  1749-6632.
  5. ^ Lovász, L. (01.06.1972). "Normální hypergrafy a dokonalá hypotéza grafu". Diskrétní matematika. 2 (3): 253–267. doi:10.1016 / 0012-365X (72) 90006-4. ISSN  0012-365X.
  6. ^ Dahlhaus, Elias; Kratochvíl, Jan; Manuel, Paul D .; Miller, Mirka (1997-11-27). "Příčné rozdělení na vyvážené hypergrafy". Diskrétní aplikovaná matematika. 79 (1): 75–89. doi:10.1016 / S0166-218X (97) 00034-6. ISSN  0166-218X.
  7. ^ „zbarvení - Která generalizace bipartitních grafů je silnější?“. Matematická výměna zásobníků. Citováno 2020-06-27.
  8. ^ A b Lehel, Jenö (01.11.1985). „Charakterizace zcela vyvážených hypergrafů“. Diskrétní matematika. 57 (1): 59–65. doi:10.1016 / 0012-365X (85) 90156-6. ISSN  0012-365X.
  9. ^ Beckenbach, Isabel; Borndörfer, Ralf (01.10.2018). „Hallova a Kőnigova věta v grafech a hypergrafech“. Diskrétní matematika. 341 (10): 2753–2761. doi:10.1016 / j.disc.2018.06.013. ISSN  0012-365X.