Project 2The subject of this project is to create an implementation of the Nagamochi-Ibaraki algorithm (see in the lecture notes) for finding a minimum cut in anundirected graph, and experiment with it.Tasks:1. Explain how your implementation of the algorithm works. Providepseudo code for the description, with sufficient comments to make itreadable and understandable by a human.2. Write a computer program that implements the algorithm. You mayuse any programming language under any operating system, this isentirely of your choice.3. Run the program on randomly generated examples. Let the numberof nodes be fixed at n = 20, while the number m of edges will varybetween 40 and 400, increasing in steps of 5. Once a value of m isselected, the program creates a graph with n = 20 nodes and m edges.The actual edges are selected randomly among all possible ones, withparallel edges allowed, but self-loops are excluded.4. Experiment with your random graph examples to find an experimen-tal connection between the average degree of the graph and its edge-connectivity λ(G). (If the graph happens to be disconnected, then takeλ(G) = 0.) How does the connectivity depend on the average degree?(Note that the average degree in a graph characterizes the density ofthe graph, as it is expressible as d = 2m/n , where m, n are the numberof edges and nodes, respectively.) Show the found relationship graphi-cally in a diagram, exhibiting λ(G) as a function of the average degreed, while keeping n = 20 fixed.5. Let us call an edge critical, if its deletion decreases the connectivity.That is, an edgeeis critical, ifλ(G−e)< λ(G), whereG−edenotes thegraph G with edge e deleted. Let C(G) denote the number of criticaledges in graph G. Using the random graphs generated above, show an1experimental relationship between the number of critical edges and theaverage degree d of the graph. That is, show C(G) graphically as thefunction of d, while keeping n = 20 fixed.6. Give a short explanation why the functions found in items 4 and 5 lookthe way they look. In other words, try to argue that they indeed showthe behavior that can be intuitively expected, so your program is likelyto work correctly. Note that it is part of your task to find out whatbehavior can be expected.Important note: If there is anything that is not specified in this projectdescription, that automatically means it is left to your choice.Submission guidelinesDescribe everything, including algorithms, program, results and figures neatlyand clearly in a study. Include everything in a single document that can beread as a report and submit it through eLearning. (Do not send it via e-mail!) Do not include executable code, but include the source code in anappendix to the study. Your submission will be read as a report, but usuallywe do not run the program. On the other hand, if either there are signs ofnon-original work or if you want to dispute the received score, then you willbe asked to demonstrate your program on a computer, show and explain itsdetails.Notes:• The work must be fully individual and original. Any form of cheat-ing is a serious violation of University policies and can lead to seriousconsequences.• It may be helpful to think about the whole project presentation thatyour task is not only to solve a technical problem, but you also haveto “sell” the results. Try to look at your work from the viewpointof a potential “customer”, who either wants to buy such a software,or perhaps wants to hire somebody to carry out similar tasks. Howconvincing would your presentation look for such a
View Full Document
Unlocking...