The adjacency matrix
A matrix is a two-dimensional rectangular array of numbers arranged in rows and columns. It looks like a table of numbers. The readers who want to more about matrix, see the Appendix A (will be shown up the later blog) in this document as a short introduction, or to know more deeply, see [7].I would like to show how a matrix can be used to describe a graph. My motivation is to be able to write down a graph. Following some rules, we can write down a graph in matrix form. Let me introduce such a method for representing a graph here. The matrix I will describe is called an adjacency matrix.
Definition: An adjacency matrix \(A\) of a graph of \(N\) vertices is an \(N \times N\) matrix where the element \(a_{i,j}\) is 1 when there is a directed edge from node \(i\) of the graph to node \(j\), otherwise 0.
That's all there is to it. An element in an adjacency matrix that represents a connection is a 1; an element that represents the lack of a connection is a 0. Let me show you some examples.
First, let's think about how we could represent relationships between people as a graph. A graph edge will represent that one person likes another person. I've decided to have an edge when someone likes someone else. It would be possible for an edge to mean that two people dislike each other, but I would prefer to know more about who likes whom. A note here, however --- a definition like the one I am making for my graph depends on me, the person who is solving the problem. I can define any meaning for a graph as long as there is no contradiction. This is not based on facts, but on what I have defined, so we first need to agree with this idea. If I say ``define,'' ``assume,'' or ``let us think...'', I am asking you to agree. If you don't agree with these initial definitions, then the rest of the discussion is meaningless!
Next time I will introduce Alice and draw a like-not-like graph.
References
[7] Gilbert Strang, ``Introduction to Linear Algebra, 4th Edition,'' Wellesley-Cambridge Press, 2009
Comments