그래프 이론에서 각도 체인은 정점 각도의 순서를 나타냅니다. 각도의 순서가 간단한 그래프를 생성할 수 있는지 또는 평행 또는 자체 루프 모서리가 없는 그래프를 생성할 수 있는지 결정하는 것이 중요합니다. 이 블로그에서는 Havel-Hakimi 알고리즘을 중심으로 이 문제를 해결하는 세 가지 방법을 살펴보겠습니다. 각 기술에 사용되는 알고리즘을 자세히 설명하고 해당 코드 표현과 적절한 제목을 제공하며 각 접근 방식의 고유한 결과를 보여줍니다.
Havel−Hakimi 알고리즘
정렬 및 확인
직접 계산
Havel−Hakimi 알고리즘은 차수 시퀀스가 간단한 그래프를 생성할 수 있는지 여부를 결정하는 데 일반적으로 사용되는 기술입니다. 초기 상황에 도달할 때까지 하나씩 도를 제거합니다.
다음 알고리즘을 사용하여 학위 계열을 내림차순으로 정렬하세요.
차수 체인이 0이면 true를 반환합니다(간단한 그래프가 생성됨).
초기 차수가 불리하거나 나머지 차수의 합보다 높을 경우 false를 반환합니다. (간단한 그래프를 구성할 수 없음)
목록에서 초기 학위를 뺍니다.
다음 'k' 각도에서 1을 뺍니다. 여기서 'k'는 제거되는 각도의 값입니다.
1~5단계를 다시 따르세요.
두 번째 방법은 차수열을 내림차순으로 정렬하고 직접 그래프의 전제 조건을 충족하는지 반복적으로 확인하는 것입니다.
다음 알고리즘을 사용하여 학위 계열을 내림차순으로 정렬합니다.
시리즈의 각 학위에 대해 이 과정을 반복하세요.
현재 수준이 바람직하지 않거나 숫자가 가능한 학위 수를 초과하는 경우 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!