Finden Sie heraus, ob eine Gradfolge einen einfachen Graphen bildet |

In der Graphentheorie stellt eine Gradkette die Reihenfolge der Scheitelpunktgrade dar. Es ist entscheidend zu bestimmen, ob die Gradreihenfolge einen einfachen Graphen oder einen Graphen ohne parallele oder selbstschleifende Kanten erzeugen kann. In diesem Blog werden wir drei Methoden zur Lösung dieses Problems untersuchen und uns dabei auf den Havel-Hakimi-Algorithmus konzentrieren. Wir werden die von jeder Technik verwendeten Algorithmen detailliert beschreiben, entsprechende Codedarstellungen und entsprechende Titel bereitstellen und die einzigartigen Ergebnisse jedes Ansatzes demonstrieren.

Anwendungsmethode

• Havel-Hakimi-Algorithmus

• Sortieren und prüfen

• Direktes Zählen

Havel-Hakimi-Algorithmus

Der Havel-Hakimi-Algorithmus ist eine häufig verwendete Technik zur Bestimmung, ob eine Gradfolge einen einfachen Graphen erzeugen kann. Eliminieren Sie die Stufen nacheinander, bis die Ausgangssituation erreicht ist.

Algorithmus

• Verwenden Sie den folgenden Algorithmus, um Gradreihen in absteigender Reihenfolge zu sortieren.

• Gibt „true“ zurück, wenn die Gradkette Null ist (es wird ein einfaches Diagramm erstellt).

• Wenn der anfängliche Grad ungünstig oder höher als die Summe der verbleibenden Grade ist, wird „false“ zurückgegeben (ein einfaches Diagramm kann nicht erstellt werden).

• Subtrahieren Sie den Anfangsabschluss von der Liste.

• Subtrahieren Sie 1 von den folgenden „k“-Graden, wobei „k“ der Wert des zu entfernenden Grades ist.

• Folgen Sie den Schritten 1-5 noch einmal.

Beispiel

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

Ausgabe

The sequence cannot represent a valid graph.

Die chinesische Übersetzung von

Sort & Check

lautet:

Sort & Check

Die zweite Methode besteht darin, die Gradfolge in nicht absteigender Reihenfolge zu sortieren und wiederholt zu bestimmen, ob die Voraussetzungen für einen direkten Graphen erfüllt sind.

Algorithmus

• Verwenden Sie den folgenden Algorithmus, um die Abschlussreihen in absteigender Reihenfolge zu sortieren.

• Wiederholen Sie diesen Vorgang für jeden Abschluss in der Reihe.

• Gibt „false“ zurück, wenn das aktuelle Niveau ungünstig ist oder die Zahl die Anzahl der verfügbaren Grade überschreitet.

• Gibt „true“ zurück, wenn jeder Grad den Test besteht (es wird ein intuitives Diagramm erstellt).

Beispiel

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

Ausgabe

The degree sequence cannot form a simple graph.

Direktes Zählen

Die vierte Methode misst einfach die Anzahl der Ebenen, die eine vorgegebene Bedingung erfüllen, um zu bestimmen, ob die Sequenz als einfaches Diagramm dargestellt werden kann.

Algorithmus

• Bestimmen Sie die Gradzahl größer oder gleich 0 und speichern Sie das Ergebnis in „n“.

• Gib false zurück, wenn 'n' ungerade ist (es bildet kein einfaches Diagramm).

• Messen und behalten Sie die Grad ungleich Null in „k“, die weiter als links liegen.

• Wenn „k“ höher ist als die Anzahl der verbleibenden Grade, wird „false“ zurückgegeben.

• Gibt „true“ zurück, wenn alle Anforderungen erfüllt sind (es wird ein Basisdiagramm erstellt).

Beispiel

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

Ausgabe

The sequence can represent a valid graph.

Fazit

In diesem Artikel untersuchen wir drei verschiedene Möglichkeiten, um festzustellen, ob eine bestimmte Gradfolge einen einfachen Graphen bildet. Wir haben den Havel-Hakimi-Algorithmus besprochen, der eine schrittweise Reduktionsmethode verwendet, um zu bestimmen, ob die Bildung eines Graphen möglich ist. Wir haben uns auch Grad-Array-Methoden, direkte Zählmethoden und Sortier- und Prüfmethoden angesehen, jeweils mit unterschiedlichen Strategien zur Validierung von Bedingungen in einfachen Diagrammen. Wenn Sie diese Techniken verstehen und anwenden, können Sie schnell feststellen, ob ein Diagramm aus einer bestimmten Abfolge von Graden erstellt werden kann. Welche Methode gewählt wird, hängt von den spezifischen Spezifikationen und Besonderheiten des aktuellen Studiengangs ab.

Das obige ist der detaillierte Inhalt vonFinden Sie heraus, ob eine Gradfolge einen einfachen Graphen bildet |. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!