Wikiszótár

Welsh-Powell-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈvɛlʃhpovɛlːɒlɡoritmuʃ]

Főnév

Welsh-Powell-algoritmus

  1. (matematika, algoritmusok)

Welsh-Powell-algoritmus

A Welsh-Powell-algoritmus egy hatékony gráfszínezési algoritmus, amely csökkentett kromatikus számot eredményezhet, mint a Greedy algoritmus. Az algoritmus a csúcsokat csökkenő fokszám szerint rendezi, majd sorban próbálja őket színezni.


Python Implementáció

def welsh_powell(graph):
    """
    Welsh-Powell algoritmus a gráfszínezési problémára.
    
    Args:
        graph: Szomszédsági lista, ahol graph[i] az i csúcs szomszédait tartalmazza.
    
    Returns:
        colors: Lista, amely tartalmazza az egyes csúcsok színeit.
    """
    n = len(graph)
    # Csúcsok fokszám szerinti rendezése
    degrees = [(node, len(graph[node])) for node in range(n)]
    degrees.sort(key=lambda x: x[1], reverse=True)

    colors = [-1] * n  # Kezdetben minden csúcs nincs színezve
    color = 0  # Az első szín

    for node, _ in degrees:
        if colors[node] == -1:  # Csak még nem színezett csúcsokat színezünk
            colors[node] = color
            # Színezzük azokat a csúcsokat, amelyek nem szomszédosak a már színezett csúcsokkal
            for neighbor, _ in degrees:
                if colors[neighbor] == -1 and all(colors[adj] != color for adj in graph[neighbor]):
                    colors[neighbor] = color
            color += 1  # Következő szín

    return colors

# Példa gráf szomszédsági listával
graph = [
    [1, 2, 3],  # 0. csúcs szomszédai
    [0, 2],     # 1. csúcs szomszédai
    [0, 1, 3],  # 2. csúcs szomszédai
    [0, 2]      # 3. csúcs szomszédai
]

# Welsh-Powell algoritmus futtatása
colors = welsh_powell(graph)

print("Csúcsok színei:", colors)

Példa Kimenet

Csúcsok színei: [0, 1, 2, 1]

C++ Implementáció

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Welsh-Powell algoritmus implementáció
vector<int> welsh_powell(const vector<vector<int>>& graph) {
    int n = graph.size();
    vector<int> colors(n, -1); // Csúcsok színei (-1 = nincs színezve)
    
    // Csúcsok fokszám szerinti rendezése
    vector<pair<int, int>> degrees;
    for (int i = 0; i < n; i++) {
        degrees.push_back({i, graph[i].size()});
    }
    sort(degrees.begin(), degrees.end(), [](pair<int, int>& a, pair<int, int>& b) {
        return b.second < a.second; // Csökkenő sorrend
    });

    int color = 0; // Kezdeti szín
    for (auto& node_degree : degrees) {
        int node = node_degree.first;
        if (colors[node] == -1) { // Még nincs színezve
            colors[node] = color;
            // Színezés nem szomszédos csúcsokhoz
            for (auto& other_node : degrees) {
                int neighbor = other_node.first;
                if (colors[neighbor] == -1) {
                    bool canColor = true;
                    for (int adj : graph[neighbor]) {
                        if (colors[adj] == color) {
                            canColor = false;
                            break;
                        }
                    }
                    if (canColor) {
                        colors[neighbor] = color;
                    }
                }
            }
            color++; // Következő szín
        }
    }

    return colors;
}

int main() {
    // Példa gráf szomszédsági listával
    vector<vector<int>> graph = {
        {1, 2, 3}, // 0. csúcs szomszédai
        {0, 2},    // 1. csúcs szomszédai
        {0, 1, 3}, // 2. csúcs szomszédai
        {0, 2}     // 3. csúcs szomszédai
    };

    // Welsh-Powell algoritmus futtatása
    vector<int> colors = welsh_powell(graph);

    // Eredmények kiírása
    cout << "Csúcsok színei: ";
    for (int color : colors) {
        cout << color << " ";
    }
    cout << endl;

    return 0;
}

Példa Kimenet

Csúcsok színei: 0 1 2 1

Magyarázat

  1. Input: Egy gráf szomszédsági listában megadva.
  2. Csúcsok rendezése: A csúcsokat a fokszámuk szerint csökkenő sorrendben rendezzük.
  3. Színezés:
    • A legmagasabb fokszámú csúcsot egy színnel színezzük.
    • Megpróbáljuk ugyanazt a színt alkalmazni a nem szomszédos csúcsokra.
    • Ha nem lehetséges, új színt adunk.
  4. Output: A csúcsok színeit tartalmazó lista.


Előnyök

  • Hatékonyabb, mint a Greedy algoritmus a kromatikus szám minimalizálásában.
  • Időbonyolultság: (O(V^2)), ahol (V) a csúcsok száma.

Hátrányok

  • Nem garantálja az optimális kromatikus számot.


Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Welsh-Powell-algoritmus&oldid=3479796”