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

Groups > comp.programming > #8010

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

Cross-posted to 2 groups.

Show all headers | View raw

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> 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 did happen to consider ' as matrix transposition, but then I
(incorrectly) found a counterexample to the claim so I thought I was
totally off.  The counterexample I found was for a nonsimple graph.

>> 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.

Yes! :-) Thanks very much!

Back to comp.programming | Previous | Next — Previous 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