Stuff-for-eig - ประวัติรุ่นแก้ไข

Jittat เมื่อ 13:44, 21 มิถุนายน 2553

2010-06-21T13:44:17Z

Jittat เมื่อ 13:40, 21 มิถุนายน 2553

2010-06-21T13:40:57Z

Jittat เมื่อ 13:38, 21 มิถุนายน 2553

2010-06-21T13:38:32Z

Jittat เมื่อ 13:36, 21 มิถุนายน 2553

2010-06-21T13:36:36Z

Jittat เมื่อ 13:34, 21 มิถุนายน 2553

2010-06-21T13:34:41Z

Jittat: หน้าที่ถูกสร้างด้วย 'พิจารณาการเดินทางจาก u ไป t ให้ d(u,t) แทนระยะทางจาก u ไป…'

2010-06-21T13:33:09Z

หน้าที่ถูกสร้างด้วย 'พิจารณาการเดินทางจาก u ไป t ให้ d(u,t) แทนระยะทางจาก u ไป…'

หน้าใหม่

พิจารณาการเดินทางจาก u ไป t ให้ d(u,t) แทนระยะทางจาก u ไป t ใน base graph

'''case 1:''' ถ้ามีเส้นเชื่อมกระโดดที่กระโดดจาก u ไป w ใน D(u,t) ที่ <math>d(u,w) >= c\cdot d(u,t)</math>, สำหรับบาง c
เราจะได้ว่า d(w,t) จะลดลงจาก d(u,t) มาก ดังนั้น case นี้น่าจะจัดการได้แล้ว

'''case 2:''' สมมติว่าไม่มีกรณีข้างต้น:

สำหรับระยะทาง r ใด ๆ ให้ Ball(u,r) แทน ball ที่มีจุดศูนย์กลางเป็น u รัศมี r

ให้ <math>Z = c \cdot d(u,t)</math> แบ่ง Ball(u,Z) ออกเป็น layer ตามระยะทางจาก u

สำหรับเซ็ต U ใด ๆ ให้ P(u,U) = Pr[มีเส้นเชื่อมกระโดดจาก u ไปบางโหนดในเซ็ต U]

ให้ <math>Y = c'\cdot Z</math> สำหรับบาง constant <math>0 < c' < 1</math>

พิจารณา <math>P(u, Ball(u,Y)\cap D(u,t))</math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 13:44, 21 มิถุนายน 2553
แถว 19:		แถว 19:

	'''Goal:''' จะแสดงว่ามีความน่าจะเป็นมากพอที่จะมีเส้นเชื่อมกระโดดจาก u ไป w ที่ <math>d(w,t) \leq \alpha d(u,t)</math> สำหรับค่าคงที่ <math>\alpha</math> บางค่า		'''Goal:''' จะแสดงว่ามีความน่าจะเป็นมากพอที่จะมีเส้นเชื่อมกระโดดจาก u ไป w ที่ <math>d(w,t) \leq \alpha d(u,t)</math> สำหรับค่าคงที่ <math>\alpha</math> บางค่า
−
−	~~พิจารณา <math>p = P(u, Ball(u,Y)\cap D(u,t))</math> และ <math>q = P(u,D(u,t)) - P(u, Ball(u,Y)\cap D(u,t))</math>~~
−
−	~~แนวทาง: พิจารณา <math>\|Ball(u,Y)\cap D(u,t)\|</math> กับ <math>\|(Ball(u,Z) - Ball(u,Y))\cap D(u,t)\|</math>~~

@@ แถว 17: / แถว 17: @@
 '''(A.1)''' สมมติว่า P(u,D(u,t)) มีค่ามากกว่าค่าคงที่บางค่า ('''assumption นี้ต้องมาจัดการต่อ''')
 พิจารณา <math>p = P(u, Ball(u,Y)\cap D(u,t))</math> และ <math>q = P(u,D(u,t)) - P(u, Ball(u,Y)\cap D(u,t))</math>
+แนวทาง: พิจารณา <math>|Ball(u,Y)\cap D(u,t)|</math>  กับ <math>|(Ball(u,Z) - Ball(u,Y))\cap D(u,t)|</math>

@@ แถว 16: / แถว 16: @@
 '''(A.1)''' สมมติว่า P(u,D(u,t)) มีค่ามากกว่าค่าคงที่บางค่า ('''assumption นี้ต้องมาจัดการต่อ''')
 พิจารณา <math>p = P(u, Ball(u,Y)\cap D(u,t))</math> และ <math>q = P(u,D(u,t)) - P(u, Ball(u,Y)\cap D(u,t))</math>
-'''(C.1)''' claim: <math>q \geq \gamma p</math>

@@ แถว 13: / แถว 13: @@
 ให้ <math>Y = c'\cdot Z</math> สำหรับบาง constant <math>0 < c' < 1</math>
 '''(A.1)''' สมมติว่า P(u,D(u,t)) มีค่ามากกว่าค่าคงที่บางค่า ('''assumption นี้ต้องมาจัดการต่อ''')
-พิจารณา <math>P(u, Ball(u,Y)\cap D(u,t))</math>
+พิจารณา <math>p = P(u, Ball(u,Y)\cap D(u,t))</math> และ <math>q = P(u,D(u,t)) - P(u, Ball(u,Y)\cap D(u,t))</math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 13:34, 21 มิถุนายน 2553
แถว 13:		แถว 13:

	ให้ <math>Y = c'\cdot Z</math> สำหรับบาง constant <math>0 < c' < 1</math>		ให้ <math>Y = c'\cdot Z</math> สำหรับบาง constant <math>0 < c' < 1</math>
		+
		+	'''(A.1)''' สมมติว่า P(u,D(u,t)) มีค่ามากกว่าค่าคงที่บางค่า ('''assumption นี้ต้องมาจัดการต่อ''')

	พิจารณา <math>P(u, Ball(u,Y)\cap D(u,t))</math>		พิจารณา <math>P(u, Ball(u,Y)\cap D(u,t))</math>