The Mathematics of P vs NP by hemant pandey - HTML preview

PLEASE NOTE: This is an HTML preview only and some elements such as links or page numbers may be incorrect.
Download the book in PDF, ePub, Kindle for a complete version.

 

 

 


394

 

395

 

396

397

398

399

400

 

401


Case 1: When a diagonal is joined between two consecutive points

 

Let A14  is joined to A12, so the point A13 is now out of network. [Refer Fig.2].

 

Now since we have to cover each point of the network, A13 has to be joined to some other point. Let A13 is joined to A3 and A4.These points are arbitrary .The important point is not the point but the property exhibited by each point. If A13 is joined to any other point the property exhibited by the point would be the same as with this point. Note we are talking of topological properties where only the relative position matters.


402\ Now new network distance is


 

403


N-A14A13-A13A12+A14A12+A3A13A4A13-A3A4


 


404

405

 

406

407

408

 

409

410

 

411


Now A14A12   >A14A13 (A14A12 is the adjacent diagonal of SCP and by the definition of SCP it is greater than the side forming it)

 

Further A3A13 >A13A12 (Since by the definition of SCP the shortest distance from a point on the periphery is next point to it on either side, all other branches from emerging from it are the diagonals)

 

Finally A4A13>A3A4 (A4A13 is the adjacent diagonal of SCP and by the definition of SCP it is greater than the side forming it)


412 c The  Net  network  distance  increases  as  sum  of  the  adding  distances  is  greater  than  the


413

 

414

415

 

416

 

417

 

418

419