ผลต่างระหว่างรุ่นของ "Stuff-for-eig"
ไปยังการนำทาง
ไปยังการค้นหา
Jittat (คุย | มีส่วนร่วม) |
Jittat (คุย | มีส่วนร่วม) |
||
| แถว 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 นี้ต้องมาจัดการต่อ''') | '''(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> |
| + | |||
| + | '''(C.1)''' claim: <math>q \geq \gamma p</math> | ||
รุ่นแก้ไขเมื่อ 13:36, 21 มิถุนายน 2553
พิจารณาการเดินทางจาก u ไป t ให้ d(u,t) แทนระยะทางจาก u ไป t ใน base graph
case 1: ถ้ามีเส้นเชื่อมกระโดดที่กระโดดจาก u ไป w ใน D(u,t) ที่ , สำหรับบาง c เราจะได้ว่า d(w,t) จะลดลงจาก d(u,t) มาก ดังนั้น case นี้น่าจะจัดการได้แล้ว
case 2: สมมติว่าไม่มีกรณีข้างต้น:
สำหรับระยะทาง r ใด ๆ ให้ Ball(u,r) แทน ball ที่มีจุดศูนย์กลางเป็น u รัศมี r
ให้ แบ่ง Ball(u,Z) ออกเป็น layer ตามระยะทางจาก u
สำหรับเซ็ต U ใด ๆ ให้ P(u,U) = Pr[มีเส้นเชื่อมกระโดดจาก u ไปบางโหนดในเซ็ต U]
ให้ สำหรับบาง constant
(A.1) สมมติว่า P(u,D(u,t)) มีค่ามากกว่าค่าคงที่บางค่า (assumption นี้ต้องมาจัดการต่อ)
พิจารณา และ
(C.1) claim:
