C++로 휠 그래프의 지름, 사이클 수, 간선 수 구하기

문제 소개

이 문제에서는 휠 그래프(Wheel Graph)의 정점 개수를 나타내는 숫자가 주어지며, 우리가 작성해야 할 프로그램은 C++로 휠 그래프의 지름, 사이클 수, 간선 수를 구하는 것입니다.

문제 설명 — n개의 정점을 가진 휠 그래프에 대해 사이클의 개수, 간선의 개수, 그리고 지름을 계산해야 합니다.

먼저 휠 그래프의 기본 개념부터 차근차근 살펴보겠습니다.

휠 그래프란?

휠 그래프는 사이클 그래프 C(n-1)에 새로운 정점 하나를 추가하여 만든 그래프입니다. 이때 새로 추가된 정점을 허브(Hub)라고 부르며, 허브는 해당 사이클의 모든 정점과 연결됩니다. 마치 바퀴(wheel)처럼 생겼다고 해서 '휠 그래프'라는 이름이 붙었습니다.

다음은 7개의 정점을 가진 휠 그래프의 예시입니다.

핵심 용어 정리

휠 그래프의 지름(Diameter)

한 정점에서 다른 정점으로 이동할 때 거쳐야 하는 간선의 최대 개수를 의미합니다. 위 휠 그래프의 경우 지름은 2입니다.

휠 그래프의 사이클 수(Cycles)

주어진 그래프에서 만들 수 있는 닫힌 경로, 즉 사이클의 총 개수입니다. 위 휠 그래프의 경우 사이클 수는 31개입니다.

휠 그래프의 간선 수(Edges)

모든 정점을 서로 연결하는 간선의 총 개수입니다. 위 휠 그래프의 경우 간선 수는 12개입니다.

해결 접근 방법

이 문제는 그래프 이론에서 제공하는 공식을 직접 활용하면 매우 간단하게 해결할 수 있습니다. 필요한 공식은 다음과 같습니다.

휠 그래프의 지름 =

정점이 4개인 경우 1, 그 외에는 2

휠 그래프의 사이클 수 =

(정점 개수)^2 − (3 × (정점 개수 − 1))

휠 그래프의 간선 수 =

2 × (정점 개수 − 1)

예제 코드

아래 프로그램은 위 공식을 활용해 휠 그래프의 속성값을 계산하는 과정을 보여줍니다.

#include <iostream>
#include <math.h>
using namespace std;

void calcValuesWheelGraph(int V){
    // Calculating the Diameter
    if(V == 4){
        cout<<"The Diameter of the Wheel Graph is 1 "<<endl;
    }
    else {
        cout<<"The Diameter of the Wheel Graph is 2 "<<endl;
    }
    // Calculating the no. of cycles
    cout<<"The number of cycles of the Wheel Graph is "<<(pow(V, 2) - (3 * (V-1)))<<endl;
    // Calculating the no. of Edges
    cout<<"The number of Edges of the Wheel Graph is "<<(2 * (V-1))<<endl;
}

int main(){
    int V = 9;
    calcValuesWheelGraph(V);
    return 0;
}

실행 결과

The Diameter of the Wheel Graph is 2
The number of cycles of the Wheel Graph is 57
The number of Edges of the Wheel Graph is 16

위 실행 결과에서 정점 V = 9인 휠 그래프의 경우, 지름은 2, 사이클 수는 9² − 3×8 = 57개, 간선 수는 2×8 = 16개로 계산된 것을 확인할 수 있습니다. 이처럼 공식만 활용하면 복잡한 그래프 탐색 없이도 휠 그래프의 속성을 빠르게 구할 수 있습니다.