01204211/homework9 graph theory 2 - ประวัติรุ่นแก้ไข

Jittat เมื่อ 19:44, 17 ธันวาคม 2558

2015-12-17T19:44:29Z

Jittat เมื่อ 18:07, 9 ธันวาคม 2558

2015-12-09T18:07:36Z

Jittat เมื่อ 18:03, 9 ธันวาคม 2558

2015-12-09T18:03:58Z

Jittat เมื่อ 18:00, 9 ธันวาคม 2558

2015-12-09T18:00:23Z

Jittat เมื่อ 17:55, 9 ธันวาคม 2558

2015-12-09T17:55:04Z

Jittat เมื่อ 17:44, 9 ธันวาคม 2558

2015-12-09T17:44:31Z

Jittat: หน้าที่ถูกสร้างด้วย ': ''This is part of 01204211-58'' '''Due:''' 18 Dec 2015'

2015-12-09T17:18:12Z

หน้าที่ถูกสร้างด้วย ': ''This is part of 01204211-58'' '''Due:''' 18 Dec 2015'

หน้าใหม่

: ''This is part of [[01204211-58]]''

'''Due:''' 18 Dec 2015

@@ แถว 3: / แถว 3: @@
 '''Due:''' 18 Dec 2015
-'''H.1''' (LPV-7.3.9)  Prove that at least one of <math>G</math> and <math>\bar{G}</math> is connected.
+'''H.1''' (LPV-7.3.9)  Prove that at least one of <math>G</math> and <math>\bar{G}</math> is connected.   (Note that <math>\bar{G}</math> is a [https://en.wikipedia.org/wiki/Complement_graph complement graph] of <math>G</math>.)
-'''H.2'''  ''TBA''
+'''H.2'''  <del>''TBA''</del> ''There is no problem H.2.  Please skip this problem.''

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 18:07, 9 ธันวาคม 2558
แถว 6:		แถว 6:


−	'''H.2'''	+	'''H.2''' ''TBA''

@@ แถว 3: / แถว 3: @@
 '''Due:''' 18 Dec 2015
-'''H.1''' (LPV-8.3.2)  How many labeled trees on ''n'' nodes are stars?  How many are paths?
+'''H.1''' (LPV-7.3.9)  Prove that at least one of <math>G</math> and <math>\bar{G}</math> is connected.
-'''H.2''' (LPV-8.5.4)  Prove that if a tree has a node of degree ''d'', then it has at least ''d'' leaves.
+'''H.2'''
-'''H.3''' (LPV-10.3.1)  In class, we proved the [https://en.wikipedia.org/wiki/Hall's_marriage_theorem Hall's marriage theorem].  In this problem, you will show that if a bipartite graph <math>G=(A\cup B,E)</math> satisfies the condition that every node has the same degree <math>d\geq 1</math>, the <math>G</math> has a perfect matching.
+'''H.3''' (LPV-8.3.2)  How many labeled trees on ''n'' nodes are stars?  How many are paths?
 (Hint: first prove that (1) <math>|A|=|B|</math>, and (2) for any subset <math>X\subseteq A</math> of size <math>k</math>, the number of nodes in <math>B</math> that are connected to some node in <math>X</math> is at least <math>k</math>, then apply the Hall's theorem.)
-'''H.4''' (LPV-10.4.9)  Let ''G'' be a bipartite graph with ''m'' nodes on both sides.  Prove that if each node has degree larger than ''m/2'', then it has a perfect matching.
+'''H.6''' (LPV-10.4.9)  Let ''G'' be a bipartite graph with ''m'' nodes on both sides.  Prove that if each node has degree larger than ''m/2'', then it has a perfect matching.
 (Hint: prove that ''G'' is good.  Is is possible to find a subset of nodes on the left side that violates condition (2) for the Hall's marriage theorem?)

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 18:00, 9 ธันวาคม 2558
แถว 12:		แถว 12:

	(Hint: first prove that (1) <math>\|A\|=\|B\|</math>, and (2) for any subset <math>X\subseteq A</math> of size <math>k</math>, the number of nodes in <math>B</math> that are connected to some node in <math>X</math> is at least <math>k</math>, then apply the Hall's theorem.)		(Hint: first prove that (1) <math>\|A\|=\|B\|</math>, and (2) for any subset <math>X\subseteq A</math> of size <math>k</math>, the number of nodes in <math>B</math> that are connected to some node in <math>X</math> is at least <math>k</math>, then apply the Hall's theorem.)
		+
		+
		+	'''H.4''' (LPV-10.4.9) Let ''G'' be a bipartite graph with ''m'' nodes on both sides. Prove that if each node has degree larger than ''m/2'', then it has a perfect matching.
		+
		+	(Hint: prove that ''G'' is good. Is is possible to find a subset of nodes on the left side that violates condition (2) for the Hall's marriage theorem?)

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 17:55, 9 ธันวาคม 2558
แถว 7:		แถว 7:

	'''H.2''' (LPV-8.5.4) Prove that if a tree has a node of degree ''d'', then it has at least ''d'' leaves.		'''H.2''' (LPV-8.5.4) Prove that if a tree has a node of degree ''d'', then it has at least ''d'' leaves.
		+
		+
		+	'''H.3''' (LPV-10.3.1) In class, we proved the [https://en.wikipedia.org/wiki/Hall's_marriage_theorem Hall's marriage theorem]. In this problem, you will show that if a bipartite graph <math>G=(A\cup B,E)</math> satisfies the condition that every node has the same degree <math>d\geq 1</math>, the <math>G</math> has a perfect matching.
		+
		+	(Hint: first prove that (1) <math>\|A\|=\|B\|</math>, and (2) for any subset <math>X\subseteq A</math> of size <math>k</math>, the number of nodes in <math>B</math> that are connected to some node in <math>X</math> is at least <math>k</math>, then apply the Hall's theorem.)

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 17:44, 9 ธันวาคม 2558
แถว 2:		แถว 2:

	'''Due:''' 18 Dec 2015		'''Due:''' 18 Dec 2015
		+
		+	'''H.1''' (LPV-8.3.2) How many labeled trees on ''n'' nodes are stars? How many are paths?
		+
		+
		+	'''H.2''' (LPV-8.5.4) Prove that if a tree has a node of degree ''d'', then it has at least ''d'' leaves.