01204211/activity8 polynomials and graph theory 1 - ประวัติรุ่นแก้ไข

Jittat: /* In-class activities */

2015-12-09T17:15:11Z

In-class activities

2015-12-09T17:14:59Z

2015-11-26T04:19:22Z

Graph theory 1

2015-11-26T02:31:33Z

Polynomials

2015-11-26T02:19:06Z

Graph theory 1

2015-11-26T02:17:58Z

Graph theory 1

2015-11-26T02:09:50Z

Graph theory 1

2015-11-26T02:06:57Z

Graph theory 1

2015-11-26T02:06:15Z

Graph theory 1

2015-11-26T02:01:49Z

Polynomials

@@ แถว 3: / แถว 3: @@
 == In-class activities ==
-: '''Due 14 Dec 2015'''
+: '''Due date: 14 Dec 2015'''
 === Polynomials ===

@@ แถว 2: / แถว 2: @@
 == In-class activities ==
 === Polynomials ===
@@ แถว 55: / แถว 57: @@
 '''A.2.6''' (LPV-8.5.3) Prove that a graph with <math>n</math> nodes and <math>m</math> edges has at least <math>n-m</math> connected components.

@@ แถว 31: / แถว 31: @@
 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 6 numbers.  Give the code to your friend.
+''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.

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 02:31, 26 พฤศจิกายน 2558
แถว 12:		แถว 12:


−	'''A.1-1''' We shall use your last 4 digits: <math>a_0,a_1,a_2,a_3</math>. Find a polynomial <math>f</math> of degree 3 such that <math>f(x)=a_x</math> for <math>i=0,\ldots,3</math>. You should start by writing down <math>\Delta_i(x)</math>.	+	'''A.1-1''' We shall use your last 4 digits: <math>a_0,a_1,a_2,a_3</math>. Find a polynomial <math>f</math> of degree 3 such that <math>f(x)=a_x</math> for <math>x=0,\ldots,3</math>. You should start by writing down <math>\Delta_i(x)</math>.

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 02:19, 26 พฤศจิกายน 2558
แถว 48:		แถว 48:


−	'''A.2-4''' (LPV-7.3.10) Let <math>G</math> 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.)	+	'''A.2-4''' (LPV-7.3.10) Let <math>G</math> 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?)

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 02:17, 26 พฤศจิกายน 2558
แถว 48:		แถว 48:


−	'''A.2-4''' (LPV-7.3.10) Let <math>G</math> 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.	+	'''A.2-4''' (LPV-7.3.10) Let <math>G</math> 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.)
		+
		+
		+	'''A.2-5''' (LPV-8.1.1) Prove this statement: A graph <math>G</math> 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 <math>n</math> nodes and <math>m</math> edges has at least <math>n-m</math> connected components.

	== Homework ==		== Homework ==

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 02:09, 26 พฤศจิกายน 2558
แถว 46:		แถว 46:

	'''A.2-3''' (LPV-7.1.5) What is the largest number of edges a graph with 10 nodes can have?		'''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 <math>G</math> 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.

	== Homework ==		== Homework ==

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 02:06, 26 พฤศจิกายน 2558
แถว 43:		แถว 43:

	(d) How many graphs are there on 10 nodes with degrees 1,1,1,1,1,1,1,1,1,1?		(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?

	== Homework ==		== Homework ==

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 02:06, 26 พฤศจิกายน 2558
แถว 34:		แถว 34:

	''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.		''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?

	== Homework ==		== Homework ==

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 02:01, 26 พฤศจิกายน 2558
แถว 24:		แถว 24:

	''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.		''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.
−
−
−	~~'''A.1-3''' '''Secret sharing.'''~~

	=== Graph theory 1 ===		=== Graph theory 1 ===