Hypergraph
W hipergrafów są obiektami matematyka uogólniając koncepcji wykresu . Nazwali je tak Claude Berge w latach sześćdziesiątych XX wieku.
Hipergrafy uogólniają pojęcie grafu nieukierunkowanego w tym sensie, że krawędzie nie łączą już jednego lub dwóch wierzchołków, ale dowolną liczbę wierzchołków (zawartą między jednym a liczbą wierzchołków hipergrafu).
Niektóre twierdzenia teorii grafów są naturalnie uogólniane na hipergrafy, na przykład twierdzenie Ramseya .
Hipergrafy są obsługiwane we wszystkich obszarach, w których stosowana jest teoria grafów: rozwiązywanie problemów związanych ze spełnieniem ograniczeń , przetwarzanie obrazu, optymalizacja architektur sieci, modelowanie itp.
Definicje
Hypergraph
Hipergraf jest para , która jest ustawiona niepusty (zwykle ograniczony) i jest rodzina z części nie jest pusta .
H.{\ displaystyle H}(V,mi){\ displaystyle (V, E)}V={v1,v2,...,vnie}{\ Displaystyle V = \ {v_ {1}, v_ {2}, ..., v_ {n} \}}mi=mi1,mi2,...,mim{\ Displaystyle E = E_ {1}, E_ {2}, ..., E_ {m.}}V{\ displaystyle V}
Podobnie jak w przypadku wykresów, mówimy, że:
- Elementy są wierzchołki z .V{\ displaystyle V}H.{\ displaystyle H}
- Liczba wierzchołków to kolejność hipergrafu.nie{\ displaystyle n}
- Te elementy są krawędziami o .mi{\ displaystyle E}H.{\ displaystyle H}
Hipergrafy odpowiadają dokładnie macierzom o współczynnikach 0 lub 1 (z których każda kolumna ma co najmniej 1). Rzeczywiście, każdy hipergrraf jednoznacznie odpowiada macierzy, takiej jak:
H.{\ displaystyle H}Wnie,m{\ Displaystyle {\ mathcal {A}} _ {n, m} \,}
∀wja,jot∈W,wja,jot={1gdyby vja∈mijot0Jeśli nie{\ displaystyle \ forall a_ {i, j} \ in {\ mathcal {A}}, \ quad a_ {i, j} = {\ rozpocząć {przypadki} 1 i {\ text {si}} ~ v_ {i} \ in E_ {j} \\ 0 & {\ text {inaczej}} \ end {cases}}}
Jednolity hipergraph
Wśród „nowych” właściwości hipergrafów w odniesieniu do grafów są dwa powiązane pojęcia.
- Rangę hipergrafu nazywamy maksymalną liczbą wierzchołków krawędzi:ranga(H.)=maxja∈{1,...,m}|mija|{\ displaystyle \ operatorname {zadzwonił} (H) = \ max _ {i \ in \ {1, \ ldots, m \}} | E_ {i} |}Ranga hipergrafu jest zwiększana o jego kolejność. Jeśli , to jest wykresem .rwniesol(H.)=2{\ Displaystyle \ mathrm {ranga} (H) = 2}H.{\ displaystyle H}
- Minimalną liczbę wierzchołków krawędzi nazywamy anty-rangą hipergrafu: wnietja-rwniesol(H.)=minja∈{1,...,m}|mija|{\ displaystyle \ operatorname {anty-rank} (H) = \ min _ {i \ in \ {1, \ ldots, m \}} | E_ {i} |}
Z definicji hipergrafu, krawędzie są niepustymi częściami zbioru wierzchołków hipergrafu. W związku z tym antyranga hipergrafu jest różna od zera.
Mówi się, że hipergraf jest jednolity, gdy jego ranga i antyranga są równe.
Mówimy również o r-uniform hypergraph, aby wskazać jednolity hipergraph rangi .
r{\ displaystyle r}
Przykład: hipergraf płaszczyzny Fano
Hipergraf płaszczyzny Fano ma siedem wierzchołków zwanych punktami {0,1,2,3,4,5,6} i siedem krawędzi zwanych liniami prostymi (013, 045, 026, 124, 346, 325, 516). Kolejność (liczba wierzchołków) to 7.
Rząd i antyrząd są równe 3 (liczbie wierzchołków krawędzi). Dlatego hipergrraf płaszczyzny Fano jest hipergrrafem w trzech jednostkach.
Częściowy hipergrraf i pod-hipergraf
Podobnie jak w przypadku wykresów, mówimy, że:
- Częściowy hipergraf hipergrafu jest taki, że:H.p=(V,mip){\ Displaystyle H_ {p} = (V, E_ {p})}H.=(V,mi){\ Displaystyle H = (V, E)}
mip⊂mi{\ Displaystyle E_ {p} \ podzbiór E}.
- Podhiperaf hipergrafu jest taki, że:
H.′=(V′,mi′){\ Displaystyle H '= (V', E ')}H.=(V,mi){\ Displaystyle H = (V, E)}
-
V′⊆V{\ Displaystyle V '\ subseteq V} i
-
∀mija∈mi′,mija⊆V′∧mija∈mi{\ displaystyle \ forall E_ {i} \ in E ', \ quad E_ {i} \ subseteq V' \ land E_ {i} \ in E}.
Pojęcia te uogólniają pojęcia grafu cząstkowego i podgrafu na teorię hipergrafów.
Prosty hipergraph
Podobnie jak (niezorientowane) wykresy, mówimy, że hipergraf jest prosty, jeśli nie ma wielu krawędzi (patrz artykuł: prosty wykres ).
Nazywamy rodzinę Spernera (lub po angielsku bałagan ) prostym hipergrafem, którego żadna krawędź nie jest zawarta w innym.
Podwójny hipergraph
Albo takie, że .
V∗={Vjot∣jot=1,2,...,|V|}{\ Displaystyle V ^ {*} = \ {V_ {j} \ mid j = 1,2, \ ldots, | V | \}}Vjot={mija∣(mija∈mi)∧(vjot∈mija)}{\ Displaystyle V_ {j} = \ {E_ {i} \ mid (E_ {i} \ in E) \ wedge (v_ {j} \ in E_ {i}) \}}
Następnie hipergraf zdefiniowane przez nazywa się podwójną hipergraf się . Odpowiada transpozycji macierzy. Pojęcie to nie pokrywa się z pojęciem wykresu podwójnego , nawet w przypadku, gdy hipergraf okazuje się wykresem.
H.∗=(mi,V∗){\ Displaystyle H ^ {*} = (E, V ^ {*})}H.{\ displaystyle H}
Przykłady:
-
({1,2},{1,3},{2,3}){\ Displaystyle (\ {1,2 \}, \ {1,3 \}, \ {2,3 \})}jest zarówno autodual, jak i autotransversal .
-
({1,2,3},{1,4,5},{1,6,7},{2,4,6},{2,5,7},{3,4,7},{3,5,6}){\ Displaystyle (\ {1,2,3 \}, \ {1,4,5 \}, \ {1,6,7 \}, \ {2,4,6 \}, \ {2,5, 7 \}, \ {3,4,7 \}, \ {3,5,6 \})}jest płaszczyzną rzutową , autotranswersalną, jednorodną, regularną i autodualną.
Hypergraph, odzyskiwanie, partycja
Zbiór krawędzi hipergrafu niekoniecznie nakłada się , ponieważ wierzchołek może mieć zero stopni, to znaczy nie może być połączony żadną krawędzią; w tym przypadku połączenie krawędzi nie obejmuje wszystkich wierzchołków. Na przykład w hipergrafie takim, że i , wierzchołek ma zero stopni; nie pojawia się w żadnym z podzbiorów programu , zapobiega to, że jest on nakładką. Zbiór krawędzi hipergrafu nakłada się na siebie tylko wtedy, gdy każdy wierzchołek ma co najmniej stopień 1.
V={v1,v2,v3,v4,v5,v6,v7}{\ displaystyle V = \ {v_ {1}, v_ {2}, v_ {3}, v_ {4}, v_ {5}, v_ {6}, v_ {7} \}}mi={mi1,mi2,mi3,mi4}={{v1,v2,v3},{v2,v3},{v3,v5,v6},{v4}}{\ Displaystyle E = \ {e_ {1}, e_ {2}, e_ {3}, e_ {4} \} = \ {\ {v_ {1}, v_ {2}, v_ {3} \}, \ {v_ {2}, v_ {3} \}, \ {v_ {3}, v_ {5}, v_ {6} \}, \ {v_ {4} \} \}}v7{\ displaystyle v_ {7}}mija{\ displaystyle e_ {i}}mi{\ displaystyle E}mi{\ displaystyle E}
W rezultacie istnieje podział, jeśli zestaw krawędzi zachodzi na siebie i żaden wierzchołek nie jest połączony dwoma krawędziami, tj. Jeśli którykolwiek wierzchołek ma dokładnie stopień 1.
Zobacz też
Uwagi i odniesienia
-
Claude Berge , Graphs et Hypergraphes , Dunod, Collection Monograph Universitaires de Mathématiques nr 37, styczeń 1970.
-
Claude Berge , Hypergraphs. Kombinatoryka zbiorów skończonych , Gauthier-Villars, 1987 ( ISBN 2-04-016906-7 ) .
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">