ผลต่างระหว่างรุ่นของ "Stuff-for-eig"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
แถว 17: แถว 17:
 
'''(A.1)''' สมมติว่า P(u,D(u,t)) มีค่ามากกว่าค่าคงที่บางค่า ('''assumption นี้ต้องมาจัดการต่อ''')
 
'''(A.1)''' สมมติว่า P(u,D(u,t)) มีค่ามากกว่าค่าคงที่บางค่า ('''assumption นี้ต้องมาจัดการต่อ''')
  
 +
 +
'''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>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>
'''Goal:''' จะแสดงว่ามีความน่าจะเป็นมากพอที่จะมีเส้นเชื่อมกระโดดจาก u ไป w ที่ <math>d(w,t) \leq \alpha d(u,t)</math>
 

รุ่นแก้ไขเมื่อ 13:40, 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 นี้ต้องมาจัดการต่อ)


Goal: จะแสดงว่ามีความน่าจะเป็นมากพอที่จะมีเส้นเชื่อมกระโดดจาก u ไป w ที่ สำหรับค่าคงที่ บางค่า

พิจารณา และ

แนวทาง: พิจารณา กับ