Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with directed-graphs
Search options not deleted
user 9025
A directed graph is a graph with directed edges. Loops and 2-cycles are usually allowed. See also the tag *quiver*.
2
votes
Accepted
Minimum number of edges - directed graph with given sums of weights
First, divide the vertex weights into a maximum number of portions that each sum to 0 and handle them separately.
For each set of vertices whose weights sum to 0, you can can implement them as a path …
- 37.7k
1
vote
0
answers
33
views
Both-way flows in a directed graph
Let $G$ be a finite directed graph, and let $s,t$ be two distinct vertices.
Problem $1(s,t)$. Find the maximum number of mutually edge-disjoint directed paths from $s$ to $t$. OK, I didn't think of i …
- 37.7k
2
votes
Name for directed graphs with "balanced cycles"
In network-flow land, this is a "layered network", see for example
this (page 114). Unfortunately, that name is used for lots of things.
- 37.7k
6
votes
Accepted
Length of longest directed circuit in random tournament
A random tournament is strongly connected with probability tending to 1 exponentially fast, and all strongly connected tournaments have hamiltonian cycles.
- 37.7k
4
votes
Accepted
Non-equivalent eulerian trails in $K_{2n+1}$
If I understand your question, you are asking for the number of isomorphism classes of regular tournaments.
There are no exact formulas. See http://oeis.org/A096368 for counts up to 15 vertices.
Th …
- 37.7k
5
votes
Explicit upper bound on the number of simple rooted directed graphs on 𝑛 vertices?
1, 4, 36, 752, 45960, 9133760, 6154473664
Let $a(n)$ be the number you want. If all of the digraphs had a trivial automorphism group, then the number of them would be
$$ \ell(n) = \frac{4^{\binom n2 …
- 37.7k
6
votes
0
answers
69
views
Digraph weak connectivity in $O(V)$ space and $O(V+E)$ time
A digraph is called weakly connected if its underlying undirected graph is connected.
You are given a digraph $G$ with $V$ vertices and $E$ edges as a read-only data structure consisting of lists of …
- 37.7k
3
votes
Accepted
Graph isomorphism problem for minimally strongly connected digraphs
Isomorphism of MSC digraphs is isomorphism-complete. Consider two connected undirected graphs $G,H$ with no vertices of degree 1. It is routine to see that connectivity and minimum degree at least 2 w …
- 37.7k
1
vote
Which directed graphs have a normal adjacency matrix?
For $n=1,\ldots,8$, the number of isomorphism classes of normal loop-free digraphs is apparently 1, 2, 5, 15, 49, 232, 1413, 14961.
If loops are allowed, the counts for $n=1,\ldots,8$ are 2, 6, 22, 10 …
- 37.7k