graph theory is an important part of mathematics and computer science. to many such problems, exact solutions do exist. many times however, they are very hard to calculate. therefore, very often, approximations are used. there are two kinds of such approximations, monte-carlo algorithms and las-vegas algorithms.