I need a good read on the relationship of graph theory with linear algebra. Can someone discuss this or point me to good reading materials? Thanks.
Relationship of graph theory with linear algebra or converting graphs into vector spaces, you can find in any book of Discrete Mathematics-Graph Theory.
There are some links for beginning:
GRAPH THEORY
http://math.tut.fi/~ruohonen/GT_English.pdf
Graph Embedding
http://www.informatik.uni-ulm.de/ni/ANNPR10/InvitedTalks/Buh...
I suppose you are talking about things like incidence matrices and adjacency matrices (or even lists). You can find these constructions in any graph theory textbook (introductory). Certain operations like squaring them as a matrix can tell you things, and also are a more efficient means of representing them on a computer.
For example, suppose I have a graph G=(V,E), where:
V={1,2,3,4,5}
E={{1,2},{3,5},{4,2}}
For example, an adjacency matrix is described as follows. We say A[i][j]=1 if there is an edge {i,j} in E, and 0 otherwise.
Then the adjacency matrix A for G above is:
A= 0 1 0 0 0
1 0 0 1 0
0 0 0 0 1
0 1 0 0 0
0 0 1 0 0.
Hope this helps! :)
The usual keywords are "algebraic graph theory" or "spectral graph theory". The book of Godsil-Royle is a perfect introduction to this topic.
Daniel/Dello, thanks for your suggestion. What about matroids? One notion I am trying to grasp is the idea of independence.
I guess I better grab this book - Godsil I read came from Melbourne :-)
Relationship of graph theory with linear algebra or converting graphs into vector spaces, you can find in any book of Discrete Mathematics-Graph Theory.
There are some links for beginning:
GRAPH THEORY
http://math.tut.fi/~ruohonen/GT_English.pdf
Graph Embedding
http://www.informatik.uni-ulm.de/ni/ANNPR10/InvitedTalks/Buh...
Thanks so much Qefsere, that PDF from Finland is probably just what I need for now.
Most courses/texts/etc., tend to use the word "associate" (i.e., "We start with two vector spaces associated with every graph – the cycle space and the cocycle space; from Knauer's Algebraic Graph Theory). Among other reasons, vector spaces excluding the null space consist of linear combinations of vectors (outside of intro matrix/linear algebra texts and sometimes even in these they are defined in terms of fields, specifically in terms of some vector space over a field such as R). That is, while it is easy enough to associate a graph to basis vectors that span some vector space V, the actual space consists of infinitely many elements.
That is a key part of independence, actually. Given some set of vectors, if they span some vector (sub)space then no addition of them or any scalar multiplication of any of them can take you out of that space. Given some set of vectors in R2, for example, they cannot span the "space" of some line unless that line is through the origin (also, if span is taken to mean minimal span of a subspace, which every line is in the space R2, redundancy comes into play).
The relationship between graph theory and linear algebra is algebra. Algebraic structures and representations (and representation theory) all can by crudely and simplistically subsumed under "abstract algebra", and while such a broad definitions misses crucial distinctions, it does provide a foundation for understanding why text on graph theory or linear algebra contain terms, concepts, definitions, propositions, etc., one may find in a text on algebraic topology or Boolean algebra. Whether lattices or Lie groups, algebras are concerned centrally with abstracting away from the algebra we all learned before college to arbitrary alphabets, sets, etc., to create algebraic structures. Graph theory is in many ways a more direct and intuitive method to represent, examine, and investigate algebras (more flexibly than possible using the language of geometry).
It can be basis as a vertex space or vertex set then edge space or edge set is the symmetric difference of the vertex space elements for a particular vector space
- Badges
- Science topic
- Similar topics
- Mathematics