# Summer School 2016

• Road map of Hungary (in LGF format)
• There are three versions:
• The description of the LGF format can be found here: http://lemon.cs.elte.hu/pub/doc/1.3/a00002.html
• The file contains the following attributes:
• in the `@nodes` section:
• `label`: the node label, >= 1 integer numbers
• `lat`: the latitude of the node, floating point number
• `lon`: the longitude of the node, floating point number
• in the `@arcs` section:
• `length`: The length of the road, in meter (integer number)
• `maxspeed`: The maximum allowed speed , in km/h (integer number)
• Planar graph test examples: planar-graphs.zip
• The file contains the following attributes:
• in the `@nodes` section:
• `cost`: cost of the nodes (integer number)
• `label`: the node label, >= 0 integer numbers
• `coordinates_x` and `coordinates_y`: the coordinates of the nodes, floating point number
• in the `@arcs` section (in `*-c.lgf` files only)
• `capacity`: capacity of the arcs (integer number)
• `cost`: cost of the arcs (integer number)
• Homeworks
• Is there a polynomial algorithm for finding the 1002 long sequence surely opening any three digit door?
• Or just a short proof that it exists?
• Find the two places in Hungary that are the farthest away from each other.
• Find a small cardinality/cost vertex set covering all edges in the above graphs.