human
What is a code to make a tree with n vertices , d diameter and at most vertex degree k and the other steps required given the following:
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"
Solution in Python:
assistant
#Here is code to make a tree with n vertices , d diameter and at most vertex degree k and the other steps required.
 def Make_tree ( n , d , k ) :
	if ( d > n - 1 ) :
		print ( " No " )
		return
	deg = [ 0 ] * ( n )
	ans = [ ]
	q = { }
	for i in range ( d ) :
		deg [ i ] += 1
		deg [ i + 1 ] += 1
		if ( deg [ i ] > k or deg [ i + 1 ] > k ) :
			print ( " NO " )
			return
		ans . append ( ( i , i + 1 ) )
	for i in range ( 1 , d ) :
		q [ ( max ( i , d - i ) , i ) ] = 1
	for i in range ( d + 1 , n ) :
		arr = list ( q . keys ( ) )
		while ( len ( q ) > 0 and deg [ arr [ 0 ] [ 1 ] ] == k ) :
			del q [ arr [ 0 ] ]
		if ( len ( q ) == 0 or arr [ 0 ] [ 0 ] == d ) :
			print ( " No " )
			return
		deg [ i ] += 1
		deg [ arr [ 0 ] [ 1 ] ] += 1
		ans . append ( ( i , arr [ 0 ] [ 1 ] ) )
		q [ ( arr [ 0 ] [ 0 ] + 1 , i ) ] = 1
	for i in range ( n - 1 ) :
		print ( ans [ i ] [ 0 ] + 1 , ans [ i ] [ 1 ] + 1 )
if __name__ == ' _ _ main _ _ ' :
	n , d , k = 6 , 3 , 4
	Make_tree ( n , d , k )