# Graph theory, rank and other characteristics

• prehisto

## Homework Statement

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

## The Attempt at a Solution

I managed to find the incidence matrix which was pretty much easy but I can't 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:

## Answers and Replies

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 textbook say? I would go for the first one, since I tend to think of arrows as pointing UP.

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 textbook say? I would go for the first one, since I tend to think of arrows as pointing UP.

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.

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
I don't understand this question. I did not say anything about separation.
I do not have any textbook.
Where did you get this problem?
. Because only definitions i can find about rank in graph theory context is about rank of whole graph not node rank.
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.