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

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