Classifying graphs by patterns in their adjacency matrices

Given a set $S$, how can we classify different graphs $G(S)$ (tree, connected/disconnected, ...) based on the patterns of the 1's and 0's in their adjacency matrices $M(G(S))$?

-
Interesting idea. However, classification based on the "physical" arrangement of elements in the adjacency matrix can be tricky, because that arrangement depends on the correspondence between graph vertices and matrix rows and columns. It's unlikely that any property of "Snake" gameplay persists across reordering of the rows and columns, except in the least-complicated of cases, even when the reordered matrix represents the same graph. – Blue Jun 20 '12 at 4:01
What is a "true element" of an adjacency matrix? – Qiaochu Yuan Jun 20 '12 at 4:18
@Qiaochu, I'm guessing those would be the ones, which would make the zeros "false elements". – Gerry Myerson Jun 20 '12 at 4:45
You might want to avoid clicking the "Post Your Question" button until your thoughts have settled. If the StackExchange software is posting your many in-progress edits without you clicking that button, then report that on "Meta" as a bug, and consider composing your text off-site. That way, the rest of us can avoid commenting on an ever-evolving formulation of your question. (My reference to "'Snake' gameplay" is going to seem odd to people who read the question in its current form. Actually, I'm somewhat disappointed that the game element is gone from the question.) – Blue Jun 20 '12 at 5:25
@DayLateDon That's wasn't a glitch--I was indeed clicking the button repeatedly. From now on I will try to click less often. – idonutunderstand Jun 20 '12 at 5:28