# Functions, graphs, and adjacency matrices

One naively thinks of (continuous) functions as of graphs1 (lines drawn in a 2-dimensional coordinate space).

One often thinks of (countable) graphs2 (vertices connected by edges) as represented by adjacency matrices.

That's what I learned from early on, but only recently I recognized that the "drawn" graphs1 are nothing but generalized - continuous - adjacency matrices, and thus graphs1 are more or less the same as graphs2.

I'm quite sure that this is common (maybe implicit) knowledge among working mathematicians, but I wonder why I didn't learn this explicitly in any textbook on set or graph theory I've read. I would have found it enlightening.

My questions are:

Did I read my textbooks too superficially?

Is the analogy above (between graphs1 and graphs2) misleading?

Or is the analogy too obvious to be mentioned?

-

Coming from a set theoretic point of view, both of them are more or less the same thing - a collection of ordered pairs defining a relation which is a graph in one case and a function in another.

The reason, however, the idea of a continuous matrix is slightly troublesome is that you need to know which is the "next" coordinate. So the matrix needs to be well ordered, further more, if we require there is a permutation of the rows leaving the matrix with the same order (for example, switch two rows) we have to require initial ordinals, i.e. cardinals, and not any ordinals.

Otherwise, the matrix with $\omega + 1$ rows can be isomorphic to the one with $\omega$ rows (take the $\omega$-th row, switch it with the first row, the one you switched put in the second row, and so on...).

Now, matrices are very useful when there is some corresponding between the indices of the matrix and the element you're dealing with. So a finite graph and an adjacency matrix are similar in that sense.

While the real numbers can be well-ordered, this well-ordering tells us nothing about the usual order of them, and it's harder to "navigate" within the matrix, let alone keep the idea of continuity as being close to another point in the real numbers does not imply that you are close to it on the matrix.

In that sense, both graphs are similar like dogs and cats. Both are mammals (relations) and have fur, and surely you can find some connection and common characteristics but ultimately they are different animals, when viewed as dogs and cats, and not as mammals.

-

My opinion: the analogy is not misleading, is not too obvious to be mentioned, but is also not terribly useful. Have you found a use for it?

EDIT: Here's another way to think about it. A $\it relation$ on a set $S$ is a subset of $S\times S$, that is, it's a set of ordered pairs of elements of $S$. A relation on $S$ can be viewed as a (directed) graph, with vertex set $S$ and edge set the relation. We draw this graph by drawing the vertices as points in the plane and the edges as (directed) line segments connecting pairs of points

Now consider "graph" in the sense of "draw the graph of $x^2+y^2=1$." That equation is a relation on the set of real numbers, and the graph is obtained by drawing the members of this relation as points in the plane.

So the two kinds of graph are two ways of drawing a picture to illustrate a relation on a set.

-
No use, only in understanding the homonymy of graph$_1$ and graph$_2$. – Hans Stricker May 1 '11 at 0:33

In my opinion, the similarity between graphs1 and graphs2 is only superficial. Both kinds of graphs can be thought of as particular subsets of certain kinds of Cartesian product ($\mathbb R \times \mathbb R$ and $V \times V$), but that's about as far as it goes.

Consider:

1. A graph1 generalizes to higher dimensional functions $\mathbb R^m \to \mathbb R^n$ which cannot be thought of as a graph2 when $m \neq n$. A graph2 generalizes to graphs with labelled edges, multigraphs, and so on, which cannot be thought of as a graph1.

2. Rearranging the order of elements in the adjacency matrix gives you the same graph2, but not the same graph1.

3. Given a graph1, we care about things like injectivity, continuity, convexity, and so on, which do not correspond to useful properties of the corresponding graph2. Given a graph2, we care about things like connectivity, shortest paths, planarity, and so on, which do not correspond to useful properties of the corresponding graph1.

A simple example: The graph of $f(x) = x$ is a continuous line, but a graph where each vertex is only connected to itself is completely disconnected.

-