Zrównoważony hipergraf - Balanced hypergraph

W teorii wykres , A zrównoważony hipergraf jest hipergraf że ma kilka właściwości analogiczne do tego z dwuczęściowego wykresie .

Zrównoważone hipergrafy zostały wprowadzone przez Berge jako naturalne uogólnienie grafów dwudzielnych. Podał dwie równoważne definicje.

Definicja według 2-kolorowalności

Hipergraf H = ( V , E ) jest nazywany dwukolorowym, jeśli jego wierzchołki mogą być dwukolorowe, tak że żadna hiperkrawędź nie jest monochromatyczna. Każdy dwudzielny graf G = ( X + Y , E ) jest 2-kolorowy: każda krawędź zawiera dokładnie jeden wierzchołek X i jeden wierzchołek Y , więc np. X może być pokolorowane na niebiesko, a Y na żółto i żadna krawędź nie jest monochromatyczna.

Hipergraf, w którym niektóre hiperkrawędzie są singletonami (zawierają tylko jeden wierzchołek), oczywiście nie jest dwukolorowy; aby uniknąć takich trywialnych przeszkód dla dwubarwności, powszechnie uważa się hipergrafy, które są zasadniczo dwubarwne , tj. stają się dwubarwne po usunięciu wszystkich swoich pojedynczych hiperkrawędzi.

Hipergraf nazywa się zrównoważonym, jeśli jest zasadniczo dwukolorowy i pozostaje zasadniczo dwukolorowy po usunięciu dowolnej liczby wierzchołków. Formalnie, dla każdego podzbioru U o V , określa ograniczenia z H do U jako hipergraf H _U = ( U , E _U ), gdzie . Wtedy H nazywa się zrównoważonym, jeśli H _U jest zasadniczo dwukolorowe dla każdego podzbioru U z V . Zauważ, że prosty wykres jest dwudzielny, jeśli jest dwukolorowy, jeśli jest zrównoważony. ${\ Displaystyle E_ {U} = \ {e \ czapka U | e \ w E \}}$

Definicja według nieparzystych cykli

Cyklu (lub obwód ) w hipergraf jest sekwencja cykliczna przemienne różnych wierzchołków i hyperedges: ( v ₁ , E, ₁ , V, ₂ , E, ₂ , ..., v _k , e _k , v _{k +1} = v ₁ ), gdzie każdy wierzchołek v _i jest zawarty zarówno w e _{i -1 jak} i e _i . Liczba k nazywana jest długością cyklu.

Hipergraf jest zrównoważony, jeśli każdy cykl o nieparzystej długości C w H ma krawędź zawierającą co najmniej trzy wierzchołki C .

Zauważ, że w prostym grafie wszystkie krawędzie zawierają tylko dwa wierzchołki. Stąd prosty wykres jest zrównoważony, jeśli w ogóle nie zawiera cykli o nieparzystej długości, co oznacza, że ​​jest dwuczęściowy.

Berge udowodnił, że obie definicje są równoważne; dowód jest również dostępny tutaj.

Nieruchomości

Niektóre twierdzenia dotyczące grafów dwudzielnych zostały uogólnione na hipergrafy zrównoważone.

• W każdym zrównoważonym hipergrafie minimalne pokrycie wierzchołków ma taki sam rozmiar jak maksymalne dopasowanie . To uogólnia twierdzenie Kőniga-Egervary'ego na grafach dwudzielnych.
• W każdym zrównoważonym hipergrafie stopień (= maksymalna liczba hiperkrawędzi zawierających jeden wierzchołek) jest równy indeksowi chromatycznemu (= najmniejsza liczba kolorów wymagana do pokolorowania hiperkrawędzi w taki sposób, że żadne dwa hiperkrawędzie o tym samym kolorze nie mają wspólnego wierzchołka) . To uogólnia twierdzenie Konig na grafach dwudzielnych.
• Każdy zrównoważony hipergraf spełnia uogólnienie twierdzenia Halla o małżeństwie : dopuszcza idealne dopasowanie iff dla wszystkich rozłącznych zbiorów wierzchołków V ₁ , V ₂ , jeśli dla wszystkich krawędzi e w E , to | V ₂ | ≥ | V ₁ |. Zobacz twierdzenia typu Halla dla hipergrafów .${\ Displaystyle | e \ cap V_ {2} | \ geq | e \ cap V_ {1} |}$
• Każdy zrównoważony hipergraf z maksymalnym stopniem D , może być podzielony na D dopasowań rozłącznych na krawędziach.

K -krotnie poprzeczny zrównoważonej hipergraf można wyrazić jako związek K kąty naprzemianległe parami-rozłącznych i taka przegroda może być uzyskane w czasie wielomianowym.

Porównanie z innymi pojęciami dwustronności

Oprócz równowagi istnieją alternatywne uogólnienia grafów dwudzielnych. Hipergraf nazywa się dwudzielnym, jeśli jego zbiór wierzchołków V można podzielić na dwa zbiory, X i Y , tak że każdy hiperkrawędź zawiera dokładnie jeden element X (patrz hipergraf dwudzielny ). Oczywiście każdy wykres dwudzielny jest dwukolorowy.

Właściwości dwudzielności i równowagi nie implikują się nawzajem.

Równowaga nie oznacza dwustronności . Niech H będzie hipergrafem:

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

jest dwukolorowy i pozostaje dwukolorowy po usunięciu z niego dowolnej liczby wierzchołków. Nie jest to jednak dwudzielność, ponieważ aby mieć dokładnie jeden zielony wierzchołek w każdym z pierwszych dwóch hiperkrawędzi, musimy mieć dwa zielone wierzchołki w ostatnim hiperkrawędzi. 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 przez podział 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 dwukolorowa, ponieważ w każdym dwukolorowaniu występują 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 .

Trójstronność nie oznacza równowagi . Na przykład niech H będzie hipergrafem trójdzielnym z wierzchołkami {1,2},{3,4},{5,6} i krawędziami:

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

Nie jest zrównoważony, ponieważ jeśli usuniemy wierzchołki 2,3,6, reszta to:

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

który nie nadaje się do barwienia, ponieważ jest to cykl 3-cyklowy.

Innym sposobem, aby zobaczyć, że nie jest zrównoważony, jest to, że zawiera cykl o nieparzystej długości C = (1 - {1,3,5} - 5 - {2,4,5} - 4 - {1,4,6} - 1), a żadna krawędź C nie zawiera wszystkich trzech wierzchołków 1,4,5 C .

Powiązane właściwości

Całkowicie zrównoważone hipergrafy

Hipergraf nazywa się całkowicie zrównoważonym, jeśli każdy cykl C w H o długości co najmniej 3 (niekoniecznie nieparzystej) ma krawędź zawierającą co najmniej trzy wierzchołki C .

Hipergraf H jest całkowicie zrównoważony, jeśli każdy podhipergraf H jest hipergrafem drzewa.

Hipergrafy normalne

Właściwość Konig z hipergraf H jest właściwość, że jego minimalna wierzchołek, pokrywa ma taki sam rozmiar jak maksymalnego dopasowania . König-Egervary twierdzenie mówi, że wszystkie graf dwudzielny mają właściwość Konig.

Symetryczne hipergrafów są dokładnie H hipergrafów takie, że każdy częściowy subhypergraph z H ma tę właściwość Konig (czyli H ma tę właściwość Konig nawet po usunięciu wszelkich liczbę hyperedges i wierzchołków).

Jeśli każdy częściowy hipergraf H ma własność Konig (tj. H ma własność Konig nawet po usunięciu dowolnej liczby hiperkrawędzi — ale nie wierzchołków), wówczas H nazywamy hipergrafem normalnym .

Zatem całkowicie zrównoważony oznacza zrównoważony, co oznacza normalność.

Bibliografia