Gráfico de rueda: un gráfico de rueda es un gráfico formado al conectar un solo vértice universal a todos los vértices de un ciclo. Propiedades:-
- Los gráficos de ruedas son gráficos planos.
- Siempre hay un ciclo hamiltoniano en el gráfico de rueda.
- Número cromático es 3 y 4, si n es par e impar respectivamente.
Declaración del problema: dado el número de vértices en un gráfico de rueda. La tarea es encontrar:
- El número de ciclos en el gráfico de la rueda.
- Número de aristas en Wheel Graph.
- El diámetro de un gráfico de rueda.
Ejemplos:
Input: vertices = 4 Output: Number of cycle = 7 Number of edge = 6 Diameter = 1 Input: vertices = 6 Output: Number of cycle = 21 Number of edge = 10 Diameter = 2
Ejemplo #1: Para vértices = Gráfico de 4 ruedas, el ciclo total es 7 :
Ejemplo #2: Para vértices = 5 y 7 Rueda Gráfico Número de aristas = 8 y 12 respectivamente:
Ejemplo #3: Para vértices = 4, el Diámetro es 1 ya que podemos pasar de cualquier vértice a cualquier vértice cubriendo solo 1 borde.
Fórmula para calcular los ciclos, aristas y diámetro:-
Number of Cycle = (vertices * vertices) - (3 * vertices) + 3 Number of edge = 2 * (vertices - 1) Diameter = if vertices = 4, Diameter = 1 if vertices > 4, Diameter = 2
A continuación se muestra la implementación requerida:
C++
// C++ Program to find the diameter, // cycles and edges of a Wheel Graph #include <bits/stdc++.h> using namespace std; // Function that calculates the // Number of Cycle in Wheel Graph. int totalCycle( int vertices) { int result = 0; // calculates no. of Cycle. result = pow (vertices, 2) - (3 * vertices) + 3; return result; } // Function that calculates the // Number of Edges in Wheel graph. int Edges( int vertices) { int result = 0; result = 2 * (vertices - 1); return result; } // Function that calculates the // Diameter in Wheel Graph. int Diameter( int vertices) { int result = 0; // calculates Diameter. if (vertices == 4) result = 1; else result = 2; return result; } // Driver Code int main() { int vertices = 4; cout << "Number of Cycle = " << totalCycle(vertices) << endl; cout << "Number of Edges = " << Edges(vertices) << endl; cout << "Diameter = " << Diameter(vertices); return 0; } |
Java
//Java Program to find the diameter, // cycles and edges of a Wheel Graph import java.io.*; class GFG { // Function that calculates the // Number of Cycle in Wheel Graph. static int totalCycle( double vertices) { double result = 0 ; int result1 = 0 ; // calculates no. of Cycle. result = Math.pow(vertices, 2 ) - ( 3 * vertices) + 3 ; result1 = ( int )(result); return result1; } // Function that calculates the // Number of Edges in Wheel graph. static int Edges( int vertices) { int result = 0 ; result = 2 * (vertices - 1 ); return result; } // Function that calculates the // Diameter in Wheel Graph. static int Diameter( int vertices) { int result = 0 ; // calculates Diameter. if (vertices == 4 ) result = 1 ; else result = 2 ; return result; } //Driver Code public static void main(String[] args) { int vertices = 4 ; System.out.println( "Number of Cycle = " + totalCycle(vertices)); System.out.println( "Number of Edges = " + Edges(vertices)); System.out.println( "Diameter = " + Diameter(vertices)); } } |
Python3
# Python3 Program to find the diameter, # cycles and edges of a Wheel Graph # Function that calculates the # Number of Cycle in Wheel Graph. def totalCycle(vertices): result = 0 # calculates no. of Cycle. result = ( pow (vertices, 2 ) - ( 3 * vertices) + 3 ) return result # Function that calculates the # Number of Edges in Wheel graph. def Edges(vertices): result = 0 result = 2 * (vertices - 1 ) return result # Function that calculates the # Diameter in Wheel Graph. def Diameter(vertices): result = 0 # calculates Diameter. if vertices = = 4 : result = 1 else : result = 2 return result # Driver Code if __name__ = = "__main__" : vertices = 4 print ( "Number of Cycle =" , totalCycle(vertices)) print ( "Number of Edges =" , Edges(vertices)) print ( "Diameter =" , Diameter(vertices)) # This code is contributed by Rituraj Jain |
C#
// C# Program to find the diameter, // cycles and edges of a Wheel Graph using System; class GFG { // Function that calculates the // Number of Cycle in Wheel Graph. static int totalCycle( double vertices) { double result = 0; int result1 = 0; // calculates no. of Cycle. result = Math.Pow(vertices, 2) - (3 * vertices) + 3; result1 = ( int )(result); return result1; } // Function that calculates the // Number of Edges in Wheel graph. static int Edges( int vertices) { int result = 0; result = 2 * (vertices - 1); return result; } // Function that calculates the // Diameter in Wheel Graph. static int Diameter( int vertices) { int result = 0; // calculates Diameter. if (vertices == 4) result = 1; else result = 2; return result; } // Driver Code public static void Main() { int vertices = 4; Console.WriteLine( "Number of Cycle = " + totalCycle(vertices)); Console.WriteLine( "Number of Edges = " + Edges(vertices)); Console.WriteLine( "Diameter = " + Diameter(vertices)); } } // This code is contributed by inder_verma |
PHP
<?php // PHP Program to find the diameter, // cycles and edges of a Wheel Graph // Function that calculates the // Number of Cycle in Wheel Graph. function totalCycle( $vertices ) { $result = 0; // calculates no. of Cycle. $result = pow( $vertices , 2) - (3 * $vertices ) + 3; return $result ; } // Function that calculates the // Number of Edges in Wheel graph. function Edges( $vertices ) { $result = 0; $result = 2 * ( $vertices - 1); return $result ; } // Function that calculates the // Diameter in Wheel Graph. function Diameter( $vertices ) { $result = 0; // calculates Diameter. if ( $vertices == 4) $result = 1; else $result = 2; return $result ; } // Driver Code $vertices = 4; echo "Number of Cycle = " , totalCycle( $vertices ), "\n" ; echo "Number of Edges = " , Edges( $vertices ), "\n" ; echo "Diameter = " , Diameter( $vertices ); // This code is contributed by inder_verma ?> |
Number of Cycle = 7 Number of Edges = 6 Diameter = 1
Publicación traducida automáticamente
Artículo escrito por Naman_Garg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA