C++でホイールグラフの直径・閉路数・辺数を求めるプログラム

はじめに

この記事では、ホイールグラフ（Wheel Graph）の頂点数が与えられたときに、その直径・閉路の数・辺の数を求めるC++プログラムの作成方法を解説します。

問題の概要： n個の頂点を持つホイールグラフについて、閉路の総数、辺の総数、そして直径を計算する必要があります。

ホイールグラフとは

まず、ホイールグラフの基本について理解しておきましょう。

ホイールグラフは、サイクルグラフ C_n-1 に新しい頂点を1つ追加することで得られるグラフです。この新しく追加された頂点はハブ（Hub）と呼ばれ、サイクル上のすべての頂点と接続されます。車輪のように見えることから「ホイールグラフ」という名前が付いています。

以下は、7つの頂点を持つホイールグラフの例です。

各用語の定義

ホイールグラフの直径

直径とは、ある頂点から別の頂点へ移動する際に通過する必要がある辺の本数の最大値です。上記のホイールグラフの場合、直径は2となります。

ホイールグラフの閉路の数

閉路の数とは、グラフ内に存在する閉じた経路（サイクル）の総数です。上記の7頂点のホイールグラフの場合、閉路の数は31になります。

ホイールグラフの辺の数

辺の数とは、すべての頂点を接続している辺の総数です。上記のホイールグラフの場合、辺の数は12本です。

解決アプローチ

この問題は、グラフ理論で知られている直接的な公式を使用することで効率的に解くことができます。ホイールグラフの性質から導かれた以下の公式を使いましょう。

直径の公式

頂点数が4の場合は1、それ以外の場合は2

閉路の数の公式

(頂点数)^2 − (3 × (頂点数 − 1))

辺の数の公式

2 × (頂点数 − 1)

プログラムの実装例

以下は、これらの公式を実装したC++プログラムです。

#include <iostream>
#include <math.h>
using namespace std;
void calcValuesWheelGraph(int V){
    // 直径の計算
    if(V == 4){
        cout<<"ホイールグラフの直径は 1 "<<endl;
    }
    else {
        cout<<"ホイールグラフの直径は 2 "<<endl;
    }
    // 閉路の数の計算
    cout<<"ホイールグラフの閉路の数は "<<(pow(V, 2) - (3 * (V-1)))<<endl;
    // 辺の数の計算
    cout<<"ホイールグラフの辺の数は "<<(2 * (V-1))<<endl;
}
int main(){
    int V = 9;
    calcValuesWheelGraph(V);
    return 0;
}

実行結果

ホイールグラフの直径は 2
ホイールグラフの閉路の数は 57
ホイールグラフの辺の数は 16

まとめ

このように、グラフ理論の公式を活用すれば、ホイールグラフの直径・閉路の数・辺の数を頂点数だけから簡単に計算できます。プログラムの計算量はO(1)であり、非常に効率的な解法となっています。9頂点の場合、直径は2、閉路の数は57、辺の数は16という結果が得られました。