Hall-tétel

• IPA:

Hall-tétel

1. (matematika, kombinatorika) A Hall-tétel egy kombinatorikai állítás, ami feltételt ad arra, hogy mikor lehet kiválasztani egy adott halmaz valahány nem feltétlenül diszjunkt részhalmazából különböző elemeket.

A Hall-tétel egy alapvető eredmény a kombinatorikus gráfelméletben, amely a bipartit gráfokhoz kapcsolódik. A tétel kimondja, hogy egy bipartit gráfban létezik tökéletes illeszkedés, ha és csak ha minden részhalmaz az egyik részhalmaznak legalább annyi szomszédot tartalmaz, mint ahány elem van benne.

Hall-tétel: Egy bipartit gráfban létezik tökéletes illeszkedés, ha és csak ha minden ${\displaystyle S\subseteq U}$ részhalmazra: $${\displaystyle |N(S)|\geq |S|}$$ ahol ${\displaystyle N(S)}$ az ${\displaystyle S}$-tól elérhető csúcsok halmaza a ${\displaystyle V}$-ban, és ${\displaystyle |N(S)|}$ az ezeknek a csúcsoknak a száma.

- A bipartit gráf olyan gráf, amelynek csúcsai két diszjunkt halmazra oszthatók, úgy hogy minden él egy csúcsból az egyik halmazból és egy csúcsból a másik halmazból indul ki. Nincsenek élek, amelyek két csúcsot ugyanabból a halmazból kapcsolnak össze.

- A tökéletes illeszkedés egy olyan illeszkedés, amely minden csúcsot tartalmaz a gráfban. Más szóval, minden csúcs egy másik csúcshoz van kapcsolva, és nincs csúcs, amely ne lenne része az illeszkedésnek.

- A részhalmaz egy halmaz olyan elemeinek gyűjteménye, amelyek az eredeti halmaz részei. A szomszédság azt jelenti, hogy két csúcs között él van, tehát egy csúcs elérhetősége más csúcsokból származik.

A Hall-tétel bizonyítása indukcióval történik. Az alábbiakban a bizonyítás lépéseit ismertetem:

- Tekintsük a bipartit gráfot ${\displaystyle G=(U,V,E)}$, ahol ${\displaystyle |U|=n}$ és ${\displaystyle |V|=m}$. - A cél annak bizonyítása, hogy létezik tökéletes illeszkedés, ha és csak ha minden részhalmaz ${\displaystyle S\subseteq U}$-ra igaz, hogy ${\displaystyle |N(S)|\geq |S|}$.

- Ha a fenti feltétel teljesül, akkor építsünk fel egy illeszkedést lépésről lépésre. Először bemutatjuk, hogy a tétel igaz egy kis értékre, például ${\displaystyle n=1}$. Ezután az indukciós lépést alkalmazva kimutatjuk, hogy a tétel igaz nagyobb értékekre is.

- Ha nincs tökéletes illeszkedés, akkor létezik olyan ${\displaystyle S\subseteq U}$ részhalmaz, amelynek ${\displaystyle |N(S)|<|S|}$, ami ellentmondásba kerül a Hall-tétel feltételével.

- A bizonyítás így azt mutatja, hogy a Hall-tétel érvényes, ha és csak ha minden részhalmazra ${\displaystyle S\subseteq U}$ teljesül a fenti feltétel.

Tekintsünk egy egyszerű bipartit gráfot, ahol ${\displaystyle U=\{u_{1},u_{2}\}}$ és ${\displaystyle V=\{v_{1},v_{2},v_{3}\}}$, és az élek a következőképpen vannak: ${\displaystyle \{(u_{1},v_{1}),(u_{1},v_{2}),(u_{2},v_{2}),(u_{2},v_{3})\}}$.

A Hall-tétel szerint a részhalmazokra: - ${\displaystyle S=\{u_{1}\}}$ esetén ${\displaystyle N(S)=\{v_{1},v_{2}\}}$, tehát ${\displaystyle |N(S)|=2\geq 1}$, - ${\displaystyle S=\{u_{2}\}}$ esetén ${\displaystyle N(S)=\{v_{2},v_{3}\}}$, tehát ${\displaystyle |N(S)|=2\geq 1}$, - ${\displaystyle S=\{u_{1},u_{2}\}}$ esetén ${\displaystyle N(S)=\{v_{1},v_{2},v_{3}\}}$, tehát ${\displaystyle |N(S)|=3\geq 2}$.

Mivel minden részhalmazra teljesül a Hall-tétel feltétele, a gráfban létezik tökéletes illeszkedés.

A Hall-tétel egy egyszerű alkalmazása a bipartit gráfoknak. Az alábbi Python kód a NetworkX könyvtárat használja a bipartit gráfok és azok illeszkedéseinek vizsgálatára:

import networkx as nx

# Gráf létrehozása
G = nx.Graph()

# Csúcsok és élek hozzáadása
U = 
V = 
edges = 

G.add_nodes_from(U + V)
G.add_edges_from(edges)

# Ellenőrzés, hogy van-e tökéletes illeszkedés
def is_perfect_matching(G, U, V):
    # A bipartit gráf illeszkedésének vizsgálata
    matching = nx.bipartite.maximum_matching(G)
    
    # Ha az illeszkedés tartalmazza az összes csúcsot
    return len(matching) == 2 * len(U)

# Tökéletes illeszkedés ellenőrzése
if is_perfect_matching(G, U, V):
    print("A gráfban létezik tökéletes illeszkedés!")
else:
    print("A gráfban nincs tökéletes illeszkedés!")

A gráfban létezik tökéletes illeszkedés!

Ebben a példában a Python kód a bipartit gráf maximum illeszkedését vizsgálja, és megtalálja, hogy létezik tökéletes illeszkedés, mivel minden részhalmazra teljesül a Hall-tétel feltétele.

1. Gráfelméleti alkalmazások:

  - A Hall-tétel alapvető fontosságú a bipartit gráfok és a maximális illeszkedések területén, például a munkaerőpiaci párosítások vagy feladat-alkalmazott párosítások problémáinál.

1. Algoritmusok:

  - A Hall-tétel felhasználható olyan algoritmusokban, amelyek bipartit gráfokban keresnek illeszkedéseket, például a maximum bipartite matching algoritmusokban.

1. Alkalmazások a közlekedésben és gazdaságban:

  - A tétel segíthet a közlekedési hálózatok optimalizálásában vagy a gazdasági párosítások (például kereslet-kínálat) modellezésében.

A Hall-tétel alapvető eredmény a gráfelméletben, amely a bipartit gráfok tökéletes illeszkedését vizsgálja. A tétel azt mondja ki, hogy egy bipartit gráfban akkor és csak akkor létezik tökéletes illeszkedés, ha minden részhalmazra teljesül a Hall-tétel feltétele. A tétel alkalmazásai széleskörűek a kombinatorikai számelméletben és más területeken, mint a közlekedés, gazdaság és munkaerőpiaci problémák.

• Hall-tétel - Értelmező szótár (MEK)
• Hall-tétel - Etimológiai szótár (UMIL)
• Hall-tétel - Szótár.net (hu-hu)
• Hall-tétel - DeepL (hu-de)
• Hall-tétel - Яндекс (hu-ru)
• Hall-tétel - Google (hu-en)
• Hall-tétel - Helyesírási szótár (MTA)
• Hall-tétel - Wikidata
• Hall-tétel - Wikipédia (magyar)