Šířka hypergrafu - Width of a hypergraph

v teorie grafů, existují dvě související vlastnosti a hypergraf které se nazývají jeho „šířka“. Dostal hypergraf H = (PROTI, E), říkáme, že množina K. hran kolíky další sada F hran, pokud jsou všechny hrany dovnitř F protíná nějakou hranu dovnitř K..^[1] Pak:

• The šířka z H, označeno w (H), je nejmenší velikost podmnožiny E to kolíky E.^[2]
• The odpovídající šířka z H, označeno mw (H), je maximum, ve všech párování M v H, podmnožiny E to kolíky M.^[3]

Od té doby E obsahuje všechny shody v E, pro všechny H: w (H) ≥ mw (H).

Šířka hypergrafu se používá v Hallovy věty pro hypergrafy.

Příklady

Nechat H být hypergrafem se sadou vrcholů V = {A, B; a, b} a sada hran:

E = {{A, a}, {B, b}, {A, b}, {B, a}}

Šířky H jsou:

• w (H) = 2, protože E je připnut množinou {{A, a}, {B, b}} a nelze ji připnout žádnou menší sadou.
• mw (H) = 1, protože každou shodu lze připnout jednou hranou. Existují dvě shody: {{A, a}, {B, b}} je připnutý např. od {{A, b}} a {{A, b}, {B, a}} je připnuto např. autor: {{A, a}}.

Charakterizace

The graf disjunktnosti z H, označeno D (H), je graf, kde každá hrana v H je vrchol v D (H) a každé dva nesouvislé okraje v H sousedí v D (H). The párování v H odpovídají kliky v D (H). Meshulam^[2] charakterizoval šířky hypergrafu H z hlediska vlastností D (H). Pro jakékoli kladné celé číslo r:

• w (H) > r právě když D (H) splňuje vlastnost zvanou P (r, ∞), což znamená, že každá sada r vrcholy v D (H) mají společného souseda. Je to proto, že w (H) > r iff H nemá žádnou připínací sadu velikosti r, iff pro každou podmnožinu r okraje H tam je hrana, která není připnutá, pokud každá podmnožina r okraje H má společného souseda v D (H).
• mw (H) > r právě když D (H) splňuje vlastnost zvanou P (r, 0), což znamená, že každá sada r vrcholy v D (H) mají společného souseda a navíc je zde klika C v D (H), který obsahuje společného souseda každé takové sady.

The hranový graf z H, označeno L (H), je graf, kde každá hrana v H je vrchol v L (H) a každé dva protínající se okraje v H sousedí v L (H). Odpovídání v H odpovídá nezávislé sady v L (H). Od L (H) je doplňkem D (H), výše uvedená charakteristika může být přeložena do L (H):

• w (H) > r právě když pro každou sadu r vrcholy v L (H) tam je vrchol nesousedící s žádným z nich.
• mw (H) > r právě když pro každou sadu r vrcholy v L (H) existuje vrchol, který nesousedí s žádným z nich, a navíc existuje nezávislá množina Já v L (H) který obsahuje vrchol nesousedící s žádnou takovou množinou.

The dominantní číslo grafu G, označeno y(G), je nejmenší velikost množiny vrcholů, která dominuje všem vrcholům G. Šířka hypergrafu se rovná číslu dominance nebo jeho spojnicovému grafu: w (H) = y(L (H)). Je to proto, že okraje E jsou vrcholy L (H): každá podmnožina E to kolíky E v H odpovídá vrcholu nastavenému v L (H) který dominuje všem L (H).

The číslo dominance nezávislosti grafu G, označeno iγ(G), je maximum, ve všech nezávislé sady A z G, dominující nejmenší množina A.^[4] Odpovídající šířka hypergrafu se rovná číslu dominance nezávislosti nebo jeho spojnicovému grafu: mw (H) = iγ(L (H)). Je to proto, že každá shoda M v H odpovídá nezávislé sadě Já_M v L (H) a každá podskupina E to kolíky M v H odpovídá množině, která dominuje Já_M v L (H).

Viz také

• Další pojmy, které se v teorii grafů nazývají „šířka“, viz Šířka (disambiguation) #Graph theory.

Reference