Make a tree with n vertices , d diameter and at most vertex degree k | C ++ implementation of the approach ; Function to Make a tree with n vertices , d as it 's diameter and degree of each vertex is at most k ; If diameter > n - 1 impossible to build tree ; To store the degree of each vertex ; To store the edge between vertices ; To store maximum distance among all the paths from a vertex ; Make diameter of tree equals to d ; Add an edge between them ; Store maximum distance of each vertex from other vertices ; For next ( n - d - 1 ) edges ; If the vertex already has the degree k ; If not possible ; Increase the degree of vertices ; Add an edge between them ; Store the maximum distance of this vertex from other vertices ; Print all the edges of the built tree ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void Make_tree ( int n , int d , int k ) { if ( d > n - 1 ) { cout << " No " ; return ; } vector < int > deg ( n ) ; vector < pair < int , int > > ans ; set < pair < int , int > > q ; for ( int i = 0 ; i < d ; ++ i ) { ++ deg [ i ] ; ++ deg [ i + 1 ] ; if ( deg [ i ] > k deg [ i + 1 ] > k ) { cout << " NO " << endl ; return ; } ans . push_back ( make_pair ( i , i + 1 ) ) ; } for ( int i = 1 ; i < d ; ++ i ) q . insert ( make_pair ( max ( i , d - i ) , i ) ) ; for ( int i = d + 1 ; i < n ; ++ i ) { while ( ! q . empty ( ) && deg [ q . begin ( ) -> second ] == k ) q . erase ( q . begin ( ) ) ; if ( q . empty ( ) || q . begin ( ) -> first == d ) { cout << " No " ; return ; } ++ deg [ i ] ; ++ deg [ q . begin ( ) -> second ] ; ans . push_back ( make_pair ( i , q . begin ( ) -> second ) ) ; q . insert ( make_pair ( q . begin ( ) -> first + 1 , i ) ) ; } for ( int i = 0 ; i < n - 1 ; ++ i ) cout << ans [ i ] . first + 1 << " ▁ " << ans [ i ] . second + 1 << endl ; } int main ( ) { int n = 6 , d = 3 , k = 4 ; Make_tree ( n , d , k ) ; return 0 ; }