01204211/activity8 polynomials and graph theory 1

This is part of 01204211-58.

In-class activities

Due date: 14 Dec 2015

Polynomials

To work on these questions, you can refer to this lecture note from Berkeley.

For this set of activities, we shall work modulo 11.

We will use your student ID as a data. For $i=0,...,9$, let $a_{i}$ denote the $i$-th digit (counting from the lest, starting at 0) of your student ID. For example if your student ID is 5755543210, $a_{0}=0$, $a_{2}=2$, $a_{9}=5$, $a_{8}=7$

A.1-1 We shall use your last 4 digits: $a_{0},a_{1},a_{2},a_{3}$. Find a polynomial $f$ of degree 3 such that $f(x)=a_{x}$ for $x=0,\ldots ,3$. You should start by writing down $\Delta _{i}(x)$.

A.1-2 Erasure codes. Let's experiment on erasure codes using the degree 3 polynomial $f$ from the last question. You should work with another student.

Encoding: Let's treat the first 4 digits of your ID $a_{0},a_{1},a_{2},a_{3}$ as a message. We will encode it into 6 pairs of numbers (modulo 11) like this: $(0,f(0))$, $(1,f(1))$, $(2,f(2))$, $(3,f(3))$, $(4,f(4))$, $(5,f(5))$.

Note that the first 4 pairs represent your message exactly. The last 2 pairs provide extra information.

Now discard 2 of the first 4 pairs, and give the rest (including the last 2 pairs) to your friend. (I.e., you should give your friend 4 pairs of integer modulo 11.) Notes: do not give out the polynomial.

Decoding: Now suppose that you have already got the encoded message (with 2 missing pairs) from your friend. How can you decode the message? Try to decode the message and check with your friend if you do that correctly.

Graph theory 1

A.2-1 Prufer codes. Again for this problem, you should work with another student.

We shall practice encoding and decode the Prufer code. We will work with a tree with 9 nodes.

Encoding: Draw a labeled tree randomly with 9 nodes. Label the nodes with 0,1,...,8. Find the extended Prufer code of the tree and then strip it down to the actual Prufer code with 7 numbers. Give the code to your friend.

Decoding: After receiving the code from your friend. Reconstruct the extended Prufer code and draw the labeled tree corresponding to that code. Check with your friend if you work correctly.

A.2-2 (LPV-7.1.2) (a) Is there a graph on 6 nodes with degrees 2,3,3,3,3,3?

(b) Is there a graph on 6 nodes with degrees 0,1,2,3,4,5?

(c) How many graphs are there on 4 nodes with degrees 1,1,2,2? (In this problem, we treat graphs as unlabeled graphs; therefore, two graphs are the same if they are isomorphic.)

(d) How many graphs are there on 10 nodes with degrees 1,1,1,1,1,1,1,1,1,1?

A.2-3 (LPV-7.1.5) What is the largest number of edges a graph with 10 nodes can have?

A.2-4 (LPV-7.3.10) Let $G$ be a connected graph with at least two nodes. Prove that it has a node such that if this node is removed (along with all edges incident with it), the remaining graph is connected. (Hint: you can try to prove this by (strong) induction on the number of nodes. Pick any node in the graph. If it is not the node with the property that we want, how can we find another node satisfying our condition?)

A.2-5 (LPV-8.1.1) Prove this statement: A graph $G$ is a tree if and only if it contains no cycles, but adding any new edge creates a cycle. (Hint: recall that a tree is a graph that (1) is connected and (2) contains no cycles. In this problem, (2) is already stated, you just need to show (1).)

A.2.6 (LPV-8.5.3) Prove that a graph with $n$ nodes and $m$ edges has at least $n-m$ connected components.