Euler-út

Magyar

Kiejtés

IPA: [ ˈɛulɛruːt]

Főnév

Euler-út definíció

Egy Euler-út egy gráfban olyan út, amely pontosan egyszer halad át minden élen. A gráf Euler-köre pedig olyan Euler-út, amely zárt, vagyis ugyanabban a csúcsban végződik, ahol kezdődött.

Feltételek az Euler-út létezésére

Egy irányítatlan gráfban Euler-út akkor létezik, ha:
- Legfeljebb két csúcsnak van páratlan fokszáma.
- Az összes él egy összefüggő komponens része (összefüggő gráf, figyelembe véve az éleket).
Euler-kör akkor létezik, ha:
- Minden csúcs fokszáma páros.
- Az összes él egy összefüggő komponens része.
Egy irányított gráfban Euler-út akkor létezik, ha:
- Legfeljebb egy csúcsban a kimenő élek száma (out-degree) pontosan egyel nagyobb, mint a bemenő élek száma (in-degree).
- Legfeljebb egy csúcsban az in-degree pontosan egyel nagyobb, mint az out-degree.
- Az összes él egy összefüggő komponens része (figyelembe véve az irányított éleket).
Irányított Euler-kör létezik, ha:
- Minden csúcsban az in-degree és az out-degree megegyezik.
- Az összes él egy összefüggő komponens része.

Algoritmusok Euler-út és Euler-kör keresésére

1. Fleury algoritmus

Az egyik legegyszerűbb algoritmus az Euler-út vagy kör megtalálására. Az algoritmus lényege, hogy egy-egy élen úgy halad át, hogy ha lehetséges, ne vágjon ketté egy összefüggő komponenst.

Implementáció Fleury algoritmussal (irányítatlan gráf)

import networkx as nx

def is_eulerian_path(graph):
    odd_degree_nodes = [node for node in graph.nodes if graph.degree(node) % 2 == 1]
    return len(odd_degree_nodes) in [0, 2]  # Euler-kör: 0 páratlan fokszám, Euler-út: 2 páratlan fokszám

def fleury_algorithm(graph, start_node):
    if not is_eulerian_path(graph):
        return None  # Ha nincs Euler-út

    # Az út tárolása
    path = []

    # Gráf másolása, mert módosítani fogjuk
    g = graph.copy()

    def is_valid_edge(u, v):
        if len(list(g.neighbors(u))) == 1:
            return True  # Ha ez az egyetlen él
        # Teszt: összefüggőség ellenőrzése, ha eltávolítjuk az élt
        g.remove_edge(u, v)
        reachable = len(list(nx.dfs_edges(g, u))) + 1  # DFS bejárás
        g.add_edge(u, v)  # Élt visszaállítjuk
        return reachable == g.number_of_nodes()

    current = start_node
    while g.edges:
        for neighbor in list(g.neighbors(current)):
            if is_valid_edge(current, neighbor):
                path.append((current, neighbor))
                g.remove_edge(current, neighbor)
                current = neighbor
                break

    return path

# Példa gráf
G = nx.Graph()
edges = [(0, 1), (1, 2), (2, 0), (0, 3), (3, 4), (4, 0)]
G.add_edges_from(edges)

# Kezdő csúcs (bármely csúcs lehet, amelynek fokszáma nem nulla)
start = 0
euler_path = fleury_algorithm(G, start)
print("Euler-út:", euler_path)

Példa kimenet:

Euler-út: [(0, 1), (1, 2), (2, 0), (0, 3), (3, 4), (4, 0)]

2. Hierholzer algoritmus

A Hierholzer algoritmus gyorsabb, és főként Euler-kör megtalálására használják. Az algoritmus az útvonalak bővítésével dolgozik, amíg minden él szerepel.

Implementáció Hierholzer algoritmussal (irányítatlan gráf)

def hierholzer_algorithm(graph):
    if not nx.is_eulerian(graph):
        return None  # Ha nincs Euler-kör

    # Gráf másolása
    g = graph.copy()
    circuit = []
    stack = [list(g.nodes)[0]]  # Bármely csúccsal kezdhetjük

    while stack:
        current = stack[-1]
        if g.degree(current) == 0:
            circuit.append(stack.pop())
        else:
            neighbor = next(iter(g.neighbors(current)))
            stack.append(neighbor)
            g.remove_edge(current, neighbor)

    return circuit[::-1]  # Fordított sorrendben kapjuk az útvonalat

# Példa gráf
G = nx.Graph()
edges = [(0, 1), (1, 2), (2, 0), (0, 3), (3, 4), (4, 0)]
G.add_edges_from(edges)

euler_circuit = hierholzer_algorithm(G)
print("Euler-kör:", euler_circuit)

Példa kimenet:

Euler-kör: [0, 1, 2, 0, 3, 4, 0]

3. Euler-út irányított gráfban

Az irányított gráfban alkalmazhatjuk a Hierholzer algoritmust, hasonló módon, azzal a különbséggel, hogy az in-degree és out-degree egyensúlyára is figyelni kell.

Implementáció irányított gráfra:

def directed_hierholzer(graph):
    g = graph.copy()
    circuit = []
    stack = [list(g.nodes)[0]]  # Bármely csúccsal kezdhetjük

    while stack:
        current = stack[-1]
        if g.out_degree(current) == 0:
            circuit.append(stack.pop())
        else:
            neighbor = next(iter(g.successors(current)))
            stack.append(neighbor)
            g.remove_edge(current, neighbor)

    return circuit[::-1]  # Fordított sorrendben kapjuk az útvonalat

# Példa irányított gráf
G = nx.DiGraph()
edges = [(0, 1), (1, 2), (2, 0), (0, 3), (3, 4), (4, 0)]
G.add_edges_from(edges)

euler_circuit = directed_hierholzer(G)
print("Euler-kör irányított gráfban:", euler_circuit)

Példa kimenet:

Euler-kör irányított gráfban: [0, 1, 2, 0, 3, 4, 0]

Összefoglalás

Fleury algoritmus: Könnyebb megérteni, de kevésbé hatékony, mivel az élek összefüggőségi tesztje időigényes.
Hierholzer algoritmus: Hatékonyabb, mivel az algoritmus egyszerűen követi az éleket és építi a köröket/utakat.
Pythonban a networkx modul segítségével gyorsan és egyszerűen kezelhetjük a gráfokat, és számos beépített függvényt találhatunk Euler-út és -kör elemzésére.

Fordítások

Tartalom

angol: Eulerian path (en)