Exercise $2$

In this exercise you will examine how the rules $($A$)$ and $($B$)$ can be translated into constraints for a linear programming problem. Furthermore you will find the objective function we wish to maximize.

We begin by introducing some notation. Let V denote the set of all vertices in the

ring system. E denotes the set of all bonds $($edges$),$ and H is the set of hexagons in the

system. For a vertex v in V we let E$($v$)$ be the set of bonds incident with this vertex,

i$.$e$.,$ all bonds that connect v to another vertex. Finally for each hexagon hi

in H we let

$1$

$2$

$3$

$4$

$5$

$6$

$7$

$8$

$9$

$10$

$11$

$12$

$13$

$15$

e$1$ e$2$ e$3$ e$4$ e$5$ e$6$

e$15$ e$14$ e$12$ e$11$ e$9$ e$8$

e$16$ h e$13$ e$10$ e$71$ h$2$ h$3$

Figure $2$: A tricyclic aromatic hydrocarbon. The prefix v$$s at the vertices have been

omitted for readability. With the right placement of double bonds this structure is called

anthracene