1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Number of possible trees in graph theory

  1. Dec 20, 2017 #1
    1. The problem statement, all variables and given/known data
    upload_2017-12-20_18-24-19.png

    2. Relevant equations
    Reduce the matrix to reduced matrix by removing 1 row completely
    Number of trees = determinant of [ Ar times ArT ]
    3. The attempt at a solution
    I removed 4th row to get Ar(reduced matrix)
    Then I did Ar times Ar (transpose)
    And found it's determinant but I got different answer depending on which row I remove.
    Do I randomly remove any row?
    Sorry for posting too many homework questions. I have an exam coming up in Feb.
     
  2. jcsd
  3. Dec 20, 2017 #2

    StoneTemplePython

    User Avatar
    Science Advisor
    Gold Member

    Long story short, this looks like a mechanical recipe being misapplied. I don't understand your incidence matrices. Or to the extent I do understand them, then the shoe doesn't fit.

    - - - - - -
    If you're looking for understanding, I would strongly suggest reading chapter 21 of Thirty Three Miniatures. A free pre-publication draft is a available here:

    http://kam.mff.cuni.cz/~matousek/stml-53-matousek-1.pdf

    (note to moderators: see referring page under "books" here: http://kam.mff.cuni.cz/~matousek/ )

    another place to look is:

    http://math.mit.edu/~levine/18.312/alg-comb-lecture-19.pdf


    - - - -
    Mechanically there are a few problems here. Technical nit: you aren't just counting trees, you're counting spanning trees.

    In general, a clean way to do this is to lop off the final row and final column of the graph Laplacian. (Via graph isomorphism arguments it ultimately doesn't matter, but doing the outermost components is easiest.)


    There's a few ways to proceed. Key question: what does the graph Laplacian look like?

    You can draw the actual picture associated with your incidence matrix and make the graph Laplacian by hand.

    What you currently, in effect, are saying is that ##\mathbf L = \mathbf A \mathbf A^T##. The (un-normalized aka combinatorial) graph Laplacian is supposed to have the ones vector in its nullspace, such that we always have ##\mathbf 1^T \mathbf L \mathbf 1 = 0##.

    But in your example ##\mathbf 1 ^T \mathbf L \mathbf 1 = \big(\mathbf 1^T \mathbf A\big)\big( \mathbf A^T \mathbf 1\big) \gt 0##. I.e. the fact that ##\big( \mathbf A^T \mathbf 1\big) \neq \mathbf 0## is a red flag that something is amiss with your incidence matrix and/or how you're interpreting / applying it.
     
  4. Dec 21, 2017 #3
    In solved examples all incidence matrix had sum of elements in each columns as 0. So I think there must be a typo in the question.
    Do you lop off one row and one column?
    Book says to remove only one row to get reduced incidence matrix. It doesn't mention removing any column.
     
  5. Dec 21, 2017 #4

    StoneTemplePython

    User Avatar
    Science Advisor
    Gold Member

    It depends on whether you're working directly with ##\mathbf L## or instead the incidence matrix ##\mathbf A##. If ##\mathbf L##, then remove outer most row and column. If working directly with a conforming incidence matrix, then if you work through the multiplications, you'll see just removing the bottom row of the incidence matrix is equivalent.
     
  6. Dec 24, 2017 #5
    What is L? The notes only have A as incidence matrix and Ar as reduced incidence matrix and then there are formula of number of graphs and number of twigs/branches.
    Is there some formula of L? What does L mean?
     
  7. Dec 24, 2017 #6

    StoneTemplePython

    User Avatar
    Science Advisor
    Gold Member

    ##\mathbf L## is the 'regular', aka 'combinatorial' aka 'unnormalized' graph Lapalacian. It is generally defined as the degree matrix minus the adjacency matrix. If your graph is undirected/ symmetric, you generally have a relation to incidence matrix ##\mathbf A## in the form of ##\mathbf L = \mathbf {AA}^T## (or ##\mathbf A^T \mathbf A## depnding on how you set it up.)

    check out

    https://en.wikipedia.org/wiki/Laplacian_matrix

    They also fully define it in the links I gave to a pdf from MIT and a pdf called Thirty Three Miniatures.

    (note in general ##\mathbf A## tends to refer to an adjacency matrix, not the incidence matrix, but that's a minor convention.)

    The graph Laplacian in some sense is the end-game for looking at interesting stuff in graphs. Your incidence matrix is just a pre-cursor. (Nothing wrong with working directly with the precursor though.)
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted