Questions tagged [directed-graphs]
For questions about directed graphs. In a directed graph, each edge is an ordered pair of vertices; we think of it as pointing from one to the other. Use with the (graph-theory) tag.
385
questions
1
vote
1
answer
20
views
Does influence graph have multiple directed edges?
so I am studying about graphs from the book discrete maths by Keneth Rosen 7th edition.Pg:645
However, I am bit unsatisifed with one of the statements from the book. So I would like to get it reviewed ...
-3
votes
0
answers
21
views
Tournament with directed edges [closed]
Prove that one can construct a finite tournament G with at least 101 vertices such that: for any subset S of 100 vertices of G, there is some vertex v for which all 100 vertices s ∈ S have a directed ...
- 1
0
votes
0
answers
23
views
Firefighter problem - finding min-cut in capacitated network (Help)
As my final project my colleagues and I chose to research the firefighter problem.
We could really use your help in the section of MIN-BUDGET regarding the DirlayNet (Directed layered network) ...
- 1
1
vote
1
answer
37
views
Odd girth of line digraph.
Are there any known results on the odd girth of the line digraph of a given digraph? By line digraph of a digraph $D$ having vertex set $V$ and arc set $A$, I mean the digraph whose vertex set is $A$ ...
- 177
1
vote
1
answer
61
views
Lower bound for the maximum number of vertices of a connected rooted sub-digraph of a simple acyclic digraph
Given a simple directed acyclic graph with $n$ vertices and $m$ edges, we get the maximum number of vertices over all connected rooted sub-digraphs of it. Connected rooted sub-digraph means here that ...
- 2,761
0
votes
0
answers
36
views
Bounds on the spectral radius of a directed graph
Suppose $(G_n)$ is a sequence of simple directed graphs with $G_n$ having $n$ edges such that the adjacency matrix $A_n$ of $G_n$ is primitive, and let $(G_n’)$ be a sequence of subgraphs obtained by ...
- 1
0
votes
2
answers
57
views
How many arcs are required to guarantee the existence of cycles?
A directed graph is weakly connected if the undirected underlying graph obtained by replacing all directed edges of the graph with undirected edges is a connected graph.
We know that for an undirected ...
- 1,948
2
votes
1
answer
82
views
Number of Branches on a Tree that spans a grid
I want to count the arrows of a tree that spans a $n$-dimensional grid in a certain way.
Take a $n$-dimensional grid of equal side length $f$. I'll use $n=2$ and $f=4$ in this example, but the ...
- 175
0
votes
1
answer
26
views
Are there any vertex-transitive digraphs with distinct in and out degree
It seems to me like a question that must have been answered somewhere before, but I haven't been able to find anything on this.
Take a vertex-transitive digraph $\Gamma$, that is a directed graph, ...
- 1,095
3
votes
0
answers
56
views
Producing even cycles in directed graphs - Alon and Spencer, Exercise 3.4
Show that there is a finite $n_0$ such that any directed graph on $n>n_0$ vertices in which each outdegree is at least $\log_2(n)-\frac{1}{10}\log_2\log_2n$ contains an even simple directed cycle.
...
- 31
1
vote
1
answer
81
views
Finding paths that satisfy criteria in a large weighted cyclic directed graph
I have a large cyclic weighted directed graph where weight is the duration in days of going from one node to another.
The graph has about 1500 nodes and 100 thousand edges, and the average node in/out ...
- 11
1
vote
0
answers
29
views
Looking for resources on irregular expander graphs
I've been reading up on Expander graphs on the web, papers, books and surveys.
However, all the resources I could find on Google is about regular, connected, non-bipartite (undirected) graphs. The ...
0
votes
1
answer
64
views
How to calculate all cycles in a directed graph?
I am competing in the American Computer Science League (ACSL), and I get problems similar to the following.
Look at this directed graph. Now tell me the number of cycles in said graph.
These ...
0
votes
1
answer
83
views
Prove that $\det(A A^T) = 0$ where $A$ is the incidence matrix of a directed graph
I would like to prove the following result about graphs:
Given a node-incidence matrix $A$ of a directed graph, the determinant of $A A^T$ is $0$.
The element $a_{ij}$ of the incidence matrix $A$ is ...
- 13
1
vote
1
answer
32
views
For every tree of shortest path there is a way of writing the adjacency lists such that there is a BFS thet returns this tree?
A directed graph G=(V,E) is given and I am asked to prove if there is a tree of shortest path of this graph that cannot be returned using BFS. Meaning to say if it is true or not that for every tree ...
- 11
1
vote
1
answer
32
views
Are there a finite number of elementary zero-sum walks in a signed finite directed graph?
Let $G=(V,E,w)$ be a signed directed graph where every vertex $v\in V$ has out-degree $2$, and every directed edge $e\in E$ has sign $w(e)\in\{-1, +1\}$.
A walk $z = (v_1, e_1, v_2, e_2, \ldots, v_{k-...
- 51
4
votes
1
answer
63
views
Succinct represention of a condensed complete directed graph
I'm working on research in multi-agent reinforcement learning, and in the experiments that I'm running now, my six agents are forming a social order. I've been analyzing these experiments for a while, ...
- 177
0
votes
0
answers
45
views
Given a directed graph, can you determine if it can be drawn as a planar graph?
Say a directed graph has loops and has nodes directed towards each other.
I would like to know if there is an algorithm for determining if the graph can be drawn as a planar graph.
- 185
0
votes
1
answer
44
views
Term to describe a subgraph of a digraph where no arcs go into it from outside
What's the shortest way to describe a subgraph of a digraph where, in the original graph, no arcs go into it from outside? Is there a term for this?
Note that it might or might not be connected.
Here'...
- 91
0
votes
0
answers
34
views
directed walk and a directed path
Let D be a directed graph and let u and v be vertices (nodes). Prove that if D has a directed uv-walk then D also has a directed uv-path.
I tried using the process that a walk P is the shortest uv-...
1
vote
1
answer
67
views
Inequality on the number of paths in a graph
Let $G$ be an undirected graph with $n$ nodes and let $a_k$ denote the number of directed paths of length $k$.
Prove that $$a_1 \leq \sqrt{n a_2}.$$
Note that $a \to b \to a$, where $a$ and $b$ are ...
- 11
1
vote
0
answers
76
views
Directed Acyclic Graph Complexity Measures
I have many (millions) of collider-less directed acyclic graphs (DAGs) (they're actually causal graphs, but that's unimportant for this question) I am using to model a process, and I would like to ...
- 10k
0
votes
2
answers
64
views
Is a 𝑢−𝑣 path followed by a 𝑣−𝑤 path is a 𝑢−𝑤 path. [closed]
Can I say a 𝑢−𝑣 path followed by a 𝑣−𝑤 path is a 𝑢−𝑤 path.
Because if there is a path from 𝑢−𝑣 followed by 𝑣−𝑤 I believe there should be a 𝑢−𝑤 path.
I don't know how to prove it.
EDIT:
A 𝑢...
- 279
3
votes
1
answer
562
views
Can a DAG have strongly connected components?
It seems to me, a DAG (the directed graph has no cyclic.) is not possible to have strongly connected components (SCC), but it can have weakly connected components (WCC).
The definition of SCC and WCC:
...
- 133
0
votes
0
answers
62
views
Existence of source/sink in directed acyclic graph with connected complement
The statement I would like to prove is the following:
For any connected acyclic digraph $G=(V,E)$ there exists a
source or sink vertex $v\in V$ such that the graph complementary to
that vertex, ...
- 355
0
votes
0
answers
35
views
Finding MDST in subgraph is enough for MDST problem in the original graph
Let $G = (V, E, w)$ be strongly connected graph. Show that there exists a subgraph $G′ = (V, E′, w)$ of $G$ with $|E′| \le 2(n − 2)$ such for every $r\in V$ , an MDST of $G′$ rooted at $r$ is also an ...
- 1
2
votes
2
answers
113
views
Computing Longest Simple Path in a Particular Digraph
Let $D$ be a digraph as follows:
I want to compute a longest simple path of it.
For an acyclic digraph, there is a method I can run in Python that returns a longest path, but $D$ is not acyclic.
I ...
- 3,124
2
votes
1
answer
57
views
Number of directed graphs on a $3\times 3$ grid where every vertex has both indegree and outdegree $\ge 1$
Consider nine vertices arranged in a square $3\times 3$ grid. Compute the number of directed graphs that can be drawn on the grid by connecting every vertex to its immediate horizontal and vertical ...
- 1,725
0
votes
0
answers
22
views
Graphs - Probability of reaching destination in a graph.
So I am given a graph with a bunch of nodes and links, where links "activate" with a certain probability and can also fail with non-zero probability. We have a source node and a destination ...
- 1
3
votes
1
answer
113
views
How is the expression for Kirchoff's Law obtained from this incidence matrix?
I am following along Chapter 8 ("Applications"), Section 8.2 ("Graphs and Networks") from Gilbert Strang's Introduction to Linear Algebra (4th edition). In this section he shows ...
- 4,462
0
votes
0
answers
29
views
Property of the incidence matrix of a directed graph
I would like to prove the following result about graphs:
Consider a finite set V with an antisymmetric and transitive relation, but strictly non-reflexive, i.e. no element is related to itself (it is ...
- 1
0
votes
1
answer
52
views
Discrete Mathematics - Trees and Relations Question
I am completely stuck on this multiple choice trees question. In this multiple-choice question, more than one option can be correct. I believe this is a trees question; if it is not, then I have gone ...
- 51
2
votes
1
answer
40
views
Find cycles with fixed number of edges without shared vertices in a directed graph
I am trying to find minimum weighted cycles with fixed number of edges without shared vertices in a weighted directed graph. Specifically, say I need to find 4 cycles (one cycle per user) each with 5, ...
- 23
0
votes
0
answers
12
views
Are there recent review papers on random digraph models?
I am developing interest in random digraphs. I would like to have a quick survey of the history, concepts and latest developments in random digraph models. Is there some comprehensive contemporary ...
2
votes
1
answer
107
views
What is the expected length of the longest path in a DAG?
Let's consider a random directed acyclic graph (DAG) with $n$ vertices and $m$ edges. What is the expected length of the longest path in this graph? Is there a function $f(n,m)$ that can approximate ...
1
vote
0
answers
45
views
Question about minimum of the stationary distribution of a random walk on a directed graph
Suppose there is a random walk process on a simple strongly connected directed graph $G=(V, E)$. The random walk follows a transmission matrix in the form $M=AD^{-1}$, where A is the adjacency matrix ...
- 325
-2
votes
1
answer
39
views
how to formulate the following properties formally?
Let (N, E, l), be a labeled directed graph, where N is a set of vertices, E ⊆ N×N is a set of edges, and l: E → L is a function assigning labels from a set L to edges. Let source and target be ...
- 11
2
votes
2
answers
183
views
Finding contracted vertices in a weighted directed graph
Consider an edgeless graph $$g:=(V,E):=(\{1,2,\ldots,n\},\emptyset)$$ and an embedding of $g$ on the 2-dimensional Euclidean plane $\omega:V \rightarrow \mathbb{R}^2$.
Consider the surjection $$\phi:V ...
0
votes
0
answers
139
views
Global efficiency for weighted directed graphs?
I would like to compute the global efficiency of a weighted directed graph. When looking the appendix of Rubinov & Sporns (2009) it seems like there's no difference in the computation:
$$
E^\text{...
- 101
0
votes
0
answers
159
views
Can Dijkstras Algorithm be used for directed graphs with negative edges in only the initial node?
Imagine a directed graph in which the only negative edges are those that leave the initial node s; but all other edges are positive. Can Dijkstra’s algorithm, started at s, fail on such a graph? Prove ...
- 121
1
vote
0
answers
25
views
Number of sink vertices connected to a vertex in a directed acyclic graph
I'm looking for a term in graph theory for the number of sink vertices (or end vertices) connected via a directed path to each vertex in a directed acyclic graph. I mocked up a sample network here, ...
- 11
1
vote
1
answer
128
views
Directed graph branching
Let $G = (V, E)$ a directed graph then a $\textit{branching}$ $ B \ \subseteq E $ is a subset of edges such that there is at most one incoming edge for each vertex $v \in V$. Let $I = \{B \mid \text{ $...
- 301
0
votes
0
answers
31
views
Shortest paths: Does $d(s, t) = d(s, v) + d(v, t ) $ always hold if $v \in p $ where p is the shortest path between $s, t$?
Now I know that there is a distinction between single source shortest path algorithms and all-pair shortest path algorithm . My question is the following:
If we solve the single source (let's say s ) ...
- 807
5
votes
0
answers
108
views
What type of Mathematics, if any, is this? (On curiosities associated with a logo.)
I'm not sure whether I have articulated my curiosity well enough here. Please, therefore, bear with me if I need to edit the question, and please forgive me if this is otherwise a nonsense question ...
- 43k
0
votes
0
answers
50
views
Graph theory: name for a strongly connected component where every edge is bidirectional?
Hi :) I was wondering if there is a term for a strongly connected component in a directed graph where every edge in the component is bidirectional. E.g. Graph1 would qualify, but graph2 would not, ...
0
votes
0
answers
78
views
What "tool" to extrapolate traffic data on graph used for routing (Open Street Maps).
Background (non-math):
I'm planning to use Open Street Maps data to find the fastest route by car between points. Data is a directed graph where vertices represent locations, and edges are routes. ...
2
votes
0
answers
480
views
Why can matrix rounding be seen as a max flow problem?
For a general max flow problem, we know that each intermediatte node must give away the same amount of flow it receives. Besides this, we also know that the amount of flow that leaves the origin node (...
- 1,520
0
votes
1
answer
27
views
Is it possible to have more than one complete directed graphs? And if yes, how many? I found a formula but I can't make sense of it.
3Cn2 = 3[num of arcs in undirected graph for some reason]
Is the formula I found relating to this, I would imagine it means for every node you can either have an arc pointing to it, from it, or both ...
3
votes
1
answer
34
views
Terminology for rooted directed graph with no directed cycles
I'm working on a algorithm that creates a rooted directed graph where cycles exist, but no directed cycles.
So the set of vertices in this graph contain a root and leaves (just like a tree), it allows ...
- 33
1
vote
0
answers
135
views
Number of loops in a type of directed multigraph
I am interested in finite directed multi-graphs with one connected component, where each vertex comes with exactly 1 edge pointing out from it, which can point to another vertex, or itself. So self-...
- 382