# Equilibrium Points of Directed Graphs

• Pauly Man
In summary, the maximum number of equilibrium points of a directed hypercube in Rn is 2^(n-1). This can be proven by considering the construction procedure of "doubling" the n-dimensional hypercube and connecting each original point with its double, and using induction to find the number of unconnected vertices. Alternatively, it can be shown by considering the number of edges for which the direction is known when there are a certain number of equilibrium points, and finding the maximum number of equilibrium points when all edges have a known direction, which is 2^(n-1).
Pauly Man
Suppose I have a directed graph in Rn. Where the graph is a hypercube, (a square in R2, a cube in R3 etc).

Suppose I define an equilibrium point of a directed graph to be a vertex such that I can travel from any adjacent vertex along an edge to that vertex. What is the maximum number of equilibrium points of a directed hypercube in Rn?

As an example in R2:

Code:
*****<*****
*          *
^          ^
*          *
***** >*****

(For some reason the graph isn't formatting properly, hopefully you can imagine that it is supposed to be a square).

The upper left corner is an equilibrium point for the directed hypercube.

I now wish to work out how to find the maximum number of equilibrium points possible in a directed hypercube in Rn. (Any ideas??)

Last edited:
Unfortunately I could not decipher the plotted graph, but in any case you should consider the proyection of the graph on the plane and then argue, as is usually done in graph theory.

It's pretty straightforward to show that this is the same as the size of the largest set of unconnected vertices. For that, you can consider the construction procedure of "doubling" the n-dimensional hypercube and connecting each original points with its double. Then using induction you find 2^(n-1) for n dimensions.

There's probably a prettier way to do it, but graph theory isn't my thing.

Originally posted by damgo
It's pretty straightforward to show that this is the same as the size of the largest set of unconnected vertices. For that, you can consider the construction procedure of "doubling" the n-dimensional hypercube and connecting each original points with its double. Then using induction you find 2^(n-1) for n dimensions.

There's probably a prettier way to do it, but graph theory isn't my thing.

Thanks damgo. I sat up last night before going to bed and thought about the problem. I came up with this argument (which I'm pleased to see results in the same conclusion you came up with).

There are n2n-1 edges in a hypercube. If we know that we have one equilibrium point then we know the direction of n edges. So it follows that we don't know the direction of n(2n-1-1) edges. If we know of another equilibrium point then we know that it cannot share any edges with the previous equilibrium point, and so we know the direction of another n edges. We therefore do not know the direction of n(2n-1-2) edges.

Continuing on in this fashion we find that for a equilibrium points we have n(2n-1-a) edges for which we are unsure of the direction.

The maximum number of equilibrium points occurs when we know the direction of every edge, which occurs when:

n(2n-1-a) = 0
a = 2n-1

Note that I have edited the graph above, so now it hopefully makes sense).

## 1. What are equilibrium points in directed graphs?

Equilibrium points in directed graphs refer to the set of vertices where the number of incoming edges is equal to the number of outgoing edges. In other words, at equilibrium points, the total flow of edges into a vertex is equal to the total flow of edges out of that vertex.

## 2. How are equilibrium points different from other types of points in directed graphs?

Equilibrium points are different from other types of points, such as sources and sinks, because they represent a balance in the flow of edges. Sources have more incoming edges than outgoing edges, while sinks have more outgoing edges than incoming edges. Equilibrium points have an equal number of both incoming and outgoing edges.

## 3. Why are equilibrium points important in directed graphs?

Equilibrium points play a crucial role in understanding the behavior and stability of directed graphs. They can help identify patterns and cycles in a graph and determine if a system will reach a steady state or continue to change over time. Equilibrium points also have applications in fields such as economics, biology, and computer science.

## 4. How can equilibrium points be calculated in a directed graph?

Equilibrium points can be calculated by analyzing the adjacency matrix or by using algorithms such as the Tarjan's algorithm or the Bellman-Ford algorithm. These methods can determine which vertices have an equal number of incoming and outgoing edges, and thus, are equilibrium points.

## 5. Can a directed graph have more than one equilibrium point?

Yes, a directed graph can have multiple equilibrium points. In fact, most directed graphs will have more than one equilibrium point. This means that there can be multiple vertices where the flow of edges is balanced, and the system reaches a steady state. However, the number of equilibrium points may vary depending on the structure of the graph and the flow of edges within it.

• General Math
Replies
21
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
5
Views
1K
• General Math
Replies
4
Views
2K
• General Math
Replies
1
Views
1K
• Engineering and Comp Sci Homework Help
Replies
1
Views
2K
• Calculus and Beyond Homework Help
Replies
2
Views
4K
• General Math
Replies
2
Views
2K
• MATLAB, Maple, Mathematica, LaTeX
Replies
2
Views
1K
• General Math
Replies
4
Views
2K
• Introductory Physics Homework Help
Replies
5
Views
776