Cari sama ada jujukan darjah membentuk graf ringkas |

Dalam teori graf, rantaian darjah mewakili susunan darjah bucu. Adalah penting untuk menentukan sama ada susunan darjah boleh menghasilkan graf ringkas atau graf tanpa tepi selari atau gelung sendiri. Dalam blog ini, kami akan meneroka tiga kaedah untuk menyelesaikan masalah ini, memberi tumpuan kepada algoritma Havel-Hakimi. Kami akan memperincikan algoritma yang digunakan oleh setiap teknik, menyediakan perwakilan kod yang sepadan dan tajuk yang sesuai, dan menunjukkan hasil unik setiap pendekatan.

Kaedah penggunaan

• Havel−Algoritma Hakimi

• Isih dan Semak

• Pengiraan terus

Havel− Algoritma Hakimi

Algoritma Havel−Hakimi ialah teknik yang biasa digunakan untuk menentukan sama ada jujukan darjah boleh menjana graf ringkas. Hapuskan darjah satu demi satu sehingga keadaan awal dicapai.

Algoritma

• Gunakan algoritma berikut untuk mengisih siri darjah dalam tertib menurun.

• Kembalikan benar jika rantaian darjah adalah sifar (ia menghasilkan graf mudah).

• Jika darjah awal tidak menguntungkan atau lebih tinggi daripada jumlah darjah yang tinggal, kembalikan palsu (tidak boleh membentuk graf mudah).

• Tolak darjah awal daripada senarai.

• Tolak 1 daripada darjah 'k' berikut, dengan 'k' ialah nilai darjah yang dikeluarkan.

• Ikuti langkah 1-5 sekali lagi.

Contoh

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

using namespace std;

bool havelHakimi(vector<int>& degrees) {
    sort(degrees.rbegin(), degrees.rend()); // Sort in non-increasing order

    while (!degrees.empty() && degrees.front() > 0) {
        int firstDegree = degrees.front();
        degrees.erase(degrees.begin()); // Remove the first degree

        if (firstDegree > degrees.size()) {
            return false;
        }

        for (int i = 0; i < firstDegree; ++i) {
            degrees[i]--;
        }

        sort(degrees.rbegin(), degrees.rend()); // Re-sort the sequence
    }

    return degrees.empty(); // Return true if the sequence is empty
}

int main() {
    // Test the havelHakimi function
    vector<int> degrees = {3, 1, 2, 3, 1, 0};
    bool result = havelHakimi(degrees);

    if (result) {
        cout << "The sequence can represent a valid graph." << endl;
    } else {
        cout << "The sequence cannot represent a valid graph." << endl;
    }

    return 0;
}

Output

The sequence cannot represent a valid graph.

Isih & Semak

Isih & Semak

Kaedah kedua ialah mengisih urutan darjah dalam susunan tidak menurun dan berulang kali menentukan sama ada prasyarat untuk graf langsung dipenuhi.

Algoritma

• Gunakan algoritma berikut untuk mengisih siri darjah dalam tertib menurun.

• Ulang proses ini untuk setiap ijazah dalam siri ini.

• Kembalikan palsu jika tahap semasa tidak menguntungkan atau bilangannya melebihi bilangan darjah yang ada.

• Berhasil jika setiap ijazah lulus ujian (ia menghasilkan graf intuitif).

Contoh

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

using namespace std;

bool havelHakimiAlgorithm(vector<int>& degrees) {
    // Sort the degree sequence in non-increasing order
    sort(degrees.rbegin(), degrees.rend());

    while (!degrees.empty() && degrees[0] > 0) {
        int highestDegree = degrees[0];
        int n = degrees.size();

        // Check if the highest degree is greater than the number of remaining vertices
        if (highestDegree >= n) {
            return false;
        }

        // Remove the highest degree vertex
        degrees.erase(degrees.begin());

        // Decrease the degrees of its neighbors
        for (int i = 0; i < highestDegree; ++i) {
            degrees[i]--;
        }

        // Sort the degree sequence again
        sort(degrees.rbegin(), degrees.rend());
    }

    // If all degrees are zero, the degree sequence can form a simple graph
    return degrees.empty();
}

int main() {
    // Example degree sequence
    vector<int> degrees = {3, 3, 2, 2, 1};

    // Check if the degree sequence can form a simple graph
    bool canFormGraph = havelHakimiAlgorithm(degrees);

    if (canFormGraph) {
        cout << "The degree sequence can form a simple graph." << endl;
    } else {
        cout << "The degree sequence cannot form a simple graph." << endl;
    }

    return 0;
}

Output

The degree sequence cannot form a simple graph.

Pengiraan terus

Kaedah keempat hanya mengukur bilangan tahap yang memenuhi syarat yang telah ditetapkan untuk menentukan sama ada jujukan boleh diwakili sebagai graf ringkas.

Algoritma

• Tentukan bilangan darjah yang lebih besar daripada atau sama dengan 0 dan simpan hasilnya dalam 'n'.

• Kembalikan palsu jika 'n' ganjil (ia tidak membentuk graf mudah).

• Ukur dan simpan darjah bukan sifar dalam "k" yang lebih daripada kiri.

• Jika 'k' lebih tinggi daripada bilangan darjah yang tinggal, kembalikan palsu.

• Kembalian benar jika semua keperluan dipenuhi (ia menghasilkan graf asas).

Contoh

#include <iostream>
#include <vector>

using namespace std;

bool directCount(vector<int>& degrees) {
    int n = 0;
    int k = 0;

    for (int degree : degrees) {
        if (degree >= 0) {
            n++;
            if (degree > degrees.size() - n) {
                k++;
            }
        }
    }

    return (n % 2 == 0) && (k <= n);
}

int main() {
    // Test the directCount function
    vector<int> degrees = {3, 1, 2, 3, 1, 0};
    bool result = directCount(degrees);

    if (result) {
        cout << "The sequence can represent a valid graph." << endl;
    } else {
        cout << "The sequence cannot represent a valid graph." << endl;
    }

    return 0;
}

Output

The sequence can represent a valid graph.

Kesimpulan

Dalam artikel ini, kami meneroka tiga cara berbeza untuk menentukan sama ada jujukan darjah tertentu membentuk graf ringkas. Kami membincangkan algoritma Havel−Hakimi, yang menggunakan pendekatan pengurangan langkah demi langkah untuk menentukan sama ada pembentukan graf boleh dilaksanakan. Kami juga melihat kaedah tatasusunan darjah, kaedah pengiraan terus dan kaedah isih dan semak, masing-masing dengan strategi yang berbeza untuk mengesahkan keadaan pada graf asas. Dengan memahami dan menggunakan teknik ini, anda boleh menentukan dengan cepat sama ada graf boleh dibuat daripada jujukan darjah tertentu. Kaedah yang dipilih akan bergantung kepada spesifikasi dan ciri khusus siri ijazah semasa.

Atas ialah kandungan terperinci Cari sama ada jujukan darjah membentuk graf ringkas |. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!