Make a tree with n vertices , d diameter and at most vertex degree k | 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 ; Prall the edges of the built tree ; Driver code
def Make_tree ( n , d , k ) : NEW_LINE INDENT if ( d > n - 1 ) : NEW_LINE INDENT print ( " No " ) NEW_LINE return NEW_LINE DEDENT deg = [ 0 ] * ( n ) NEW_LINE ans = [ ] NEW_LINE q = { } NEW_LINE for i in range ( d ) : NEW_LINE INDENT deg [ i ] += 1 NEW_LINE deg [ i + 1 ] += 1 NEW_LINE if ( deg [ i ] > k or deg [ i + 1 ] > k ) : NEW_LINE INDENT print ( " NO " ) NEW_LINE return NEW_LINE DEDENT ans . append ( ( i , i + 1 ) ) NEW_LINE DEDENT for i in range ( 1 , d ) : NEW_LINE INDENT q [ ( max ( i , d - i ) , i ) ] = 1 NEW_LINE DEDENT for i in range ( d + 1 , n ) : NEW_LINE INDENT arr = list ( q . keys ( ) ) NEW_LINE while ( len ( q ) > 0 and deg [ arr [ 0 ] [ 1 ] ] == k ) : NEW_LINE INDENT del q [ arr [ 0 ] ] NEW_LINE DEDENT if ( len ( q ) == 0 or arr [ 0 ] [ 0 ] == d ) : NEW_LINE INDENT print ( " No " ) NEW_LINE return NEW_LINE DEDENT deg [ i ] += 1 NEW_LINE deg [ arr [ 0 ] [ 1 ] ] += 1 NEW_LINE ans . append ( ( i , arr [ 0 ] [ 1 ] ) ) NEW_LINE q [ ( arr [ 0 ] [ 0 ] + 1 , i ) ] = 1 NEW_LINE DEDENT for i in range ( n - 1 ) : NEW_LINE INDENT print ( ans [ i ] [ 0 ] + 1 , ans [ i ] [ 1 ] + 1 ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n , d , k = 6 , 3 , 4 NEW_LINE Make_tree ( n , d , k ) NEW_LINE DEDENT