โปรแกรม C++ สำหรับการทำ Edge Coloring บน Line Graph

Line Graph L(G) ของกราฟแบบไม่มีทิศทาง G เป็นกราฟอีกตัวหนึ่งที่แทนความติดกันระหว่างขอบ (edges) ของ G ในโปรแกรมนี้ เราทำ Edge Coloring บน Line Graph ของกราฟอินพุต

อัลกอริธึม

1. รับจำนวนโหนด n และจำนวนขอบ e
2. รับคู่โหนด e คู่ สำหรับขอบในกราฟ (เก็บใน ed[][])
3. GenLineGraph(): สร้าง Line Graph ใน LineEd[][]
   • สำหรับแต่ละขอบในกราฟต้นฉบับ เชื่อมต่อกับขอบที่ติดกันใน LineEd
4. EdgeColor(): ทาสีขอบของกราฟ LineEd
   • กำหนดสีให้ขอบปัจจุบันเป็น col (เริ่มจาก 1)
   • ถ้าขอบติดกันมีสีเดียวกัน → ทิ้งสีนี้ ลองสีถัดไป (goto flag)
   • พิมพ์สีสำหรับแต่ละขอบของ line graph

โค้ดตัวอย่าง

#include <iostream>
#include <vector>
#include <map>
using namespace std;

// สร้าง Line Graph: return จำนวนขอบใน line graph
int GenLineGraph(const vector<pair<int,int>> &edges, vector<pair<int,int>> &lineEdges) {
    int e = edges.size();
    for (int i = 0; i < e; ++i) {
        for (int j = i + 1; j < e; ++j) {
            // ขอบ i และ j ติดกันถ้า share vertex
            if (edges[i].first == edges[j].first || edges[i].first == edges[j].second ||
                edges[i].second == edges[j].first || edges[i].second == edges[j].second) {
                lineEdges.emplace_back(i, j); // vertex ใน line graph = edge index ใน original
            }
        }
    }
    return lineEdges.size();
}

// Greedy Edge Coloring
void EdgeColor(const vector<pair<int,int>> &lineEdges, vector<int> &color) {
    int E = lineEdges.size();
    color.assign(E, 0);

    // สร้าง adjacency list ของ line graph
    vector<vector<int>> adj(E);
    for (int i = 0; i < E; ++i) {
        for (int j = i + 1; j < E; ++j) {
            if (lineEdges[i].first == lineEdges[j].first || lineEdges[i].first == lineEdges[j].second ||
                lineEdges[i].second == lineEdges[j].first || lineEdges[i].second == lineEdges[j].second) {
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }

    // Greedy coloring
    for (int i = 0; i < E; ++i) {
        vector<bool> used(E + 1, false);
        for (int nb : adj[i])
            if (color[nb] != 0) used[color[nb]] = true;

        int c = 1;
        while (used[c]) ++c;
        color[i] = c;
    }
}

int main() {
    int n, e;
    cout << "Enter number of vertices: "; cin >> n;
    cout << "Enter number of edges: "; cin >> e;

    vector<pair<int,int>> edges;
    for (int i = 0; i < e; ++i) {
        int u, v;
        cout << "Edge " << i+1 << " - V1: "; cin >> u;
        cout << "V2: "; cin >> v;
        edges.emplace_back(u, v);
    }

    vector<pair<int,int>> lineEdges;
    GenLineGraph(edges, lineEdges);

    cout << "\nLine Graph edges (original edge indices):" << endl;
    for (auto &p : lineEdges)
        cout << "(" << p.first << "," << p.second << ") " << endl;

    vector<int> color;
    EdgeColor(lineEdges, color);

    cout << "\nEdge Coloring of Line Graph:" << endl;
    for (int i = 0; i < (int)lineEdges.size(); ++i) {
        cout << "Line edge " << i << " (orig edges " << lineEdges[i].first << "-" << lineEdges[i].second
             << ") : color " << color[i] << endl;
    }
    return 0;
}

ตัวอย่างผลลัพธ์

Enter number of vertices: 4
Enter number of edges: 3
Edge 1 - V1: 1 V2: 2
Edge 2 - V1: 3 V2: 2
Edge 3 - V1: 4 V2: 1

Line Graph edges (original edge indices):
(0,1)  // edge 0 (1-2) ติด edge 1 (3-2) ที่ vertex 2
(0,2)  // edge 0 (1-2) ติด edge 2 (4-1) ที่ vertex 1

Edge Coloring of Line Graph:
Line edge 0 (orig edges 0-1) : color 1
Line edge 1 (orig edges 0-2) : color 2

ทฤษฎี: Edge coloring ของ line graph = Vertex coloring ของ original graph (Vizing's theorem) จำนวนสีขั้นต่ำ = Δ หรือ Δ+1 (Δ = max degree)