Are There Missing Minimal Paths or Cuts?

  • Context: Graduate 
  • Thread starter Thread starter brad sue
  • Start date Start date
  • Tags Tags
    System
Click For Summary
SUMMARY

The discussion focuses on identifying minimal paths and cuts in a strongly connected graph with five vertices. The user identified several cuts: {1,6}, {7,3}, {6,4,2}, and {2,5,7}, and paths: {6,7}, {1,2,3}, {1,2,5,7}, and {1,4,7}. It was confirmed that there should be a total of ten paths due to the graph's connectivity, as calculated by the formula for paths between vertices. Additionally, the labels in the graph represent components of the system and their logical connections.

PREREQUISITES
  • Understanding of graph theory concepts, specifically minimal paths and cuts.
  • Familiarity with strongly connected graphs and their properties.
  • Knowledge of combinatorial counting principles related to paths in graphs.
  • Basic graph representation and notation for vertices and edges.
NEXT STEPS
  • Study the concept of minimal cuts in network flow problems.
  • Learn about the structure function in graph theory and its applications.
  • Explore algorithms for finding all paths in a directed graph.
  • Investigate the properties of strongly connected components in directed graphs.
USEFUL FOR

Students and professionals in mathematics, computer science, and engineering, particularly those focusing on graph theory, network analysis, and optimization problems.

brad sue
Messages
270
Reaction score
0
Hi,
please I need help with finding the minimal paths and cuts of the attached figure.

Here for the cuts I found: {1,6}, {7,3}, {6,4,2}, {2,5,7}
for the paths I get: {6,7},{1,2,3},{1,2,5,7},{1,4,7}
Do i miss some paths or cut please?

Also i cannot find the an expression for the structure function, using minimal paths and cuts.

Thank you
 

Attachments

  • system.jpg
    system.jpg
    4.1 KB · Views: 478
Physics news on Phys.org
I am pretty sure there should be ten paths. What do the labels mean? Are they just labels for the edges or distances?
 
hi,
the labels are components of the system with their logical connections. how do you know , i need to have 10 paths?
 
The graph is strongly connected, there is a path between each two vertices. There are five vertices, so there are 4 paths from an arbitrary vertex to another (not including paths to itself), then from another arbitrary vertex there are 3 paths to other vertices not including the first counted path, etc. 4+3+2+1= 10.
 

Similar threads

  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 19 ·
Replies
19
Views
5K
  • · Replies 3 ·
Replies
3
Views
2K
Replies
18
Views
3K
  • · Replies 12 ·
Replies
12
Views
2K
  • · Replies 6 ·
Replies
6
Views
4K
  • · Replies 4 ·
Replies
4
Views
4K
  • · Replies 5 ·
Replies
5
Views
2K
  • · Replies 1 ·
Replies
1
Views
1K
Replies
7
Views
8K