Kuratowski-tétel

1. Sablon:Label Kuratowski síkbarajzolhatósági tétele – Egy gráf akkor és csak akkor síkbarajzolható, ha nem tartalmaz felosztott K_3,3-at vagy felosztott K₅-öt. Itt K_3,3 a (3,3) párhoz tartozó teljes páros gráf (a három ház–három kút-gráf), K₅ az öt csúcspontú teljes gráf (a „teljes ötös”).

---

Kuratowski-tétel

Definíció

A **Kuratowski-tétel** egy alapvető állítás a gráfelméletben, amely a síkbarajzolható gráfok karakterizációját adja. A tétel kimondja:

> Egy gráf akkor és csak akkor síkbarajzolható, ha nem tartalmaz \( K_5 \) (teljes gráf öt csúccsal) vagy \( K_{3,3} \) (három csúcspár teljes kétszeresen összekötött gráfja) topológiai minorát.

Fogalmak

Síkbarajzolhatóság

- Egy gráf **síkbarajzolható**, ha rajzolható síkban úgy, hogy élei csak csúcsokon találkoznak (nincsenek metsző élek).

Topológiai minor

- Egy gráf \( H \) egy másik gráf \( G \) topológiai minorja, ha \( H \) előáll \( G \)-ból élkontrahálások (összevonások), él- és csúcseltávolítások sorozatával.

Kritikus gráfok

- A \( K_5 \) és \( K_{3,3} \) kritikus nem síkbarajzolható gráfok, azaz ezek biztosan nem rajzolhatók le síkban, és minden síkbarajzolható gráf ezek topológiai minoraitól mentes.

A tétel bizonyítása (vázlatosan)

1. Szükséges feltétel

Ha a gráf nem síkbarajzolható, akkor tartalmaz \( K_5 \)-öt vagy \( K_{3,3} \)-at topológiai minorban.

1. Tegyük fel, hogy \( G \) nem síkbarajzolható.
2. Wagner-tétel alapján a nem síkbarajzolható gráfok \( K_5 \)-öt vagy \( K_{3,3} \)-at tartalmaznak minorban.
3. Ha a gráf tartalmaz \( K_5 \)-öt vagy \( K_{3,3} \)-at minorban, akkor ezek valamelyikének topológiai minorai is jelen vannak.

2. Elégséges feltétel

Ha egy gráf síkbarajzolható, akkor nem tartalmaz \( K_5 \)-öt vagy \( K_{3,3} \)-at topológiai minorban.

1. Tegyük fel, hogy \( G \) síkbarajzolható.
2. Ha \( G \) tartalmazna \( K_5 \)-öt vagy \( K_{3,3} \)-at topológiai minorban, akkor \( G \) sem lenne síkbarajzolható (mivel ezek nem síkbarajzolhatók).
3. Ez ellentmond annak, hogy \( G \) síkbarajzolható.

A két feltétel teljesülése bizonyítja a tételt.

Példa Gráfok

1. **\( K_5 \):** Teljes gráf öt csúccsal. Minden csúcs minden más csúccsal össze van kötve.

  - 5 csúcs, 10 él.
  - Nem síkbarajzolható, mert nem elég a síkon 4 diszjunkt régió az élek ábrázolásához.

1. **\( K_{3,3} \):** Bipartit gráf három csúccsal mindkét partícióban, ahol minden csúcs össze van kötve az ellentétes partíció összes csúcsával.

  - 6 csúcs, 9 él.
  - Nem síkbarajzolható, mert nem lehet az éleket úgy elhelyezni, hogy ne metsződjenek.

Egyenes bizonyítás Euler-tétellel

Euler-tétel a síkbarajzolható gráfokhoz

Egy síkbarajzolható gráfra teljesül: $v-e+f=2$ ahol:

• \( v \): a csúcsok száma,
• \( e \): az élek száma,
• \( f \): a régiók száma.

Korlátok alkalmazása

1. Ha a gráf síkbarajzolható, minden régiót legalább három él határol:

$2e\ge 3f$ Mivel \( f = 2 - v + e \), behelyettesítéssel: $e\le 3v-6$

1. Ha a gráf nem tartalmaz \( K_5 \)-öt vagy \( K_{3,3} \)-at, akkor ezek élszáma túl nagy ahhoz, hogy megfeleljen az \( e \leq 3v - 6 \) korlátnak.

Python Implementáció a Kuratowski-tétel ellenőrzésére

import networkx as nx

def is_planar(graph):
    """
    Ellenőrzi, hogy egy gráf síkbarajzolható-e.
    
    Args:
        graph: A NetworkX gráf objektuma.
    
    Returns:
        True, ha a gráf síkbarajzolható, különben False.
    """
    planar, _ = nx.check_planarity(graph)
    return planar

# Példa gráfok
G1 = nx.complete_graph(5)  # K5
G2 = nx.complete_bipartite_graph(3, 3)  # K3,3
G3 = nx.cycle_graph(5)  # Egy síkbarajzolható gráf

print("K5 síkbarajzolható:", is_planar(G1))  # False
print("K3,3 síkbarajzolható:", is_planar(G2))  # False
print("C5 síkbarajzolható:", is_planar(G3))  # True

Kimenet

K5 síkbarajzolható: False
K3,3 síkbarajzolható: False
C5 síkbarajzolható: True

C++ Implementáció a Boost könyvtárral

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/planar_test.hpp>

using namespace boost;

int main() {
    // Gráf deklarációja
    typedef adjacency_list<vecS, vecS, undirectedS> Graph;

    // K5 definiálása
    Graph G(5);
    add_edge(0, 1, G);
    add_edge(0, 2, G);
    add_edge(0, 3, G);
    add_edge(0, 4, G);
    add_edge(1, 2, G);
    add_edge(1, 3, G);
    add_edge(1, 4, G);
    add_edge(2, 3, G);
    add_edge(2, 4, G);
    add_edge(3, 4, G);

    // Planaritás ellenőrzése
    if (boyer_myrvold_planarity_test(boyer_myrvold_params::graph = G)) {
        std::cout << "K5 síkbarajzolható." << std::endl;
    } else {
        std::cout << "K5 nem síkbarajzolható." << std::endl;
    }

    return 0;
}

Kimenet

K5 nem síkbarajzolható.

Alkalmazások

1. Áramkörök tervezése: Elektromos kapcsolási rajzok síkba helyezhetősége.
2. Hálózatok: Hálózati diagramok vizualizációja.
3. Számítógépes grafika: Síkgrafikus ábrázolások készítése.

Összegzés

A **Kuratowski-tétel** elengedhetetlen a síkbarajzolható gráfok azonosításához. Ez a tétel elméleti gráfelméleti problémák megoldásában és gyakorlati alkalmazásokban, például hálózattervezésben is kulcsszerepet játszik. Az Euler-tétel és algoritmikus eszközök segítségével hatékonyan ellenőrizhető egy gráf síkbarajzolhatósága.

• Sablon:En: Sablon:T