2 ms·

> There's a simple mathematical explanation for that. If we agree that a state diagram is a directed graph consisting of N nodes, then there are N^2 possible tr

by JadeNB 6y ago

> There's a simple mathematical explanation for that. If we agree that a state diagram is a directed graph consisting of N nodes, then there are N^2 possible transitions (that's the definition of a completely connected graph). A state diagram is usually richer than a directed graph—usually the edges are labelled. This multiplies the number of possible transitions by the number of possible labels. (Also, for anyone interested in comparing with the graph-theoretic terminology, the term "complete graph" (https://en.wikipedia.org/wiki/Complete_graph https://en.wikipedia.org/wiki/Complete_graph) is often used for undirected graphs with no self-loops, in which case there are only \binom n 2 possible edges.)

amw-zero 6y ago
> A state diagram is usually richer than a directed graph—usually the edges are labelled. This multiplies the number of possible transitions by the number of possible labels. This is true. The technical term for this is a "multigraph." > (Also, for anyone interested in comparing with the graph-theoretic terminology, the term "complete graph" (https://en.wikipedia.org/wiki/Complete_graph https://en.wikipedia.org/wiki/Complete_graph) is often used for undirected graphs with no self-loops, in which case there are only \binom n 2 possible edges.) You gave the formula for the number of edges in an undirected graph. The number of edges in a complete directed graph is n^2 - n when transitions from a state to itself is not considered. I take liberty with that fact, and often just say there are n^2 edges in a complete directed graph, since transitions to self don't usually harm the design. Either way, it's O(n^2). As you said though, state diagrams can be multigraphs. In that case, I'm not aware of a general formula for the number of states. But I imagine it would still be O(n^2), just with possibly more edges.

by JadeNB 6y ago

amw-zero 6y ago

> A state diagram is usually richer than a directed graph—usually the edges are labelled. This multiplies the number of possible transitions by the number of possible labels. This is true. The technical term for this is a "multigraph." > (Also, for anyone interested in comparing with the graph-theoretic terminology, the term "complete graph" (https://en.wikipedia.org/wiki/Complete_graph https://en.wikipedia.org/wiki/Complete_graph) is often used for undirected graphs with no self-loops, in which case there are only \binom n 2 possible edges.) You gave the formula for the number of edges in an undirected graph. The number of edges in a complete directed graph is n^2 - n when transitions from a state to itself is not considered. I take liberty with that fact, and often just say there are n^2 edges in a complete directed graph, since transitions to self don't usually harm the design. Either way, it's O(n^2). As you said though, state diagrams can be multigraphs. In that case, I'm not aware of a general formula for the number of states. But I imagine it would still be O(n^2), just with possibly more edges.