CHAPTER 3: Algorithms Flashcards

Question 1

Q

Weights

Answer

A

consider pairs (bold(G),w) where bold(G) = (V,E) is a connected graph and 
w: E → N_0.

For each edge e∈E, the quantity w(e) is called the weight of e

Given a set S of edges

The weight of S:

w(S) = sum of e∈S of [w(e)]

Question 2

Q

TREE

Answer

A

connected graph without cycles

Question 3

Q

ISOMORPHISM CLASSES OF TREES ON n-VERTICES

Answer

A

counting isomers ie these aren’t isomorphisms to each other (they are classes of different types)

n = 1
•
n = 2
•-•
n = 3      \_\_
              |    |
•-•-•       •-• •
(1,2,1)  ~(2,1,1)

(does this count as 1-YES)

n = 4
•-•-•-•       •
                 >•-•
                •
(1,2,2,1)  (1,1,3,1)

n = 5
                                    •
•-•-•-•-•     •                  |
                  >•-•-•       •-•-•
                 •                  |
                                    •

(1,2,2,2,1) (1,1,3,2,1) (1,1,1,1,4)

8??

Question 4

Q

LABELLED TREES: KILLING ISOMORPHISMS

Answer

A

n=1
•1
n=1
•1-•2

n=3
•1-•2-•3
•2-•1-•3
•1-•3-•2
3 labelled trees :

n=4
•-•-•-•
has 4!/2=12 different labelled trees

(4! ways to label but some same graph due to symmetries)

  •
  |
  •
 / \
•   •

only choosing the middle number and permute the other 3
4!/3!=4 labelled trees

16 labelled trees

Question 5

Q

IN GENERAL LABELLED TREES WITH N VERTICES

Answer

A

(n!)/ |Automorphism group of T|

IN GENERAL LABELLED TREES WITH n VERTICES

(n!)/(#symmetris)

n=5
•-•-•-•-• 120/2=60

  •
  |
  •
  |
  •
 / \
•  •   20/2=60

   •
   |
•-•-•
   |
   •  5!/4!=3
---
125 labelled trees

Question 6

Q

unlabelled vs labelled trees

Answer

A

n: unlabelled:labelled
1: 1:1
2: 1:1
3: 1:3
4: 2:16
5: 3:125
6: 6:1296
7: 11:16807

*vertices are no longer interchangeable once labelled this implies that are n! ways to label an unlabelled tree minus the symmetries

Question 7

Q

CAYLEYS FORMULA

Answer

A

n^(n-2) labelled trees on n vertices

Question 8

Q

Pr¨ufer code

Answer

A

a unique sequence associated with a labelled tree

Definition3.4.4
Prüfer code If record the edges of a tree
T as in the Pruning Algorithm, the first n−2 number appear in the top row is the Prüfer code of T

A labelled trees Pr¨ufer code is obtained: by removing the leaf with the smallest label and set the ith element of the prufer sequence to be the label of this lease neighbour. for a labelled tree this is unique and has length n-2
the proof of code is in bijection and we can construct the tree from the code
prufer codes can be used to prove Curley’s formula
some form will be on the exam

Question 9

Q

PR¨UFER CODE:

algorithm

Answer

A

1) find the lowest leaf l of T
2) record Edge e connecting it to the rest of the tree
3) delete l & e to get a simpler tree T’
4) repeat process with T’
* no number will appear twice in the bottom row

Output: A 2×n−1 table with entries in {1,…,n} that records the edges of T in a specified order.

Find the leaf v with the lowest label; it will have one edge e, connecting it to some vertex (its “parent”) w

Form a new tree T′ by deleting v and e, and record e in the output table, putting the deleted vertex
v in the bottom row and its parent w above it in the top row.

Question 10

Q

PR¨UFER CODE:

algorithm EXAMPLE

Answer

A

given 9 Vertex labelled tree, 8 edges

[7]\   [8]---[9]
      \  |
[4]---[5]    [6]
       / |      / |
[1 ]/   [2]/   [3]

Parent: 5|6|5|2|5|5|8|9|
Leaf: 1 |3|4|6|2|7|5|8|

1*removing Leaf i.e. Edge 1-5, leaves us with lowest leaves 3479- sometimes new leaves appear eg 2 only after 3 and 6(new leaf) removed

Question 11

Q

PR¨UFER CODE: A BIJECTION

Answer

A

we can construct the tree from the code:
given any sequence of n−2 numbers between 1 and n, we can construct a tree have that sequence as its Prüfer code.

Parent: 5|6|5|2|5|5|8|9|
Leaf: 1 |3|4|6|2|7|5|8|

any # appearing as a parent isn’t a leaf this implies one is the lowest # which doesn’t appear so it’s Leaf. The first we deleted. Than the next lowest number that isn’t a leaf. But we go deleting so next is 6.
finally numbers we have not used for edge col with 9 and 8 added

Question 12

Q

Given pru¨fer code example:

Answer

A

Parent: 4|2|2|8|8|3|7|9|
Leaf: | | | | | | | | |

*by Finding lowest # not in remaining code delete the first column and iterate , last 2 spaces left are last Edge

Parent: 4|2|2|8|8|3|7|9|
Leaf: 1|4|5|2|6|8|3|7|

drawing
tree with 9 vertices, leaves 1,5,6,9

**lowest number not in first row, ignore the previous top and bottom row numbers and write the lowest

Question 13

Q

CAYLEYS ENRICHMENT

Answer

A

Degree of vertex i=
#times i appears in table
= # times i appears in PRUFER CODE +1

Question 14

Q

COROLLARY labelled trees with degrees

Answer

A

the # of labelled trees on n vertices where for each i, Vertex i has degree d_i is

(n-2)!/ [pi (d_i-1)!]

*consistent with hand shaking

Question 15

Q

PRUFER CODE EXAMPLE:

Answer

A

Draw the tree whose Pr¨ufer code is (1, 1, 1, 1, 6, 5).

*The given Pr¨ufer code has six entries, therefore the corresponding
tree will have 6 + 2 = 8 entries.
The first number in the Pr¨ufer code is 1 and the lowest number not included in the Pr¨ufer code is 2, so we connect 1 to 2.

*We then drop the leading 1 in the code and put 2 at the back of the code:
(1, 1, 1, 6, 5, 2).
The first number in the code is still 1 and the lowest number not included is now
3, so we connect 1 to 3.

etc

*last numbers missing are 5 and 8 so we connect them

Parent: 1| 1| 1| 1|6|5|5|
Leaf: 2|3|4|7| 1|6|8|

1 connected to 2,7,3,4,6
then 6 connected to 5 which is connected to 8

ie leaves are 2,7,3,4,8

8 vertices

Question 16

Q

example degrees and trees

Answer

A

*trees on 6 vertices where vertices 1 and 3 have degree 3 everything else is a leaf

prufer code where
1 appears 3-1 = 2
3 appears 2-_ times

*1331,11331,3311,

4!/(2!2!) ways to arrange 4 #s

n-2 #s : ways to arrange two of each of two different #s

ie permute x2

Question 17

Q

prufer code and degree notes

Answer

A

for the table every column is an edge
so looking at the table (prev example) the degree of 5 is 5, as 5 appears 5 times
from the code 1 and 5 didn’t appear previously
two appears twice and has degree 3

Question 18

Q

SPANNING TREES

Answer

A

*minimal connected graphs and spanning trees are minimal subgraphs containing all vertices that are still connected

Let G be a connected graph. A spanning tree T of G is a subgraph T⊆ G st T is a tree and contains every Vertex of G.

*found by deleting edges and preserving connectedness

example 3 vertices triangle
spanning trees are ABC
st different edges but still connected
3 spanning trees: A-B-C C-A-B and A-C-B

Question 19

Q

Spanning trees of K_n

Answer

A

Spanning trees of K_n are the same as label trees on n vertices, i.e. any tree on the n vertices

K_5 is pentagon with star and a spanning tree is C_5 for example, others include any other edges st vertices are connected

Question 20

Q

weighted graph encoded:

[A]
[4][B]
[5][7][C]
[9][8][8][D]
[5][5][5][8][E]

Answer

A

[A]
[4][B]
[5][7][C]
[9][8][8][D]
[5][5][5][8][E]

drawing: edge from A-B weight 4, edge from A to C weight 5,…

pentagon with star in the middle ABCDE - ie complete
outside weights 4,7,8,8,5

Question 21

Q

Weighted graphs

Answer

A

cost associated to edge a weighted graph is a graph together with a weight function we assume the weight is bigger than or equal to 0 for all edges

for example we look for the cheapest way to connect all cities that is we look for its minimal spanning tree

checking every spanning tree is too slow
for example K_n has n^{n-2} spanning trees

Question 22

Q

KRUSKALS ALGORITHM

Answer

A

greedy algorithm- as we don’t plan ahead
avoids Cycles
looks at all edges at the start
T may be disconnected at intermediate steps

we start with t having no edges:
•look at cheapest remaining Edge e
•if adding e to T creates a loop discard e
•otherwise add e to T

Question 23

Q

KRUSKALS ALGORITHM: EXAMPLE

[A]
[4][B]
[5][7][C]
[9][8][8][D]
[5][5][5][8][E]

Answer

A

•cheapest edges:
AB costs 4
CE costs 5
BE costs 5
{WE costs 5 but loops,
AC costs 5 but loops,
BC costs 7 but loops}
DE costs 8

TOTAL COST= 4+5+5+8=22

Meanwhile drawing MST:

edges included and ensure its connected
THUS 22 is the total cost of the cheapest spanning tree

Question 24

Q

PRIMS ALGORTHIM

Answer

A

*start at one Vertex and explore

Start T=v, a single vertex, iteratively:
find the cheapest edge e=v-w from v ∈T to w∉T
add e & w to T

produces a spanning tree but is this minimal?

Question 25

Q

PRIMS ALGORTHIM: EXAMPLE

[A]
[4][B]
[5][7][C]
[9][8][8][D]
[5][5][5][8][E]

STARTING AT D

Answer

A

start at D:
•cheapest Edge out costs 8 (pick any one of the cheapest)
pick DB at random
•cheapest from D or B to New vertex:
BA costing 4
• cheapest from (A,B,D) to new:
(AC, AE or BE)
pick AC costing 5
• cheapest from (A,B,C,D) to E:
(AE, BE, CE) all cost 5

so 8+5+5+4=22 same minimal value but DIFFERENT MST than kruskals

Question 26

Q

Kruskal’s notes:

Answer

A

*Kruskal’s algorithm always finds a cheapest spanning tree:
Suppose we have a tree T from kruskal’s. let T_m be a minimum spanning tree. Need to show w(T)=w(T_m) over edges of w(e_i) ≤w(e_i)≤…≤…

(i.e. transform T to T_m edge by Edge, by exchange principal ,and show each step is a minimal spanning tree)

Let T be a spanning tree of G and e=xy an edge not in T. Then: unique path P from x to y using only edges of T. if f is any edge in P then T’=T\f∪e is a spanning tree

ie can exchange edges in P for e.

*always add cheapest edge in T but not in T_m

in T∪T_m will be loops: BDE

…..

Question 27

Q

*always add cheapest edge in T but not in T_m

in T∪T_m will be loops: BDE
continued

Answer

A

notes on proof:
??

drawn diagrams deleting edges, adding to get loops either adding edges or making loops

Exchange principle:
Let T be a spanning tree of G, and e = xy an edge not in T.
Then:
Unique path P from x to y using only edges of T I If f any edge in P, then T0 = T \f ∪e a spanning tree i.e., can exchange edges in P for e.

Basic idea of proofs:

Let T be spanning tree produced by algorithm I Let Tm be a minimal spanning tree
Transform Tm to T edge by edge using exchange principle
Show each step is a minimal spanning tree

Key: always add cheapest edge in T but not Tm.

Question 28

Q

cheapest spanning tree

Answer

A

2 greedy algorithms:
Kruskal: add cheapest edge that doesn’t make a loop

Prims: start at v, add cheapest edge to the new vertex

*not immediately clear they find MST but proof wont be on the exam

Question 29

Q

paths

Answer

A

TSP- visiting every vertex and returning
shortest paths
longest paths

Question 30

Q

Directed graph

Answer

A

A directed graph is one where each edge has a chosen starting and ending point, usually indicated with arrows.

*walks on directed graphs can only follow that direction

Question 31

Q

Finding all minimal spanning trees
All edges have distinct weights:

All edges have the same weight:

A few edges have repeated weights:

Answer

A

All edges have distinct weights:

- Never have to make an arbitrary choice
- Unique minimal weight spanning tree

All edges have the same weight:

- Any spanning tree is minimal
*Probably too many to write down

A few edges have repeated weights:

- Only a few places we have to make a choice
- Can ﬁnd them with case by case analysis breaking ties

Question 32

Q

Dijkstra’s algorithm

Answer

A

Dijkstra’s algorithm for shortest path

cant have negative edge weights

Input: A weighted (possibly directed) graph G and starting vertex v ∈ G

output:
For every vertex w ∈ G a list of all shortest paths from v to w

Initialize:
From starting vertex v list every edge out of v as a potential shortest path to corresponding vertex w

Iterate:

*Choose w with cheapest potential shortest path and make these paths permanent
- Update list of potential paths by adding edges out of w to the shortest paths to w and checking if they’re cheaper than known paths

Question 33

Q

Example graph from the 2008 Exam

Directed graph edges
SB 7
SA 11
BA 3
AD 6
BD 10
DC 4
AC 10
CF 5
DF 9
CE 10
FE 3
ET 7
FT 11

Answer

A

marking route on graph S to T

writing:
possible paths
setting cheapest possible path as permanent

Step 1: possible paths from S
SB 7**** chosen
SA 11
Step 2: possible out of B,chosen
SA 11 but SBA 10****
                SBD 17

Step 3:possible out of A
SBAD 16**
SBAC 20 SBADC 20
SBADF 25

Step 4: out of C
SBADF *
SBACF *
SBADCF all cost 25***

S..CE= 20+10 = 30

Step 5: New record for S-E
S_{3 ways} FE 28**
S_{3 ways} FT 36

Step 6:
S..ET cost 28+7=35 less than 36

cheapest path:
SB 7
SBA 10
SBAD 16
SBAC or SBADC 20

SF = 25 in 3 ways
S_(3 ways) FE 28
S_ .. ET 35
….
SBACFET
SBADFET
SBADCFET

Question 34

Q

Add on:

Which edges if made a little longer would make the distance from S to T longer?

in example

Answer

A

General answer: Edges In all shortest paths:
these are:
always
SB, BA,FE,ET

sometimes:
AC
AD
CE
CF
DF

Question 35

Q

Which edges if made a little shorter would make the distance from S to T shorter?

Answer

A

Any edge in any shortest path

eg
both 
SB 
BA
AC 
 AD
CE 
 DF
CF
FE 
 ET

Question 36

Q

NOTES ON DIJKSTRAS ALGORITHM:

Answer

A

Suppose we’re at the step were Dijkstra’s decides the cheapest path to w.

Then:
A cheaper path to w would have to go through a vertex u we haven’t found the cheapest path to yet.

But! Even getting to u costs more than our cheapest path to w.

An observation: Dijkstra’s algorithm depends on the edge weights being non-negative!

optimal- if all we know is a weighted graph cant improve col
not good In practical as every edge considered
driving distances
A* algorithm avoids searching London: Supposes we have an easy to calculate “heuristic distance” h(v,w), that is a lower bound for the actual distance d(v,w).

Question 37

Q

Finding the longest path

Answer

A

Scheduling a large problem with many parts For example, building a house.

Some can be done at same time: (ﬁnishing interior rooms)
Some need to be done in order: (foundation before walls)
How early could whole project be ﬁnished?

Solution: longest path
* Encode tasks as edges in directed weighted graph

Edge e follows edge f if task f requires task e
Length of longest path is the shortest time to complete project

Building the directed graph from a list of tasks and dependencies can require a few tricks and won’t be tested

Question 38

Q

Longest path might not exist

Answer

A

A necessary assumption:

If the graph has a directed cycle, we could get an inﬁnitely long path by repeating graph over and over again.

Graphs in scheduling applications are acyclic:

Otherwise we’d have a cycle of tasks that all depend on each other and we could never start the project!

Question 39

Q

Deﬁnition acyclic

Answer

A

A directed graph G is acyclic if it has no directed cycles.

Question 40

Q

The longest path algorithm

Answer

A

Initializing:

Topologically sort the vertices of G
List every edge of starting vertex as potential longest path

Iterate:
* Make the potential longest path to the ﬁrst vertex w on the list permanent

Update the list of potential longest paths adding edges out of w to longest paths to w and seeing if they create new longest paths

Question 41

Q

Ordering vertices / “topological sort”

Answer

A

If G is acyclic it’s easy to order the vertices of G so that if there’s an edge from v to w, then w comes after v

Note: the topological sort doesn’t have to be unique

eg 
UVWX
UWVX
directed edges 
UV
UW
VX
WX

*if a graph has a directed cycle we cant order it

every tree has a topological ordering, as it has no cycles ie start from top and leaves at end

HOW TO:

We choose an unvisited vertex. Explore out until we cant or have already written down in ordering . Then we add that last vertex to the end of our ordering. Go back to prev vertex and explore out if made a choice, adding. Then we can select another unvisited node. Topological orderings aren’t unique.

Question 42

Q

Example graph from the 2008 Exam
Find all longest paths from S to T

Directed graph edges
SB 7
SA 11
BA 3
AD 6
BD 10
DC 4
AC 10
CF 5
DF 9
CE 10
FE 3
ET 7
FT 11

Topological sort this graph:

Answer

A

Topological sort this graph:
SBADCFET

List every edge of starting vertex as potential longest path:
potential longest paths out of S:

SB 7*
SA 11

Iterate:
* Make the potential longest path to the ﬁrst vertex w on the list (most expensive to next vertex) permanent

Update the list of potential longest paths adding edges out of w to longest paths to w and seeing if they create new longest paths

potential longest path out of B:
SBA costs 10
but SA costs 11*
SBD 17

potential longest path out of A:
SAC 21
SAD 17*
and SBD 17*

potential longest path from D:
SADC 21*
SBDC 21*
(and SAC 21*)

SADF 26
SBDF 26

potential longest path from C:
SADCE 31
SBDCE 31
SBDCF 26*
SADCF 26*
or
SADF*
SBDF*

potential longest path from F:
S...FT 37
S...FE 29
But
SBDCE 31*
SADCE 31*
potential longest path from E:
S...ET 38*
(as S..FT 37 less than 38)

So our longest paths are:

SBDCET
SADCET
SACET

DIAGRAM: of all possible longest edges in paths and including in order

arrows
   \_\_\_      \_\_\_\_     \_\_\_
 /       ↘/       ↘/      ↘
S→B→A→D→C→F→E→T
       \       ↗ \       ↗\     ↗
        -------       ------       -----

longest path
B-7
A-11
D-17 [from B=10+7, A=11+6]
C-21 [from A=11+10, D=17+4]
F-26 [from C =21+3, D=17+4]
E-31 [from C=21+10, F= 26+3]
T-38 [from E=31+7, F=26+11]

marking on diagram edges SB SA DF CE ET bold

AD—
AC—
BD—

all longest path end CET but 3 ways get to C

Question 43

Q

Add on:

Which edges if made a little longer would make the longest path from S to T longer?

Answer

A

Any edge in the largest paths
increase makes longest path longer

SA
SB
AC
AD
DC
BD
CE
ET

Question 44

Q

Which edges if made a little shorter would make the longest path from S to T shorter?

Answer

A

THE EDGES IN ALL LONGEST PATHS

ET
CE
ie we are considering the longest path still so decrease all our options

Question 45

Q

The Travelling Salesperson Problem

Answer

A

A Travelling Salesperson wants to start from home, visit every city on their list, then return home for as cheaply as possible.

The Travelling Salesperson Problem, or TSP, is the following. Given a weighted graph G (usually G is the complete graph), what is the Hamiltonian cycle (i.e. closed walk visit every vertex) of cheapest weight

*we don’t tend to solve: only find bounds

Question 46

Q

TSP and Hamiltonian cycles

Answer

A

Let G be a graph n and vertex set V and edge set E. Suppose we want to determine whether G has a Hamiltonian cycle. Weight a complete graph on the vertex set V as follows:

make every edge in G have weight 1, and every edge not in G have slightly higher weight:
w(uv) =
{1 uv ∈ E
{1 + ε uv / ∈ E

Then, G has a Hamiltonian cycle if and only if there is a solution to the TSP with weight n.

*as we only used the edges in the original graph

Question 47

Q

upper bound for TSP

Answer

A

ﬁnd the weight of any Hamiltonian cycle

*One greedy algorithm: nearest neighbour Keeping going to the closest city you haven’t been to

Question 48

Q

nearest neighbour

Answer

A

only nearest haven’t been to. ie only the nearest to the one we just visited, no going back to consider other choices.

Question 49

Q

lower bound for TSP

Answer

A

can’t use a cycle
Any Hamiltonian cycle has length greater than solution to TSP

(ie connect every vertex vs return to original vertex)

To ﬁnd lower bound to TSP * Pick a vertex v ∈ G

Find a minimum weight spanning tree T on G \v
ie remove this vertex.
Find the two cheapest edges e1 and e2 out of v, the vertex we removed
w(T) + w(e1) + w(e2) is a lower bound:

ie its cheaper than any Hamiltonian cycle

Question 50

Q

Prove that w(T) + w(e) + w(f ) ≤ TSP

Answer

A

Suppose that C was the Hamiltonian cycle of minimum weight.
We split the C into two pieces: the two edges f1 and f2 adjacent to v, and the rest, which we’ll call R.

Edges adjacent to v: e1 and e2 were the two cheapest edges next to v, so: w(f1) + w(f2) ≥ w(e1) + w(e2)

The rest:
C a cycle, so R = C \v is a path

Paths are special cases of trees

R visits every vertex of G \v

Hence R a spanning tree and w(R) ≥ w(T)

(If C is a Hamiltonian cycle delete A and the 2 edges in C that visit A.

ill have a path through every vertex except A. C{A_{g,h}} is a spanning tree of G\A and so w(g,h) is bigger than w(t)

For the lower bound to be attainable

ie be a Hamiltonian cycle, we need

1) T has to be in path
2) the 2 cheapest edges out of A have to go to the two ends of the path

)

Question 51

Q

Example from the 2006 Exam
The following table encodes distances between towns in km:
[ A] 
[23][ B]
[10 ][ 21][  C] 
[30][ 39][ 21][  D ]
[57][ 45][ 48][ 45][   E] 
[68][ 63][ 59][ 47][ 24][ F] 
[75][ 67][ 66][ 54][ 24][ 11][ G]

Find lower and upper bounds to the TSP.

Answer

A

nearest neighbour for upper bound: start at A

AC 10
CB 21
BD 39
DE 45
EF 24
FG 11
GA 75

Brainscape's Knowledge GenomeTM

CHAPTER 3: Algorithms Flashcards

Brainscape's Knowledge Genome^TM