Graph theory, rank and other characteristics

Click For Summary

Homework Help Overview

The original poster is working on a graph theory problem involving characteristics such as incidence matrices, ranks, and layers of nodes (referred to as peaks). They express confusion regarding the definitions and applications of rank and layers in this context.

Discussion Character

  • Conceptual clarification, Assumption checking

Approaches and Questions Raised

  • The original poster has successfully found the incidence matrix but is struggling to understand the concepts of rank and layers, particularly in relation to nodes. They question the terminology used, specifically the term "peak," and seek clarification on how to arrange nodes according to rank and layers.

Discussion Status

Some participants have provided insights into the standard terminology of ranks and layers, suggesting that "peak" may refer to nodes with specific characteristics. They also reference external resources to clarify these concepts. However, there is no explicit consensus on the definitions, and the original poster continues to seek guidance on how to proceed with their arrangement of nodes.

Contextual Notes

The original poster does not have a textbook to reference and is relying on external definitions, which may vary. They note that their graph contains nodes with both incoming and outgoing edges, complicating their understanding of the rank concept.

prehisto
Messages
111
Reaction score
0

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
14v6vqv.jpg

Homework Equations

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:
Physics news on Phys.org
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.
 
andrewkirk said:
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.
 
prehisto said:
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.
prehisto said:
I do not have any textbook.
Where did you get this problem?
prehisto said:
. 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.
 

Similar threads

Replies
9
Views
2K
  • · Replies 6 ·
Replies
6
Views
3K
  • · Replies 12 ·
Replies
12
Views
4K
  • · Replies 8 ·
Replies
8
Views
2K
  • · Replies 1 ·
Replies
1
Views
3K
  • · Replies 7 ·
Replies
7
Views
4K
  • · Replies 11 ·
Replies
11
Views
3K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K