Trong bài toán này, chúng ta được cung cấp một số biểu thị số đỉnh của Đồ thị bánh xe. Nhiệm vụ của chúng tôi là tạo một Chương trình để tìm đường kính, chu kỳ và cạnh của Đồ thị bánh xe trong C ++ .
Mô tả sự cố - Ở đây, chúng ta cần tìm số chu kỳ, số cạnh và đường kính của Đồ thị bánh xe với n đỉnh.
Trước tiên, hãy hiểu một số khái niệm cơ bản về Đồ thị bánh xe -
Đồ thị bánh xe thu được từ đồ thị chu trình Cn-1 bằng cách thêm một đỉnh mới. Đỉnh mới đó được gọi là Trung tâm được kết nối với tất cả các đỉnh của Cn.
Ví dụ về biểu đồ bánh xe có 7 đỉnh.
Đường kính của biểu đồ bánh xe là số cạnh mà chúng ta cần che để đi từ bất kỳ đỉnh nào sang đỉnh khác. Đối với Đồ thị bánh xe ở trên, đường kính 2
Không. của Đồ thị chu kỳ của bánh xe là tổng số chu kỳ đóng có thể là đồ thị đã cho. Đối với Đồ thị Bánh xe ở trên, không. của chu kỳ là 31.
Không. of Edge of Wheel Graph là số cạnh nối tất cả các đỉnh. Đối với Đồ thị bánh xe ở trên, không có cạnh nào là 12.
Phương pháp tiếp cận giải pháp
Để giải quyết vấn đề, chúng tôi sẽ sử dụng công thức trực tiếp được đưa ra trong lý thuyết đồ thị để tìm các giá trị cần thiết cho biểu đồ bánh xe.
Công thức là,
Đường kính của biểu đồ bánh xe =
1, if vertices = 4, else 2.
Không. số chu kỳ của Đồ thị bánh xe =
(No. of vertices )^2 - (3 * (No. of vertices -1) )
Không. của các cạnh của bánh xe Đồ thị =
2 * (No. of vertices - 1)
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầ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