Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #8008

Re: on notation, MM', graph theory, incidence matrix product

Cross-posted to 2 groups.

Show all headers | View raw

Daniel Bastos <dbastos@toledo.com> writes:

> Problem.  Show that if G is simple, the entries on the diagonals of both
> MM' and A^2 are the degrees of the vertices of G.
>
> I don't understand what is meant by MM'.  M is the incidence matrix of
> graph G.  By looking at section 1.4, subgraphs, I take that M' must be
> the incidence matrix of some subgraph induced by M,

No.  The notation is confusing but ' is often used for different things
in different places.

> but M is a matrix,
> so I'm puzzled.  AFAIK, I need a set of vertices of a set of edges to
> induce a subgraph.

You are right.  M is a matrix and the ' just means normal matrix
transposition.  M is (in general) a rectangular v x e matrix so it can
only be multiplied by an e x v matrix such as the transpose.  The
incidence matrix of any subgraph would not be the right size.  In effect
you have to deduce the meaning from the only thing that could make
sense.

> I appreciate a clarification on the book's notation.  Thank you!

The summary of synbols at the end gives R' as the transpose of R.  It's
a shame it was used with that meaning right after some text that used V'
and E' simply as a modifier to mean some subset of V or E.

-- 
Ben.

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

on notation, MM', graph theory, incidence matrix product Daniel Bastos <dbastos@toledo.com> - 2017-09-16 11:26 -0300
  Re: on notation, MM', graph theory, incidence matrix product Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-09-16 16:39 +0100
    Re: on notation, MM', graph theory, incidence matrix product Daniel Bastos <dbastos@toledo.com> - 2017-09-17 07:51 -0300

csiph-web