Cho số đỉnh V của đồ thị bánh xe (Wheel Graph). Tìm đường kính, số chu trình, số cạnh.
Công thức: - Đường kính = 1 nếu V=4, ngược lại 2. - Số chu trình = V² - 3*(V-1). - Số cạnh = 2*(V-1).
Ví dụ: V=9 → Đường kính=2, Chu trình=57, Cạnh=16.
Giải thuật
- Áp dụng trực tiếp các công thức lý thuyết đồ thị cho Wheel Graph.
- Đường kính: trung tâm kết nối mọi đỉnh, nên đường kính ≤ 2.
- Số chu trình và cạnh suy ra từ cấu trúc: chu trình ngoài V-1 đỉnh + trung tâm.
Ví dụ mã C++
#include <iostream>
#include <math.h>
using namespace std;
void calcValuesWheelGraph(int V){
if(V == 4) cout<<"The Diameter of the Wheel Graph is 1 "<<endl;
else cout<<"The Diameter of the Wheel Graph is 2 "<<endl;
cout<<"The number of cycles of the Wheel Graph is "<<(pow(V, 2) - (3 * (V-1)))<<endl;
cout<<"The number of Edges of the Wheel Graph is "<<(2 * (V-1))<<endl;
}
int main(){
int V = 9;
calcValuesWheelGraph(V);
return 0;
}
Đầu vào
9
Đầu ra
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