wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> graph theory 
        
(Message started by: mathelete on Mar 27^th, 2005, 10:17am)

Title: graph theory
Post by mathelete on Mar 27^th, 2005, 10:17am

Can anybody tell me about the properties of the real (may be negative) weighted adjacency matrix of a graph.

Title: Re: graph theory
Post by towr on Mar 27^th, 2005, 12:45pm

I don't see any reason why it should have any properties besides those any square matrix has.. (i.e. being square :P)

Title: Re: graph theory
Post by kris on Mar 27^th, 2005, 1:33pm

isn't it symmetric too??...

Title: Re: graph theory
Post by towr on Mar 27^th, 2005, 1:55pm

Only if the graph is. i.e. it's not directed.

Otherwise you could for instance have nodes A and B, and it costs 0.5 to go from A to B, and 0.9 to go from B to A (or other arbityary values)

Aside from symmetry, the only other relational property of graphs I can think up that you can recognize from the matrix is reflexivity.
i.e. Iff the diagonal elements of the matrix are all non-zero then the graph is reflexive.