Déterminer si une séquence de degrés forme un graphe simple | Algorithme de Havel-Hakimi

Dans la théorie des graphes, une chaîne de degrés représente l'ordre des degrés des sommets. Il est crucial de déterminer si l’ordre des degrés peut produire un graphique simple ou un graphique sans arêtes parallèles ou en boucle automatique. Dans ce blog, nous explorerons trois méthodes pour résoudre ce problème, en nous concentrant sur l'algorithme de Havel-Hakimi. Nous détaillerons les algorithmes utilisés par chaque technique, fournirons les représentations de code correspondantes et les titres appropriés, et démontrerons les résultats uniques de chaque approche.

Méthode à utiliser

• Algorithme Havel−Hakimi

• Trier et vérifier

• Comptage direct

Havel− Algorithme Hakimi

L'algorithme Havel−Hakimi est une technique couramment utilisée pour déterminer si une séquence de degrés peut générer un graphique simple. Éliminez les degrés un à un jusqu’à atteindre la situation initiale.

Algorithme

• Utilisez l'algorithme suivant pour trier les séries de diplômes par ordre décroissant.

• Renvoie vrai si la chaîne de degrés est nulle (cela crée un graphique simple).

• Si le degré initial est défavorable ou supérieur à la somme des degrés restants, renvoie false (ne peut pas former un graphique simple).

• Soustrayez le diplôme initial de la liste.

• Soustrayez 1 des « k » degrés suivants, où « k » est la valeur du degré à supprimer.

• Suivez à nouveau les étapes 1 à 5.

Exemple

#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;
}

Sortie

The sequence cannot represent a valid graph.

La traduction chinoise de

Sort & Check

est :

Sort & Check

La deuxième méthode consiste à trier la séquence de degrés dans un ordre non décroissant et à déterminer à plusieurs reprises si les conditions préalables à un graphique direct sont remplies.

Algorithme

• Utilisez l'algorithme suivant pour trier les séries de diplômes par ordre décroissant.

• Répétez ce processus pour chaque diplôme de la série.

• Renvoyer faux si le niveau actuel est défavorable ou si le nombre dépasse le nombre de degrés disponibles.

• Renvoie vrai si chaque degré réussit le test (cela crée un graphique intuitif).

Exemple

#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;
}

Sortie

The degree sequence cannot form a simple graph.

Comptage direct

La quatrième méthode mesure simplement le nombre de niveaux qui satisfont une condition prédéterminée pour déterminer si la séquence peut être représentée sous la forme d'un simple graphique.

Algorithme

• Déterminez le nombre de degrés supérieur ou égal à 0 et enregistrez le résultat dans 'n'.

• Renvoyer false si 'n' est impair (il ne forme pas un simple graphique).

• Mesurez et conservez les degrés non nuls en "k" qui sont supérieurs à la gauche.

• Si 'k' est supérieur au nombre de degrés restants, renvoyez false.

• Renvoie vrai si toutes les conditions sont remplies (cela crée un graphique de base).

Exemple

#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;
}

Sortie

The sequence can represent a valid graph.

Conclusion

Dans cet article, nous explorons trois manières différentes de déterminer si une séquence de degrés spécifique forme un graphique simple. Nous avons discuté de l'algorithme Havel−Hakimi, qui utilise une méthode de réduction pas à pas pour déterminer si la formation d'un graphe est réalisable. Nous avons également examiné les méthodes de tableau de degrés, les méthodes de comptage direct et les méthodes de tri et de vérification, chacune avec des stratégies différentes pour valider les conditions sur des graphiques de base. En comprenant et en utilisant ces techniques, vous pouvez déterminer rapidement si un graphique peut être créé à partir d’une séquence spécifique de degrés. La méthode choisie dépendra des spécifications et caractéristiques spécifiques de la séquence d’études en cours.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!