학위 시퀀스가 ​​간단한 그래프를 형성하는지 확인 |

그래프 이론에서 각도 체인은 정점 각도의 순서를 나타냅니다. 각도의 순서가 간단한 그래프를 생성할 수 있는지 또는 평행 또는 자체 루프 모서리가 없는 그래프를 생성할 수 있는지 결정하는 것이 중요합니다. 이 블로그에서는 Havel-Hakimi 알고리즘을 중심으로 이 문제를 해결하는 세 가지 방법을 살펴보겠습니다. 각 기술에 사용되는 알고리즘을 자세히 설명하고 해당 코드 표현과 적절한 제목을 제공하며 각 접근 방식의 고유한 결과를 보여줍니다.

사용방법

• Havel−Hakimi 알고리즘

• 정렬 및 확인

• 직접 계산

Havel− 하키미 알고리즘

Havel−Hakimi 알고리즘은 차수 시퀀스가 ​​간단한 그래프를 생성할 수 있는지 여부를 결정하는 데 일반적으로 사용되는 기술입니다. 초기 상황에 도달할 때까지 하나씩 도를 제거합니다.

알고리즘

• 다음 알고리즘을 사용하여 학위 계열을 내림차순으로 정렬하세요.

• 차수 체인이 0이면 true를 반환합니다(간단한 그래프가 생성됨).

• 초기 차수가 불리하거나 나머지 차수의 합보다 높을 경우 false를 반환합니다. (간단한 그래프를 구성할 수 없음)

• 목록에서 초기 학위를 뺍니다.

• 다음 'k' 각도에서 1을 뺍니다. 여기서 'k'는 제거되는 각도의 값입니다.

• 1~5단계를 다시 따르세요.

예

으아악

출력

으아악

Sort & Check

의 중국어 번역은

Sort & Check

입니다.

두 번째 방법은 차수열을 내림차순으로 정렬하고 직접 그래프의 전제 조건을 충족하는지 반복적으로 확인하는 것입니다.

알고리즘

• 다음 알고리즘을 사용하여 학위 계열을 내림차순으로 정렬합니다.

• 시리즈의 각 학위에 대해 이 과정을 반복하세요.

• 현재 수준이 바람직하지 않거나 숫자가 가능한 학위 수를 초과하는 경우 false를 반환합니다.

• 각 학위가 테스트를 통과하면 true를 반환합니다(직관적인 그래프가 생성됩니다).

예

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

출력

으아악

직접 계산

네 번째 방법은 단순히 정해진 조건을 만족하는 수준의 개수를 측정하여 수열을 간단한 그래프로 표현할 수 있는지 판단하는 것입니다.

알고리즘

• 0보다 크거나 같은 각도를 결정하고 그 결과를 'n'에 저장합니다.

• 'n'이 홀수이면 false를 반환합니다(간단한 그래프를 형성하지 않음).

• 왼쪽보다 더 큰 "k"에서 0이 아닌 각도를 측정하고 유지하세요.

• 'k'가 남은 도수보다 높으면 false를 반환합니다.

• 모든 요구 사항이 충족되면 true를 반환합니다(기본 그래프 생성).

예

으아악

출력

으아악

결론

이 글에서는 특정 학위 시퀀스가 ​​간단한 그래프를 형성하는지 확인하는 세 가지 방법을 살펴봅니다. 그래프 형성이 가능한지 여부를 결정하기 위해 단계적 축소 방법을 사용하는 Havel-Hakimi 알고리즘에 대해 논의했습니다. 또한 기본 그래프의 조건을 검증하기 위한 전략이 서로 다른 차수 배열 방법, 직접 계산 방법, 정렬 및 확인 방법을 살펴보았습니다. 이러한 기술을 이해하고 사용하면 특정 각도 시퀀스에서 그래프를 만들 수 있는지 여부를 빠르게 확인할 수 있습니다. 선택한 방법은 현재 학위 시퀀스의 특정 사양과 특성에 따라 달라집니다.

위 내용은 학위 시퀀스가 ​​간단한 그래프를 형성하는지 확인 |의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!