Hipergraf dwudzielny
W teorii grafów termin hipergraf dwudzielny opisuje kilka powiązanych klas hipergrafów , z których wszystkie są naturalnymi uogólnieniami grafu dwudzielnego .
Właściwość B i 2-kolorowalność
Najsłabsza definicja dwustronności jest również nazywana 2-kolorowalnością . Hipergraf H = ( V , E ) jest nazywany 2-kolorowym, jeśli jego zbiór wierzchołków V można podzielić na dwa zbiory, X i Y , tak że każda hiperkrawędź spełnia zarówno X , jak i Y . Równoważnie wierzchołki H mogą być dwukolorowe, tak że żadna hiperkrawędź nie jest monochromatyczna. Każdy graf dwudzielny G = ( X + Y , E ) jest 2-kolorowalny: każda krawędź zawiera dokładnie jeden wierzchołek X i jeden wierzchołek Y , więc np. X można pokolorować na niebiesko, a Y na żółto i żadna krawędź nie jest monochromatyczna.
Właściwość 2-kolorowalności została po raz pierwszy wprowadzona przez Felixa Bernsteina w kontekście zestawów rodzin; dlatego jest również nazywany Własnością B .
Dokładna 2-kolorowalność
Silniejsza definicja dwudzielności jest następująca: hipergraf nazywamy dwudzielnym , jeśli jego zbiór wierzchołków V można podzielić na dwa zbiory, X i Y , tak że każda hipergraf zawiera dokładnie jeden element X . Każdy graf dwudzielny jest również hipergrafem dwudzielnym.
Każdy dwudzielny hipergraf jest 2-kolorowy, ale dwudzielność jest silniejsza niż 2-kolorowalność. Niech H będzie hipergrafem na wierzchołkach {1, 2, 3, 4} z następującymi hiperkrawędziami:
{ {1,2,3} , {1,2,4} , {1,3,4} , {2,3,4} }
To H jest 2-kolorowe, na przykład przez partycję X = {1,2} i Y = {3,4}. Nie jest on jednak dwudzielny, ponieważ każdy zbiór X z jednym elementem ma puste przecięcie z jedną hiperkrawędzią, a każdy zbiór X z dwoma lub więcej elementami ma przecięcie o rozmiarze 2 lub większym z co najmniej dwoma hiperkrawędziami.
Twierdzenie Halla o małżeństwie zostało uogólnione z grafów dwudzielnych na hipergrafy dwudzielne; zobacz Twierdzenia typu Halla dla hipergrafów .
n -partytynowość i tęczowość
Silniejsza definicja brzmi: mając liczbę całkowitą n , hipergraf nazywamy n -jednostajnym, jeśli wszystkie jego hiperkrawędzie zawierają dokładnie n wierzchołków. Hipergraf n -jednolity nazywamy n -częściowym , jeśli jego zbiór wierzchołków V można podzielić na n podzbiorów, tak że każdy hipergraf zawiera dokładnie jeden element z każdego podzbioru. Alternatywnym terminem jest kolor tęczy .
Każdy hipergraf n -cząstkowy jest dwudzielny, ale n-cząstkowy jest silniejszy niż dwuczęściowy. Niech H będzie hipergrafem na wierzchołkach {1, 2, 3, 4} z następującymi hiperkrawędziami;
{ {1,2,3} , {1,2,4} , {1,3,4} }
To H jest 3-jednolite. Jest dwudzielny według partycji X = {1} i Y = {2,3,4}. Nie jest to jednak 3-częściowe: w każdym podziale V na 3 podzbiory co najmniej jeden podzbiór zawiera dwa wierzchołki, a zatem co najmniej jedna hiperkrawędź zawiera dwa wierzchołki z tego podzbioru.
3-częściowy hipergraf jest często nazywany „hipergrafem trójdzielnym”. Jednak hipergraf dwuczęściowy to nie to samo, co hipergraf dwudzielny; jest to równoważne grafowi dwudzielnemu .
Porównanie z innymi pojęciami dwustronności
Istnieją inne naturalne uogólnienia grafów dwudzielnych. Hipergraf nazywany jest zrównoważonym , jeśli jest zasadniczo 2-kolorowy i pozostaje zasadniczo 2-kolorowy po usunięciu dowolnej liczby wierzchołków (patrz Zrównoważony hipergraf ).
Właściwości dwustronności i równowagi nie implikują siebie nawzajem.
Dwustronność nie oznacza równowagi. Na przykład, niech H będzie hipergrafem z wierzchołkami {1,2,3,4} i krawędziami:
{ {1,2,3} , {1,2,4} , {1,3,4} }
Jest dwudzielny według partycji X = {1}, Y = {2,3,4}. Ale nie jest zrównoważony. Na przykład, jeśli wierzchołek 1 zostanie usunięty, otrzymamy ograniczenie H do {2,3,4}, które ma następujące hiperkrawędzie;
{ {2,3} , {2,4} , {3,4} }
Nie jest 2-kolorowy, ponieważ w każdym 2-kolorowym są co najmniej dwa wierzchołki tego samego koloru, a zatem co najmniej jeden z hiperkrawędzi jest monochromatyczny.
Innym sposobem, aby zobaczyć, że H nie jest zrównoważony, jest to, że zawiera cykl o nieparzystej długości C = (2 - {1,2,3} - 3 - {1,3,4} - 4 - {1,2,4} - 2), a żadna krawędź C nie zawiera wszystkich trzech wierzchołków 2,3,4 C .
Równowaga nie oznacza dwustronności. Niech H będzie hipergrafem: [ potrzebne źródło ]
{ {1,2} , {3,4} , {1,2,3,4} }
jest 2-kolorowy i pozostaje 2-kolorowy po usunięciu z niego dowolnej liczby wierzchołków. Jednak nie jest dwudzielny, ponieważ aby mieć dokładnie jeden zielony wierzchołek w każdej z pierwszych dwóch hiperkrawędzi, musimy mieć dwa zielone wierzchołki w ostatniej hiperkrawędzi.
Zobacz też
- ^ Bernstein, F. (1908), "Zur theorie der trygonometrische Reihen", Leipz. Ber. , 60 : 325–328 .
- Bibliografia _ Kessler, Ofra (15.10.1990). „O możliwym rozszerzeniu twierdzenia Halla na hipergrafy dwudzielne” . Matematyka dyskretna . 84 (3): 309–313. doi : 10.1016/0012-365X(90)90136-6 . ISSN 0012-365X .
- Bibliografia _ _ _ _ : 10.1137/1.9781611974331.ch126 , ISBN 978-1-61197-433-1
- ^ Aharoni, Ron (1985-12-01). „Dopasowania inn-partiten-graphs” . Grafy i kombinatoryka . 1 (1): 303–304. doi : 10.1007/BF02582958 . ISSN 1435-5914 . S2CID 19258298 .
- ^ Guruswami, Venkatesan; Lee, Euiwoong (2018-06-01). „Wyniki silnej nieprzybliżenia na zrównoważonych hipergrafach w kolorach tęczy”. Kombinatoryka . 38 (3): 547–599. doi : 10.1007/s00493-016-3383-0 . ISSN 1439-6912 . S2CID 53566425 .