Erdős-Pósa-tétel

Sablon:Hunfn Sablon:Label 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.

---

Erdős–Pósa-tétel

Definíció

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ó $k$ páronként diszjunkt kör, vagy van egy legfeljebb $c\cdot k\cdot \log (k)$ méretű csúcshalmaz, amely lefedi az összes kört.

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

Fogalmak

Körök a gráfban

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

Páronként diszjunkt körök

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

Csúcspár-foglalat

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

Tétel Értelmezése

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

  - $k$ páronként diszjunkt kör létezik.
  - Egy $S$ csúcshalmaz eltávolításával az összes kör megszűnik, és $|S|\le 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.

Tétel Bizonyítása (Vázlatosan)

Gráfelméleti eszközök

- 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 $k$-diszjunkt körök megtalálása iteratív algoritmusokkal lehetséges.

Diszjunkt körök maximalizálása

- Ha $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ő $c$ konstans határozza meg.

Lefedő csúcshalmaz bizonyítása

- 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.

Következtetés

- Az $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 $c\cdot k\cdot \log (k)$-nél nem lehet nagyobb.

Példa

Gráf

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

Lépések

1. Találjunk $k$-diszjunkt köröket:

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

1. Lefedő csúcshalmaz:

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

Eredmény

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

Python Implementáció

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 = [("A", "B"), ("B", "C"), ("C", "A"), ("C", "D"), ("D", "E"), ("E", "C")]
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)

Kimenet

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

Alkalmazások

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.

Összegzés

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.

• Sablon:En: Sablon:T