Wikiszótár

Kőnig-tétel

(Kőnig Dénes tétele szócikkből átirányítva)

Magyar

Kiejtés

  • IPA: [ ˈkøːnikteːtɛl]

Főnév

Kőnig-tétel

  1. (matematika, gráfelmélet) A Kőnig-tétel a gráfelméletben egy páros gráf maximális párosítása és a minimális lefogó ponthalmaza közötti ekvivalenciát mondja ki. A tétel Kőnig Dénestől származik. Legyen   egy páros gráf. Ekkor a tétel szerint   (azaz a legnagyobb független élhalmaznak ugyanannyi eleme van, mint a legkisebb lefogó ponthalmaznak), és ha G-ben nincs izolált pont, akkor   (azaz a legkisebb lefogó élhalmaz azonos méretű a legnagyobb független ponthalmazzal).

Kőnig-tétel

Definíció

A **Kőnig-tétel** egy alapvető eredmény a gráfelméletben, amely bipartit gráfokra vonatkozik. A tétel kimondja:

> Egy bipartit gráfban a maximális élborítás mérete megegyezik a minimális csúcspár-foglalat méretével.

Fogalmak

Bipartit gráf

- Egy gráf akkor bipartit, ha csúcsai két diszjunkt halmazra (\(U\) és \(V\)) oszthatók, úgy hogy minden él két különböző halmazba tartozó csúcsot köt össze.

Élborítás

- Egy élhalmaz \(M\) élborítás, ha a gráf minden élének legalább egyik végpontja benne van egy élben \(M\)-ből. - A maximális élborítás a gráfban található legtöbb élből álló élborítás.

Csúcspár-foglalat

- Egy csúcshalmaz \(C\) csúcspár-foglalat, ha \(C\)-ben szereplő csúcsok eltávolításával a gráf minden élét eltávolítjuk. - A minimális csúcspár-foglalat a gráf legkisebb ilyen csúcshalmaza.

Tétel Bizonyítása

Állítás

- Jelölje a maximális élborítás méretét \( |M| \). - Jelölje a minimális csúcspár-foglalat méretét \( |C| \). - A tétel állítása: \( |M| = |C| \).

Érvelés

  1. A maximális élborítás (\(M\)) maximalizálja az egymást nem metsző élek számát.
  2. A minimális csúcspár-foglalat (\(C\)) tartalmazza az összes él lefedéséhez szükséges legkisebb számú csúcsot.
  3. A hálózatáramlás és az **áram-vágás tétel** segítségével bizonyítható, hogy:
  * A maximális párosítás (\( |M| \)) mérete megegyezik a minimális vágás méretével.
  * A minimális csúcspár-foglalat (\( |C| \)) szintén megegyezik a minimális vágás méretével.
  1. Következésképpen \( |M| = |C| \).

Példa

Egy bipartit gráf: \[ U = \{u_1, u_2, u_3\}, \quad V = \{v_1, v_2, v_3\}, \quad E = \{(u_1, v_1), (u_1, v_2), (u_2, v_2), (u_3, v_3)\}. \]

Maximális párosítás

- \(M = \{(u_1, v_1), (u_2, v_2), (u_3, v_3)\}\), tehát \( |M| = 3 \).

Minimális csúcspár-foglalat

- \(C = \{u_1, u_2, u_3\}\), vagy alternatív módon \(C = \{v_1, v_2, v_3\}\), tehát \( |C| = 3 \).

Eredmény: \( |M| = |C| = 3 \).

Python Implementáció

import networkx as nx

def maximal_matching_and_min_vertex_cover(graph):
    """
    Meghatározza a maximális párosítást és minimális csúcspár-foglalatot bipartit gráfban.
    
    Args:
        graph: A NetworkX bipartit gráf.
    
    Returns:
        tuple: A maximális párosítás és a minimális csúcspár-foglalat.
    """
    # Maximális párosítás
    matching = nx.bipartite.maximum_matching(graph)
    matching = {k: v for k, v in matching.items() if k in graph.nodes}

    # Minimális csúcspár-foglalat
    vertex_cover = nx.bipartite.minimum_node_cover(graph)

    return matching, vertex_cover

# Példa gráf
B = nx.Graph()
B.add_nodes_from(["u1", "u2", "u3"], bipartite=0)
B.add_nodes_from(["v1", "v2", "v3"], bipartite=1)
B.add_edges_from([("u1", "v1"), ("u1", "v2"), ("u2", "v2"), ("u3", "v3")])

matching, vertex_cover = maximal_matching_and_min_vertex_cover(B)
print("Maximális párosítás:", matching)
print("Minimális csúcspár-foglalat:", vertex_cover)
print("Kőnig-tétel igaz:", len(matching) == len(vertex_cover))

C++ Implementáció Boost Graph Library segítségével

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/bipartite.hpp>
#include <boost/graph/max_cardinality_matching.hpp>

using namespace boost;
using namespace std;

int main() {
    typedef adjacency_list<vecS, vecS, undirectedS> Graph;

    // Bipartit gráf létrehozása
    Graph G(6);
    add_edge(0, 3, G);
    add_edge(0, 4, G);
    add_edge(1, 4, G);
    add_edge(2, 5, G);

    // Párosítás meghatározása
    vector<graph_traits<Graph>::vertex_descriptor> mate(num_vertices(G));
    bool success = checked_edmonds_maximum_cardinality_matching(G, &mate[0]);

    if (success) {
        cout << "Maximális párosítás:" << endl;
        for (size_t i = 0; i < mate.size(); ++i) {
            if (i < mate[i]) {
                cout << i << " - " << mate[i] << endl;
            }
        }
    } else {
        cout << "Nem található érvényes párosítás." << endl;
    }

    return 0;
}

Alkalmazások

  1. Ütemezési problémák: Munkások és feladatok hozzárendelése.
  2. Közlekedési hálózatok: Járművek és célállomások optimalizált párosítása.
  3. Adatbázisok: Adatok kapcsolódásainak optimalizálása bipartit struktúrákban.

Összegzés

A **Kőnig-tétel** egy fontos eredmény a bipartit gráfok elméletében, amely lehetővé teszi a maximális élborítás és minimális csúcspár-foglalat közötti kapcsolat megértését. Gyakorlati alkalmazása széles körben elterjedt az optimalizálási problémákban, például ütemezésben és hálózatok kezelésében. Python és C++ segítségével a tétel gyakorlati ellenőrzése és alkalmazása egyszerűen megvalósítható.

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Kőnig-tétel&oldid=3479875”