This is HW1 * (a) Directed in tree are directed tree where all path goes from the leaf to the root. * (b) Directed out tree are directed tree where all the path goes from the root to the leaf. * (c) Fundamental cycle: Given a spanning tree, adding any edge will create a cycle on the tree, and that is a fundamental cycle. Take note that the cycle doesn't have to be directed, see page 26 for the definition of a cycle. * (d) Foundamental cut: Given a spanning tree, removing any edge will break the tree apart, forming 2 subset of vertices that is the cut.

Tree: Page 30

Figure 2.28

closed directed walk: A walk that starts and end on the same vertex.

• Walk has odd number of arcs => It contains an odd directed cycle in it.
• Walk has even number of arcs => It contains an even direct cycle in it?

What does it mean to have a walk containing "n" number of arcs? If the arcs repeats in the graph, do we need to count it again?

If \(d\) is the max degree of vertices in a tree, then the tree contains at least \(d\) many vertices with degree 1.

To consider the problem, we consider the worse case where he number of degree one vertices equals to the maximum degree of the tree.

I don't understand the hint and an inductive argumet works for me.

Do this one.

Proof by contradiction is the simplest way to go I think.

The key is that a cycle is a path that doesn't walk over the same arc more than once.

Take note that, if arc \((i, j)\) belongs to a cycle in \(G\), it doesn't say anything about whether \(G\) is connected or not. If it's not connected, then removing an arc is still connected. Therefore I think this question is assuming that the graph is connected when proving it in both directions.

Circulation problem is where the mass balance on the vertices are always zero, but this problem is an assignment problem, not circulation. 1. We are minimizing the resource commitment. If a car is used for a shift, it can be used again for another shift, but that will count towards the objective as an extra commitment. 2. When we assign a police car, it can come frome the reserve of a precinct, OR, a previous shift of the day. 3. The mass balance constraints resembles circulation because we are not destroying police cars.

non-isomorphic: Not the same tree by re-arranging the vertices, permuting the vertices, (but the arcs still stick to the same vertex).