Posted on

try to construct a working algorithm. It’s hard

In general there certain methods that (almost) always work and give nice solution in maths,engineering. For example take the method of trial and error. In my case for Graph theory problems these are:

1) Induction

2) Add/delete a node and figure out what is the logical flaw

3) Search using the concepts of minimum and maximum (usually gives beautiful solution)

4) Construct and algorithm

For me number 4 is really hard and this demands many  time and work. A good application must have a criterion that is applied recursively in every partition of the sets that occur each time. The procedure must stop after some steps and we have to be sure that this happens. The condition must be chosen properly so that it defines an equivalence relation

Partioning a set of vertices with a condition related to the problem.

Partitioning a set of vertices with a condition related to the problem.

Anyway, the problem that inspired me for this thought (and applied successfully both 3) and 4) )  was the following:

Problem: Given n > 4 points, show that you can place an arrow between each pair of points, so that given any point you can reach any other point by travelling along either one or two arrows in the direction of the arrow.

Unknown's avatar

About zeracuse

let it be !

Leave a comment