Erdős-Pósa-tétel

• IPA:

Erdős-Pósa-tétel (matematika, gráfelmélet) Az Erdős-Pósa-tétel kimondja, hogy létezik egy f(k) függvény, hogy minden k pozitív egész számra minden gráf vagy tartalmaz k csúcsdiszjunkt kört, vagy f(k) méretű körlefogó csúcshalmazt, ami a gráf minden köréből tartalmaz csúcsot.

Az **Erdős–Pósa-tétel** egy alapvető állítás a kombinatorikus gráfelméletben, amely kapcsolatot teremt a gráfban található páronként diszjunkt körök száma és egy minimális csúcspár-foglalat mérete között. A tétel kimondja:

> Egy gráfban vagy található ${\displaystyle k}$ páronként diszjunkt kör, vagy van egy legfeljebb ${\displaystyle c\cdot k\cdot \log(k)}$ méretű csúcshalmaz, amely lefedi az összes kört.

Itt ${\displaystyle c}$ egy konstans, amely a gráftól függ.

- Egy kör egy olyan zárt út, amelyben minden él és csúcs csak egyszer szerepel.

- A körök diszjunktak, ha nincs közös csúcsuk.

- Egy csúcshalmaz, amelynek eltávolításával a gráfból az összes kör megszűnik.

1. Két lehetőség a gráfban:

  - ${\displaystyle k}$ páronként diszjunkt kör létezik.
  - Egy ${\displaystyle S}$ csúcshalmaz eltávolításával az összes kör megszűnik, és ${\displaystyle |S|\leq c\cdot k\cdot \log(k)}$.

1. Kapcsolat a gráf tulajdonságai között:

  - A tétel egyensúlyt teremt a diszjunkt körök száma és a lefedéshez szükséges minimális csúcshalmaz mérete között.

- Kontrahálások és szétszakítások:

  - Egy gráf kontrahálásával (élek összevonásával) és csúcsok eltávolításával csökkenthető a bonyolultság.

- Diszjunkt körök keresése:

  - Az ${\displaystyle k}$-diszjunkt körök megtalálása iteratív algoritmusokkal lehetséges.

- Ha ${\displaystyle k}$ diszjunkt kör nem található, akkor létezik egy lefedő csúcshalmaz. - A csúcshalmaz méretét a gráf struktúrája és a tételben szereplő ${\displaystyle c}$ konstans határozza meg.

- A lefedésre szánt csúcshalmaz iteratív módon konstruálható:

 - Minden lépésben eltávolítjuk az aktuális körhöz tartozó csúcsokat.
 - Ez biztosítja, hogy a fennmaradó gráfban ne legyenek körök.

- Az ${\displaystyle k}$-diszjunkt kör vagy lefedő csúcshalmaz mindig létezik. - A lefedés mérete a gráf tulajdonságaitól függően ${\displaystyle c\cdot k\cdot \log(k)}$-nél nem lehet nagyobb.

Egy egyszerű gráf: ${\displaystyle V=\{A,B,C,D,E\},\quad E=\{(A,B),(B,C),(C,D),(D,E),(E,A),(B,D)\}.}$

1. Találjunk ${\displaystyle k}$-diszjunkt köröket:

  - ${\displaystyle \{A,B,C,A\}}$ és ${\displaystyle \{C,D,E,C\}}$ két diszjunkt kör.

1. Lefedő csúcshalmaz:

  - ${\displaystyle S=\{B,C,D\}}$ lefedi mindkét kört.

- ${\displaystyle k=2}$ diszjunkt kör található. - A lefedő halmaz ${\displaystyle |S|=3}$, amely kielégíti a tétel feltételeit.

import networkx as nx

def find_disjoint_cycles(graph, k):
    """
    Diszjunkt köröket keres a gráfban.

    Args:
        graph: A NetworkX gráf objektuma.
        k: A keresett diszjunkt körök száma.

    Returns:
        list: A talált diszjunkt körök listája.
    """
    cycles = 
    for cycle in nx.simple_cycles(graph):
        if all(set(cycle).isdisjoint(set(c)) for c in cycles):
            cycles.append(cycle)
        if len(cycles) == k:
            break
    return cycles

def cover_set(graph):
    """
    Lefedő csúcshalmazt keres, amely minden kört lefed.

    Args:
        graph: A NetworkX gráf objektuma.

    Returns:
        set: A lefedő csúcshalmaz.
    """
    covering_set = set()
    while True:
        try:
            cycle = next(nx.simple_cycles(graph))
            covering_set.update(cycle)
            graph.remove_nodes_from(cycle)
        except StopIteration:
            break
    return covering_set

# Példa gráf
G = nx.DiGraph()
edges = 
G.add_edges_from(edges)

# Keresés
k = 2
disjoint_cycles = find_disjoint_cycles(G.copy(), k)
print("Diszjunkt körök:", disjoint_cycles)

cover = cover_set(G.copy())
print("Lefedő csúcshalmaz:", cover)

Diszjunkt körök: , ]
Lefedő csúcshalmaz: {'A', 'B', 'C', 'D', 'E'}

1. Hálózattervezés: Körökre épülő redundáns hálózatok optimalizálása.
2. Adatstruktúrák: Körök kezelése gráf-alapú rendszerekben (pl. közlekedési hálózatok).
3. Bioinformatika: Körstruktúrák keresése genetikai hálózatokban.

Az **Erdős–Pósa-tétel** az egyik legfontosabb összefüggést adja a diszjunkt körök és lefedő csúcshalmazok között a gráfelméletben. A tétel nemcsak elméleti jelentőséggel bír, hanem széles körben alkalmazható a hálózatok és kombinatorikus optimalizáció területén. Python segítségével a tételhez kapcsolódó algoritmusok egyszerűen implementálhatók.

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