We knowthatevenwithoutrecognizing previouslyseen nodes,genericsearch willalwaysterminateonadirectedacyclicgraphwithfinitelymanynodes. We'dliketo know howlongitmight run beforeterminating onsuchagraphwithnnodes.

(a)Provethat every event when anewnodeisplacedon theopenlistcanbeassociated withadifferent pathinthe graphstartingfromthestartnode.

(b)Provethatwithnogoal node,and withoutrecognizingpreviously seen nodes, generic searchwillplace a nodeon theopenlistforeverypath inthegraphstartingfromthestartnode.

(c)Provethat for anynaturaln,thereisanumber,dependingonn,thatlimitsthenumberof suchpathsinan n-nodegraphsatisfying theseconditions.

(d)Explain howwecanusegenericsearch, withoutrecognizing previously seen nodes,to determine whetheragivendirected graph has a cycle.(Assumethat weknowthenumberofnodes.)