Dopasowanie w hipergrafach

W teorii grafów dopasowanie w hipergrafie jest zbiorem hiperkrawędzi , w którym każde dwie hiperkrawędzie są rozłączne . Jest to rozszerzenie pojęcia dopasowywania w grafie .

Definicja

Przypomnijmy, że hipergraf H $to$ $para$ ( $V, E),$ gdzie $V$ to zbiór wierzchołków , a $E$ to zbiór podzbiorów V zwanych hiperkrawędziami . Każda hiperkrawędź może zawierać jeden lub więcej wierzchołków.

Dopasowanie w $H$ jest podzbiorem $M$ z $E , takim$ , że każde dwa hiperkrawędzie $e 1$ i $e 2$ w $M$ mają puste przecięcie (nie mają wspólnego wierzchołka).

Pasująca liczba hipergrafu $H$ jest największym rozmiarem dopasowania w $H$ . Często jest oznaczany przez $ν(H)$ .

Jako przykład niech $V$ będzie zbiorem ${1,2,3,4,5,6,7}.$ Rozważ 3-jednolity hipergraf na $V$ (hipergraf, w którym każda hipergraf zawiera dokładnie 3 wierzchołki). Niech $H$ będzie 3-jednostajnym hipergrafem z 4 hiperkrawędziami:

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

Następnie $H$ dopuszcza kilka dopasowań o rozmiarze 2, na przykład:

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

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

Jednak w dowolnym podzbiorze 3 hiperkrawędzi co najmniej dwie z nich przecinają się, więc nie ma dopasowania rozmiaru 3. Stąd pasująca liczba $H$ wynosi 2.

Przecinający się hipergraf

Hipergraf $H = (V, E)$ nazywamy przecinającym się , jeśli każde dwa hipergrafy w $E$ mają wspólny wierzchołek. Hipergraf $H$ przecina się wtedy i tylko wtedy, gdy nie ma dopasowania z dwoma lub więcej hipergrafami, wtedy i tylko wtedy, gdy $ν(H) = 1$ .

Dopasowanie na wykresie jako przypadek szczególny

Graf bez pętli własnych jest po prostu hipergrafem 2-jednorodnym: każda krawędź może być traktowana jako zbiór dwóch wierzchołków, które łączy. Na przykład ten 2-jednolity hipergraf reprezentuje graf z 4 wierzchołkami ${1,2,3,4}$ i 3 krawędziami:

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

Zgodnie z powyższą definicją dopasowanie na grafie to zbiór $M$ krawędzi, taki że każde dwie krawędzie w $M$ mają puste przecięcie. Jest to równoważne stwierdzeniu, że żadne dwie krawędzie w $M$ nie sąsiadują z tym samym wierzchołkiem; to jest dokładnie definicja dopasowania na wykresie .

Dopasowanie ułamkowe

Dopasowanie ułamkowe w hipergrafie to funkcja, która przypisuje ułamek w $[0,1]$ do każdej hiperkrawędzi, tak że dla każdego wierzchołka $v$ w $V$ suma ułamków hiperkrawędzi zawierających $v$ wynosi co najwyżej 1. Dopasowanie jest specjalnym przypadek dopasowania ułamkowego, w którym wszystkie ułamki wynoszą 0 lub 1. Rozmiar dopasowania ułamkowego to suma ułamków wszystkich hiperkrawędzi.

Ułamkowa liczba dopasowania hipergrafu $H$ jest największym rozmiarem dopasowania ułamkowego w $H$ . Jest często oznaczany przez $ν *(H)$ .

Ponieważ dopasowanie jest szczególnym przypadkiem dopasowania ułamkowego, dla każdego hipergrafu $H$ :

Pasująca liczba( $H$ ) ≤ pasująca liczba ułamkowa ( $H$ )

Symbolicznie ta zasada jest zapisana:

{\ Displaystyle \ nu (H) \ równoważnik \ nu ^ {*} (H)}

Ogólnie rzecz biorąc, ułamkowa pasująca liczba może być większa niż pasująca liczba. Twierdzenie Zoltána Fürediego podaje górne granice stosunku ułamkowej liczby pasującej ( $H$ ) / liczby pasującej ( $H$ ):

Jeśli każda hiperkrawędź w H zawiera co najwyżej r wierzchołków, to
${\ Displaystyle {\ Frac {\ nu ^ {*} (H)} {\ nu (H)}} \ równoważnik r-1 + {\ frac {1} {r}}.}$

W szczególności na prostym wykresie:

${\ Displaystyle {\ Frac {\ nu ^ {*} (H)} {\ nu (H)}} \ równoważnik {\ Frac {3} {2}}.}$
- Nierówność jest ostra: Niech $H r$ będzie $r$ -jednolitą skończoną płaszczyzną rzutową . Wtedy $ν (H r) = 1$ , ponieważ każde dwie hiperkrawędzie się przecinają, a $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px} ν * ( H r ) = r – 1 + 1 / r$ przez dopasowanie ułamkowe, które przypisuje wagę $1 / r$ każdej hiperkrawędzi (jest to dopasowanie, ponieważ każdy wierzchołek jest zawarty w $r$ hiperkrawędziach, a jego rozmiar to $r - 1 + 1 / r$ , ponieważ istnieje $r 2 - r + 1$ hiperkrawędzi). Zatem stosunek wynosi dokładnie $r - 1 + 1 / r$ .
Jeśli $r$ jest takie, że $r$ -jednolita skończona płaszczyzna rzutowa nie istnieje (na przykład $r = 7$ ), to zachodzi silniejsza nierówność:
${\ Displaystyle {\ Frac {\ nu ^ {*} (H)} {\ nu (H)}} \ równoważnik r-1.}$
Jeśli H jest r -partite (wierzchołki są podzielone na r części, a każda hiperkrawędź zawiera wierzchołek z każdej części), to:
${\ Displaystyle {\ Frac {\ nu ^ {*} (H)} {\ nu (H)}} \ równoważnik r-1.}$

W szczególności na grafie dwudzielnym $ν *(H) = ν (H)$ . Udowodnił to András Gyárfás .
- Nierówność jest ostra: Niech $H r-$ będzie ściętą płaszczyzną rzutową rzędu $r - 1$ . Wtedy $ν (H r -) = 1$ , ponieważ każde dwie hiperkrawędzie się przecinają, a $ν * (H r -) = r - 1$ przez dopasowanie ułamkowe, które przypisuje wagę $1 / r$ każdej hiperkrawędzi (jest $r 2 - r$ hiperkrawędzi ).

Idealne dopasowanie

Dopasowane $M$ jest nazywane doskonałym , jeśli każdy wierzchołek $v$ w $V$ jest zawarty w dokładnie jednej hiperkrawędzi $M$ . Jest to naturalne rozszerzenie pojęcia doskonałego dopasowania w grafie.

Ułamkowe dopasowanie $M$ nazywamy idealnym , jeśli dla każdego wierzchołka $v$ w $V$ suma ułamków hiperkrawędzi w $M$ zawierających $v$ wynosi dokładnie 1.

Rozważmy hipergraf $H$ , w którym każda hiperkrawędź zawiera co najwyżej $n$ wierzchołków. Jeśli $H$ dopuszcza doskonałe dopasowanie ułamkowe, to jego ułamkowa liczba dopasowania wynosi co najmniej $.mw-parser-output .frac{white-space:nowrap}.mw-parser-output .frac .num,.mw-parser-output .frac .den{font-size:80%;line-height:0;vertical-align:super}.mw-parser-output .frac .den{vertical-align:sub}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px} | V | ⁄ rz$ . Jeśli każda hiperkrawędź w $H$ zawiera dokładnie $n$ wierzchołków, to jej ułamkowa liczba pasujących wynosi dokładnie $| V | ⁄ rz$ . Jest to uogólnienie faktu, że na wykresie rozmiar idealnego dopasowania to $| V | ⁄ 2$ .

Biorąc pod uwagę zbiór $V$ wierzchołków, zbiór $E$ podzbiorów $V$ nazywamy zrównoważonym, jeśli hipergraf $(V, E)$ dopuszcza doskonałe dopasowanie ułamkowe.

Na przykład, jeśli $V = {1,2,3,a,b,c}$ i $E = {{1,a}, {2,a}, {1,b}, {2,b}, {3, c} },$ wtedy $E$ jest zrównoważone, z doskonałym dopasowaniem ułamkowym ${ 1/2, 1/2, 1/2, 1/2, 1 }.$

Istnieją różne warunki wystarczające dla istnienia idealnego dopasowania w hipergrafie:

Twierdzenia typu Halla dla hipergrafów - przedstawia warunki dostateczne analogiczne do twierdzenia Halla o małżeństwach, oparte na zbiorach sąsiadów.
Idealne dopasowanie w hipergrafach wysokiego stopnia - przedstawia warunki wystarczające analogiczne do twierdzenia Diraca o cyklach Hamiltona , oparte na stopniu wierzchołków.
Keevash i Mycroft opracowali geometryczną teorię dopasowywania hipergrafów.

Zrównoważona rodzina zestawów

Rodzina zbiorów $E$ nad zbiorem podstawowym $V$ nazywana jest zrównoważoną (względem $V$ ), jeśli hipergraf $H = (V, E)$ dopuszcza doskonałe dopasowanie ułamkowe.

Rozważmy na przykład zbiór wierzchołków $V = {1,2,3,a,b,c}$ i zbiór krawędzi $E = {1-a, 2-a, 1-b, 2-b, 3-c}.$ $E$ jest zrównoważone, ponieważ istnieje idealne dopasowanie ułamkowe o wagach ${1/2, 1/2, 1/2, 1/2, 1}.$

Obliczanie maksymalnego dopasowania

Problem znalezienia dopasowania o maksymalnej liczności w hipergrafie, a tym samym obliczenia $, jest$ dla hipergrafów 3-jednolitych (patrz 3-wymiarowe . Kontrastuje to z przypadkiem prostych (2-jednolitych) grafów, w których obliczenie dopasowania o maksymalnej liczności można wykonać w czasie wielomianowym.

Dopasowanie i pokrycie

wierzchołków w hipergrafie $H = (V, E)$ jest podzbiorem $T$ V , takim że każda hiperkrawędź w $E$ zawiera co najmniej jeden wierzchołek $T$ (nazywany jest również $zbiorem$ poprzecznym lub uderzającym i jest równoważny zestaw okładek ). Jest to uogólnienie pojęcia pokrycia wierzchołków w grafie.

Liczba pokrycia wierzchołków hipergrafu $H$ jest najmniejszym rozmiarem pokrycia wierzchołków w $H$ . Jest często oznaczany przez $τ (H)$ dla poprzecznego.

Ułamkowe pokrycie wierzchołków to funkcja przypisująca wagę każdemu wierzchołkowi w $V$ , tak że dla każdej hiperkrawędzi $e$ w $E$ , suma ułamków wierzchołków w $e$ wynosi co najmniej 1. Pokrycie wierzchołków jest szczególnym przypadkiem wierzchołka ułamkowego pokrycie, w którym wszystkie wagi wynoszą 0 lub 1. Rozmiar ułamkowego pokrycia wierzchołków jest sumą ułamków wszystkich wierzchołków.

Ułamkowa liczba pokrycia wierzchołków hipergrafu $H$ jest najmniejszym rozmiarem ułamkowego pokrycia wierzchołków w $H$ . Często jest oznaczany przez $τ *(H)$ .

Ponieważ pokrycie wierzchołków jest szczególnym przypadkiem ułamkowego pokrycia wierzchołków, dla każdego hipergrafu $H$ :

ułamkowa-liczba-pokrycia-wierzchołków ( $H$ ) ≤ liczba-pokrycia-wierzchołków ( $H$ ).

Dualność programowania liniowego implikuje, że dla każdego hipergrafu $H$ :

ułamkowa-dopasowana-liczba ( $H$ ) = ułamkowa-liczba-pokrycia-wierzchołków( $H$ ).

Stąd dla każdego hipergrafu $H$ :

{\ Displaystyle \ nu (H) \ równoważnik \ nu ^ {*} (H) = \ tau ^ {*} (H) \leq \tau (H)}

Jeśli rozmiar każdej hiperkrawędzi w $H$ wynosi co najwyżej $r$ , to suma wszystkich hiperkrawędzi w maksymalnym dopasowaniu jest wierzchołkiem-pokryciem (gdyby istniała odkryta hiperkrawędź, moglibyśmy dodać ją do dopasowania). Dlatego:

{\ Displaystyle \ tau (H) \ równoważnik r \ cdot \ nu (H).}

Ta nierówność jest ścisła: równość zachodzi, na przykład, gdy $V$ zawiera $r \cdot ν (H) + r - 1$ wierzchołków, a $E$ zawiera wszystkie podzbiory $r$ wierzchołków.

Jednak ogólnie $τ *(H) < r \cdot ν (H)$ , ponieważ $ν * (H) < r \cdot ν (H)$ ; patrz Dopasowanie ułamkowe powyżej.

Hipoteza Rysera mówi, że w każdym hipergrafie $r$ -partite $r$ -uniform:

{\ Displaystyle \ tau (H) \ równoważnik (r-1) \ nu (H).}

Udowodniono niektóre szczególne przypadki przypuszczenia; patrz przypuszczenie Rysera .

własność Kőniga

Hipergraf ma właściwość Kőniga , jeśli jego maksymalna liczba dopasowań jest równa minimalnej liczbie pokrycia wierzchołka, a mianowicie, jeśli $ν (H) = τ (H)$ . Twierdzenie Kőniga -Egerváry'ego pokazuje, że każdy graf dwudzielny ma właściwość Kőniga. Aby rozszerzyć to twierdzenie na hipergrafy, musimy rozszerzyć pojęcie dwudzielności na hipergrafy.

Naturalne uogólnienie jest następujące. Hipergraf nazywamy 2-kolorowym , jeśli jego wierzchołki mogą być 2-kolorowe, tak że każda hipergraf (o rozmiarze co najmniej 2) zawiera co najmniej jeden wierzchołek każdego koloru. Alternatywnym terminem jest Właściwość B . Prosty graf jest dwudzielny, jeśli jest 2-kolorowy. Istnieją jednak 2-kolorowe hipergrafy bez właściwości Kőniga. Weźmy na przykład hipergraf z $V = {1,2,3,4}$ ze wszystkimi trójkami $E = { {1,2,3} , {1,2,4} , {1,3,4} , {2 ,3,4} }.$ Jest dwukolorowy, na przykład możemy pokolorować ${1,2}$ niebieski i ${3,4}$ biały. Jednak jego numer dopasowania to 1, a numer pokrycia wierzchołka to 2.

Silniejsze uogólnienie jest następujące. Biorąc pod uwagę hipergraf $H = (V, E)$ i podzbiór $V'$ z $V$ , ograniczeniem $H$ do $V'$ jest hipergraf, którego wierzchołkami są $V$ , a dla każdej hipergrafu $e$ w $E$ , który przecina $V'$ , ma hiperkrawędź $e'$ , która jest przecięciem $e$ i $V'$ . Hipergraf nazywamy zrównoważonym , jeśli wszystkie jego ograniczenia są dwukolorowe. Graf prosty jest dwudzielny, jeśli jest zrównoważony.

Prosty graf jest dwudzielny, jeśli nie ma cykli o nieparzystej długości. Podobnie hipergraf jest zrównoważony, jeśli nie ma obwodów o nieparzystej długości . Obwód o długości $k$ w hipergrafie jest ciągiem naprzemiennym $(v 1, e 1, v 2, e 2, \dots, v k, e k, v k +1 = v 1)$ , gdzie v $i są$ różnymi wierzchołkami i the $e i$ są odrębnymi hiperkrawędziami, a każda hiperkrawędź zawiera wierzchołek po lewej stronie i wierzchołek po prawej stronie. Obwód nazywamy niezrównoważonym , jeśli każda hiperkrawędź nie zawiera innych wierzchołków w obwodzie. Claude Berge udowodnił, że hipergraf jest zrównoważony wtedy i tylko wtedy, gdy nie zawiera niezrównoważonego obwodu o nieparzystej długości. Każdy zrównoważony hipergraf ma własność Kőniga.

Następujące są równoważne:

Każdy hipergraf częściowy $H$ (tj. hipergraf wyprowadzony z $H$ przez usunięcie niektórych hipergrafów) ma właściwość Kőniga.
Każdy hipergraf cząstkowy $H$ ma tę właściwość, że jego maksymalny stopień jest równy minimalnemu numerowi zabarwienia krawędzi .
$H$ ma właściwość Helly'ego , a graf przecięcia $H$ (prosty graf, w którym wierzchołki to $E$ , a dwa elementy $E$ są połączone wtedy i tylko wtedy, gdy się przecinają) jest grafem doskonałym .

Dopasowywanie i pakowanie

Problem pakowania zestawów jest równoważny dopasowywaniu hipergrafów.

Upakowanie wierzchołków w (prostym) grafie jest podzbiorem $P$ jego wierzchołków, tak że żadne dwa wierzchołki w $P nie$ sąsiadują ze sobą.

Problem znalezienia maksymalnego upakowania wierzchołków w grafie jest równoważny problemowi znalezienia maksymalnego dopasowania w hipergrafie:

Biorąc pod uwagę hipergraf $H = (V, E)$ , zdefiniuj jego graf przecięcia $Int(H)$ jako prosty graf, którego wierzchołkami są $E$ i którego krawędzie są parami $(e 1, e 2)$ takie , że $e 1$ , $e 2$ mają wierzchołek w wspólny. Wtedy każde dopasowanie w $H$ jest pakowaniem wierzchołków w $Int(H)$ i odwrotnie.
Biorąc pod uwagę graf $G = (V', E')$ , zdefiniuj jego hipergraf gwiazdowy $St(G)$ jako hipergraf, którego wierzchołkami są $E'$ i którego hiperkrawędzie są gwiazdami wierzchołków $G$ (tj. dla każdego wierzchołka $v'$ w $V '$ , istnieje hiperkrawędź w $St(G)$ , która zawiera wszystkie krawędzie w $E'$ , które sąsiadują z $v'$ ). Wtedy każde upakowanie wierzchołków w $G$ jest dopasowaniem w $St(G)$ i odwrotnie.
Alternatywnie, biorąc pod uwagę graf $G = (V', E')$ , zdefiniuj jego hipergraf kliki $Cl(G)$ jako hipergraf, którego wierzchołki są $klikami$ G $,$ a dla każdego wierzchołka $v'$ w $V'$ istnieje hipergraf w Cl $(G)$ zawierający wszystkie kliki w $G$ , które zawierają $v'$ . Z drugiej strony każde upakowanie wierzchołków w $G$ jest dopasowaniem $Cl(G)$ i odwrotnie. Zauważ, że $Cl(G)$ nie może być skonstruowany z $G$ w czasie wielomianowym , więc nie może być użyty jako redukcja do udowodnienia NP-twardości. Ale ma pewne zastosowania teoretyczne.

Zobacz też

Dopasowanie trójwymiarowe - szczególny przypadek dopasowania hipergrafu do hipergrafów trójwymiarowych.
Pokrycie wierzchołków w hipergrafach
Hipergraf dwudzielny
Dopasowywanie tęczy w hipergrafach
Hipergraf interwałowy - hipergraf nieskończony, w którym istnieje pewna zależność między dopasowaniem a liczbą pokrywającą.
Twierdzenie Erdősa – Ko – Rado o parach nierozłącznych krawędziach w hipergrafach

^ ^a ^b ^c ^d ^e ^f ^g Lovász, László ; Plummer, MD (1986), Matching Theory , Annals of Discrete Mathematics, tom. 29, Holandia Północna, ISBN 0-444-87916-1 , MR 0859549
^ Berge, Claude (1973). Wykresy i hipergrafy . Amsterdam: Holandia Północna.
^ ^ab ^Aharoni , Ron; 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 .
^ ^a ^b ^c ^d Füredi, Zoltán (1981-06-01). „Maksymalny stopień i dopasowania ułamkowe w jednolitych hipergrafach”. kombinatoryka . 1 (2): 155–162. doi : 10.1007/BF02579271 . ISSN 1439-6912 . S2CID 10530732 .
^ Lovász, L. (1974). Berge, Claude; Ray-Chaudhuri, Dijen (red.). „Twierdzenia Minimax dla hipergrafów”. Seminarium hipergraficzne . Notatki z wykładów z matematyki. Berlin, Heidelberg: Springer. 411 : 111–126. doi : 10.1007/BFb0066186 . ISBN 978-3-540-37803-7 .
^ ^a ^b Nyman, Kathryn; Su, Franciszek Edward; Zerbib, Shira (2020-01-02). „Sprawiedliwy podział z wieloma elementami” . Dyskretna matematyka stosowana . 283 : 115–122. ar Xiv : 1710.09477 . doi : 10.1016/j.dam.2019.12.018 . ISSN 0166-218X . S2CID 119602376 .
Bibliografia _ Mycroft, Richard (2015-01-01). Geometryczna teoria dopasowywania hipergrafów . Wspomnienia Amerykańskiego Towarzystwa Matematycznego. Tom. 233. Amerykańskie Towarzystwo Matematyczne. ISBN 978-1-4704-0965-4 .
^ Berge, CLAUDE (1973-01-01), Srivastava, JAGDISH N. (red.), „ROZDZIAŁ 2 - Zrównoważone hipergrafy i niektóre zastosowania teorii grafów” , A Survey of Combinatorial Theory , North-Holland, s. 15– 23, ISBN 978-0-7204-2262-7 , pobrane 2020-06-19
Bibliografia _ Vergnas, Michel LAS (1970). „Sur Un Twierdzenia Du Type König Pour Hypergraphes”. Roczniki Akademii Nauk w Nowym Jorku . 175 (1): 32–40. doi : 10.1111/j.1749-6632.1970.tb56451.x . ISSN 1749-6632 . S2CID 84670737 .

[lp-1] ^ ^a ^b ^c ^d ^e ^f ^g Lovász, László ; Plummer, MD (1986), Matching Theory , Annals of Discrete Mathematics, tom. 29, Holandia Północna, ISBN 0-444-87916-1 , MR 0859549

[2] Berge, Claude (1973). Wykresy i hipergrafy . Amsterdam: Holandia Północna.

[:1-3] Aharoni , Ron; 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 .

[:2-4] Füredi, Zoltán (1981-06-01). „Maksymalny stopień i dopasowania ułamkowe w jednolitych hipergrafach”. kombinatoryka . 1 (2): 155–162. doi : 10.1007/BF02579271 . ISSN 1439-6912 . S2CID 10530732 .

[5] Lovász, L. (1974). Berge, Claude; Ray-Chaudhuri, Dijen (red.). „Twierdzenia Minimax dla hipergrafów”. Seminarium hipergraficzne . Notatki z wykładów z matematyki. Berlin, Heidelberg: Springer. 411 : 111–126. doi : 10.1007/BFb0066186 . ISBN 978-3-540-37803-7 .

[:0-6] Nyman, Kathryn; Su, Franciszek Edward; Zerbib, Shira (2020-01-02). „Sprawiedliwy podział z wieloma elementami” . Dyskretna matematyka stosowana . 283 : 115–122. ar Xiv : 1710.09477 . doi : 10.1016/j.dam.2019.12.018 . ISSN 0166-218X . S2CID 119602376 .

[7] Bibliografia _ Mycroft, Richard (2015-01-01). Geometryczna teoria dopasowywania hipergrafów . Wspomnienia Amerykańskiego Towarzystwa Matematycznego. Tom. 233. Amerykańskie Towarzystwo Matematyczne. ISBN 978-1-4704-0965-4 .

[8] Berge, CLAUDE (1973-01-01), Srivastava, JAGDISH N. (red.), „ROZDZIAŁ 2 - Zrównoważone hipergrafy i niektóre zastosowania teorii grafów” , A Survey of Combinatorial Theory , North-Holland, s. 15– 23, ISBN 978-0-7204-2262-7 , pobrane 2020-06-19

[9] Bibliografia _ Vergnas, Michel LAS (1970). „Sur Un Twierdzenia Du Type König Pour Hypergraphes”. Roczniki Akademii Nauk w Nowym Jorku . 175 (1): 32–40. doi : 10.1111/j.1749-6632.1970.tb56451.x . ISSN 1749-6632 . S2CID 84670737 .