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!

Graph theory, rank and other characteristics

  1. Apr 16, 2017 #1
    1. The problem statement, all variables and given/known data
    hello, I have this graph and i have to figure out these so to speak characteristics.
    1) find incidence matrix
    2) arrange peak according to rank and layers
    3)draw new arranged graph
    4) find new connection matricies of peaks and arcs
    2. Relevant equations

    3. The attempt at a solution
    I managed to find the incidence matrix which was pretty much easy but I cant manage to understand what is rank of peaks and what is layers in this context ,there are a lot of different notations out there in various sources.
    please help?
    Last edited by a moderator: Apr 17, 2017
  2. jcsd
  3. Apr 17, 2017 #2


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Ranks and layers seem to be standard terminology. It is 'peak' that is uncommon.

    The introduction to this web article gives a good explanation of what a layering of a directed acyclic graph (DAG) is, what a layer is and what a rank is.

    Only 'peak' is not mentioned. A natural guess would be that a peak is either
    • a node from which there are no outgoing arrows, or
    • a node to which there are no incoming arrows.
    Either of these could be chosen, but not both. What does your text book say? I would go for the first one, since I tend to think of arrows as pointing UP.
  4. Apr 19, 2017 #3
    Hi, thanks for your reply.
    Now i understand that node=vertex but why do you think that there should be separation between a node from which there are no outgoing arrows and a node to which there are no incoming arrows? My graph consists of nodes where edges are incoming as well as outgoing.

    I do not have any textbook.

    Now, If i want need to arrange nodes according to rank and layers, i really do not know what to do. Because only definitions i can find about rank in graph theory context is about rank of whole graph not node rank.
  5. Apr 19, 2017 #4


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    I don't understand this question. I did not say anything about separation.
    Where did you get this problem?
    The link I gave defines rank in a way that applies to individual nodes, not the whole graph. It defines how to partition the graph into subsets, and all nodes in the same subset are given the same rank.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted