Circuits or edge-disjoint unions of circuits in a connected graph

Click For Summary
SUMMARY

The discussion focuses on calculating the total number of nonempty circuits or edge-disjoint unions of circuits in a connected graph with ##n## nodes and ##b## edges. The formula presented, ##2^m - 1##, where ##m = b - n + 1## represents the number of fundamental circuits, is confirmed as correct. An example with a graph containing 2 nodes and 4 edges illustrates that there are 3 fundamental circuits, reinforcing the application of the formula to determine the total number of circuits.

PREREQUISITES
  • Understanding of graph theory concepts, specifically circuits and fundamental circuits.
  • Familiarity with connected graphs and their properties.
  • Knowledge of combinatorial mathematics, particularly powers of two.
  • Ability to apply mathematical formulas to graph structures.
NEXT STEPS
  • Study the properties of fundamental circuits in graph theory.
  • Explore advanced topics in combinatorial graph theory.
  • Learn about algorithms for finding circuits in graphs, such as depth-first search.
  • Investigate applications of edge-disjoint unions of circuits in network design.
USEFUL FOR

Graph theorists, mathematicians, computer scientists, and anyone involved in network analysis or optimization will benefit from this discussion.

cianfa72
Messages
2,924
Reaction score
307
TL;DR
Evaluate the number of nonempty circuits or edge-disjoint unions of circuits in a connected graph
Hi,
I've a question related to the graph theory.

Take a connected graph with ##n## nodes and ##b## edges. We know there are ##m = b - n + 1## fundamental circuits.

Which is the total number of nonempty circuits or edge-disjoint unions of circuits ? If we do not take in account the circuit orientation I believe the answer is ##2^m - 1##.

Is the above correct ? Thanks.
 
Physics news on Phys.org
To be more specific consider the following graph with 2 nodes and 4 edges. We have 3 fundamental circuits, but which is the total number of circuits or edge-disjoint unions of circuits ?
appunti.jpg
 

Similar threads

Undergrad Two basic results from measure theory -- on volumes of rectangles
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Edge connectivity of a graph given the number of edge disjoint paths
  • · Replies 1 ·
Replies
1
Views
2K
Graduate Half-face traversal on general polyhedra
  • · Replies 9 ·
Replies
9
Views
3K
Undergrad Can a Topological Space be Both a 1-Manifold and an n-Manifold?
  • · Replies 17 ·
Replies
17
Views
3K
Two networks described by v-i graph: Find voltages when interconnected
  • · Replies 1 ·
Replies
1
Views
1K
Comp Sci Using Single Source Shortest Path Algorithm to find the longest path
  • · Replies 4 ·
Replies
4
Views
2K
Euler circuit in a directed multigraph
  • · Replies 2 ·
Replies
2
Views
5K
Graduate Algebraic topology applied to Neuroscience
  • · Replies 2 ·
Replies
2
Views
4K
Undergrad Prove that a given graph contains a cycle using induction (Graph Theory)
  • · Replies 7 ·
Replies
7
Views
3K
When to Use a Two-Port Representation for a Quadripole in External Circuits?
  • · Replies 1 ·
Replies
1
Views
2K