Total number of Spanning trees in a Cycle Graph - Coding

Given the number of vertices in a Cycle graph. The task is to find the Total number of Spanning trees possible.

Note: A cycle/circular graph is a graph that contains only one cycle. A spanning tree is the shortest/minimum path in a graph that covers all the vertices of a graph.

Examples:

Input: Vertices = 3
Output: Total Spanning tree = 3

Input: Vertices = 4
Output: Total Spanning tree = 4

Example 1:

For Cycle Graph with vertices = 3

Spanning Tree possible is 3

Example 2:
For Cycle Graph with vertices = 4

Spanning Tree possible is 4

So, the number of spanning trees will always be equal to the number of vertices in a cycle graph.

Implementation:

C++

<?php
// PHP program to find number of
// spanning trees
 
// function that calculates the
// total Spanning tree
function Spanning($vertices)
{
    $result = 0;
 
    $result = $vertices;
    return $result;
}
 
// Driver code
$vertices = 4;
 
echo "Spanning tree = " . 
     Spanning($vertices);
      
// This code is contributed 
// by Ankita Saini
?>

Javascript

<script>
 
// Javascript program to find number of
// spanning trees
 
// Function that calculates the
// total Spanning tree
function Spanning(vertices)
{
    result = 0;
    result = vertices;
    return result;
}
 
// Driver code
var vertices = 4;
document.write("Spanning tree = " + 
               Spanning(vertices));
 
// This code is contributed by noob2000
 
</script>

Output

Spanning tree = 4

Time Complexity: O(1)
Auxiliary Space: O(1)

Reffered: https://www.geeksforgeeks.org

Graph

Related
Program to Calculate the Edge Cover of a Graph
Program to find total number of edges in a Complete Graph
Maximum Possible Edge Disjoint Spanning Tree From a Complete Graph
Level Ancestor Problem
Product of lengths of all cycles in an undirected graph

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	8