home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / theory / 2524 < prev    next >
Encoding:
Internet Message Format  |  1992-11-24  |  1.6 KB
  1. Path: sparky!uunet!mcsun!uknet!nplpsg!ajm
  2. From: ajm@seg.npl.co.uk (Tony Mansfield)
  3. Newsgroups: comp.theory
  4. Subject: Re: Silence on P=NP
  5. Message-ID: <1992Nov23.170508.28493@seg.npl.co.uk>
  6. Date: 23 Nov 92 17:05:08 GMT
  7. References: <1992Nov21.222755.18863@sophia.smith.edu>
  8. Organization: National Physical Laboratory, UK
  9. Lines: 23
  10.  
  11. I have tried the Swart+Gismondi graph isomorphism algorithm on the
  12. non-isomorphic graphs G1 = {{1,2},{1,2},{2,3}} and G2 = {{1,2},{1,3},{2,3}}
  13. which have adjacency matrices (020) and (011).  Using the terms of their paper
  14.                               (201)     (101)
  15.                               (010)     (110)
  16. "A polynomial-time procedure for resolving the graph isomorphism problem"
  17. (/pub/theory/isomorph.ps.Z received from smowhite.cis.uoguelph.ca by ftp)
  18.         T = 0.5*(100 000 000) + 0.5*(100 000 000) 
  19.                 (010 000 000)       (001 000 000)
  20.                 (001 000 000)       (010 000 000)
  21.                 (000 100 000)       (000 000 100)
  22.                 (000 010 000)       (000 000 001)
  23.                 (000 001 000)       (000 000 010)
  24.                 (000 000 100)       (000 100 000)
  25.                 (000 000 010)       (000 001 000)
  26.                 (000 000 001)       (000 010 000)
  27. is a linear combination of two Q matrices and satisfies all the constraints
  28. (3), (4) and (6).  Moreover
  29.       T (020 201 010)^t = (011 101 110)^t
  30. so (5) is satisfied too, showing(?) G1 and G2 to be isomorphic!
  31.  
  32. Tony Mansfield,   <ajm@seg.npl.co.uk>             Phone: (+44) 81 943 7029
  33. DITC, NPL, Teddington, Middlesex TW11 OLW, UK.      Fax: (+44) 81 977 7091
  34.