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.

Filter by
Sorted by
Tagged with
3 votes
1 answer
15 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 ...
user avatar
  • 33
0 votes
0 answers
6 views

Is there any special condition on finding the inital spanning tree for a minimum cost flow problem?

I was wondering... When we are working with a standard minimun cost flow problem, is there any additional condition on the initial basis besides defining a spanning tree? Take the graph below as an ...
user avatar
  • 609
0 votes
0 answers
9 views

Clustering of directed graphs satisfying priority constraints

I recently ran into a problem related to directed graph clustering, but don't know how to solve it. There is a directed acyclic graph $G = (V,E)$, where $V$ is the set of vertices, and $E$ is the set ...
user avatar
  • 431
1 vote
0 answers
27 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-...
user avatar
0 votes
1 answer
24 views

Dynamic programming efficient network

Hello I have a dynamic programming related question. How can I compute the shortest path in hops from starting vertex u to ending vertex v, with the constrain that the vertices and edges will have an ...
user avatar
-1 votes
1 answer
80 views

Find the shortest path in a graph which must pass certain nodes.

I have a directed weighted graph with 16 vertices. One node (bottom left side) is labeled "S" as the starting point, the objective is to find the shortest ...
user avatar
  • 1
0 votes
1 answer
15 views

Find edges that if removed increase value of shortest path in weighted directed graph

Let's say I have a directed weighted graph $G=(V,E)$ where the weights are all positive. Let $d_G(s,t)$ be the value of the shortest path in $G$ between two nodes $s$ and $t$. I want to find the set ...
user avatar
0 votes
1 answer
35 views

Perron-Frobenius theorem for reducible non-negative matrices

Let $M$ be a non-negative matrix ($M_{ij}\geq 0$ for all $i,j$). If $M$ is irreducible, then we know that there exists an eigenvalue $\lambda$ of $M$ that equals the spectral radius $\rho(M)$ and has ...
user avatar
  • 1,083
0 votes
0 answers
16 views

Fiedler Vector for directed and not strongly connected graph

Anyone know if there is any work that deal with Fiedler vector graph partition, for the case of connected, directed, but not strongly connected graph? Thanks
user avatar
  • 1
1 vote
1 answer
23 views

Deduce the undirected edge version of Menger's theorem from the directed version

Menger's theorem says, in directed graph $G$, $k$ is the maximum number of arc-disjoint $st$-dipaths if and only if the size of the minimum $st$-cut is $k$. Use this version of Menger's theorem to ...
user avatar
  • 13
0 votes
0 answers
17 views

Find the upper bound probability of a collision in a packet scheduling problem - Exercise

Let $G$ be a graph representing a network. On this network we have $N$ packets, each with a starting node, a path and an end node. Time is discrete, so each packet move only at a certain instant. When ...
user avatar
0 votes
0 answers
19 views

Calculating number of edges in a directed graph with a small constraint.

I have a graph of events. Every time '$t$' only $2$ events may occur (i.e. $2$ vertices). Each vertex is unique and let's define it as: $V(event, t)$ where: event is either "$1$" or "$2$...
user avatar
0 votes
0 answers
31 views

Cliques in an arbitrary undirected graph

I have to describe (no pseudocode needed) how to find large cliques in an arbitrary undirected graph. All vertices have to be connected with each other and crossing is allowed. This is one approach: ...
user avatar
  • 3
0 votes
0 answers
48 views

Ordered Graph Problem

Let G = (V, E) be a directed graph with nodes v1, v2, . . . , vn. We say that G is an ordered graph if it has the following properties. (i) Each edge g Let G = (V, E) be a directed graph with nodes v1,...
user avatar
0 votes
0 answers
19 views

Given a directed graph with $n$ nodes where min out degree of a node is $m$ and max in degree is $1$, prove $n>2m$

Directed graph with $n$ nodes with the following constraints: Maximum in degree of any node: 1 Minimum out degree of any node: $m$ Prove that $n>2m$ I tried proof by contradiction, saying that let ...
user avatar
0 votes
0 answers
28 views

Each directed graph Has 0 crossing edges in Some DFS Run?

I found the following claim online: For each directed graph, There is DFS run such that it contains 0 crossing edges. Why is this correct at all? I think I found a counter example, consider a graph ...
user avatar
  • 1
0 votes
1 answer
31 views

Relationship between the minimum cost rooted k-edge connected subgraph and the unrootd version in undirected graphs

In the undirected rooted k-edge connected subgraph problem, the goal is to find a minimum cost subgraph in which there are k edge-disjoint paths between the root and each vertex in the graph. The ...
user avatar
  • 137
1 vote
0 answers
20 views

Islands and bridges proove that after removing a bridge there are at most 3 bridges which let you get to any other island

The city is built on islands, some of which are connected by bridges. There is a maximum of one bridge between two islands, you can only go one way over the bridge, but you can get from any island to ...
user avatar
  • 161
6 votes
1 answer
62 views

Möbius inversion for categories instead of directed graphs

In Tom Leinster, The Euler Characteristic Of A Category, the author generalizes the notion of Möbius Inversion for posets to finite categories. This violates the principle of equivalence. A possible ...
user avatar
0 votes
1 answer
44 views

Ordering vertices of a bipartite digraph satisfying a specific property

Let $D$ the bipartite digraph with vertices bipartitions $A$ and $B$ such that it has only arcs of $A$ to $B$. It easy to see that $D$ is acyclic (not contains directed cycle). I know that $D$ has a ...
user avatar
  • 81
0 votes
1 answer
7 views

How can one efficiently group the nodes of a directed acyclic graph to make collective nodes?

The adjacency matrix $A$ of the transitive closure of a directed acyclic graph can have a `checkerboard' pattern like \begin{equation} A = \begin{pmatrix} 0 & ? & ? & ? & {\bf a} &...
user avatar
0 votes
1 answer
94 views

convert any non DAG into DAG (Directed acyclic graphs)

It is always possible to convert any non DAG into a DAG, by changing its order, if not limiting the number of changes. Is this true? Is there a proof? [Newly Updated/Edited for exact definitions] Non ...
user avatar
1 vote
1 answer
53 views

For which directed graphs does Pascal's recursive method work for finding the number of paths?

In math contests, such as those run by the University of Waterloo CEMC in Canada or the AMC series of contests in the US, there are frequently questions of the following kind: Given an $m\times n$ ...
user avatar
  • 3,213
3 votes
0 answers
72 views

Rock-Paper-Scissors and Hadamard matrices

While playing ``rock paper scissors'' with my daughter it became obvious that she wanted to add a few elements to the game, Specifically the fox and the well. A bit later we added the match and the ...
user avatar
  • 429
1 vote
1 answer
98 views

Maximum number of edges in a balanced graph with n points, without small cycles (say, of length 2, 3, 4)

Let's say we have $n$ points numbered from $1$ to $n$. What is the maximum number of directed edges possible on a graph with these $n$ points: without any cycle of length $\leq k$, for example ...
user avatar
  • 1,597
3 votes
1 answer
162 views

Let $T$ be a tournament directed graph (round robin). Prove that there is an odd number of Hamiltonian paths in the graph

Let $T$ be a tournament directed graph (round robin). Prove that there is an odd number of Hamiltonian paths in the graph. I am aware that this question may be considered a duplicate of this one: The ...
user avatar
5 votes
2 answers
92 views

What is the name of this digraph created from other digraphs?

Let $D_1, D_2, ..., D_n$ be digraphs of various sizes and let $C$ be a diagraph with $n$ vertices $\{1,...,n\}$. Construct a new digraph, $D$, whose vertex set is $V(D) = V(D_1) \cup \cdots \cup V(D_n)...
user avatar
  • 1,409
1 vote
1 answer
69 views

Directed polyhedral graph with $d^+(v) \geq 1$ and $d^- (v) \geq 1$

Let $\Phi$ a convex polyhedron, with each edge being a vector (id est a directed line segment). For each vertex of the spatial object, let us define its $d^+(v)$ the number of vectors 'leaving' that ...
user avatar
1 vote
1 answer
120 views

General way to count the number of paths in an out-tree?

I'm trying to find a succinct and general way to count the number of paths in a directed graph with only tree edges (assuming all nodes have exactly the same number of children). For example, the ...
user avatar
  • 113
1 vote
0 answers
37 views

Graph automorphisms and union of graphs

I have a question, so please allow me to ask here. Thank you. My question is: Let $G$ be a union of directed graphs $G_1, \ldots , G_n$, that is, $G=G_1\cup\cdots\cup G_n$. If $f:G\to G$ is a morphism ...
user avatar
  • 91
0 votes
0 answers
39 views

What is the name for this class of rooted DAGs?

Is there a name for the class of directed acyclic graphs where, for every node with more than one predecessor, none of the direct predecessors are in any of the others' ancestry? I.e. the most recent ...
user avatar
  • 554
7 votes
1 answer
133 views

Tour of chess king

Consider lame chess king that can move only one cell left, down and diagonal upright. Consider square chess board. Question: Can such a king visit all cells of a board (each cell only once) and end up ...
user avatar
1 vote
1 answer
34 views

Shortest path with jumps (dynamic Bayesian network)?

Suppose I have the following graph structure: It has the following properties: There are four states $\mathcal{S} = {q,s_1,s_2,s_3}$ where $q$ is some origin state where we start from (though it is ...
user avatar
  • 632
1 vote
1 answer
41 views

What is the most unambiguous digraph representation of NAND/NOR?

Is there an official or standardized way to represent the basic boolean operations with directed graphs? (I don't mean like in circuit diagrams.) If so, what is it? And if not, I would also accept an ...
user avatar
  • 4,969
0 votes
1 answer
30 views

What is a hypergraph consisting of one edge leading from itself to itself?

Is this indeterminate? Undefined? Meaningless? I became confused when I looked at it by starting with $$(A \to B) \to (A \to B). \qquad\label{1}(1)$$ Since both ends of this edge are this edge, it's ...
user avatar
  • 4,969
1 vote
0 answers
74 views

When is a directed graph a category?

This question is taken from Category Theory for Programmers by Bartosz Milewski (1.6). Q: When is a directed graph a category? My intuition is that for a directed graph $G$ to have category ...
user avatar
  • 219
1 vote
1 answer
33 views

Cycles in a tensor product of directed graphs

I have the following basic questions for the tensor product of directed graphs: Consider two directed graphs $G_1=(V_1,E_1)$ and $G_2=(V_2,E_2)$. Is it true that in their tensor product graph, $G_1 \...
user avatar
  • 5,384
0 votes
1 answer
146 views

Does there exist a tournament with exactly two Hamiltonian paths?

A tournament is a complete directed graph. A Hamiltonian path is a path that crosses each vertex exactly once. My conjecture is no. I have tried using induction, proof by contradiction, all to no ...
user avatar
1 vote
1 answer
76 views

Directed graph isomorphism condition correctness

I'm currently working on a project and I've hit a bit of a stumbling point regarding one part related to directed graph isomorphism. To put it short, I have to find all graphs with N = 1,2,3,4 ...
user avatar
  • 13
0 votes
1 answer
30 views

stationary distribution of directed graph [closed]

How can we calculate the stationary distribution for any directed graph, let's say this one. What are the steps? This is the transition matrix , i did: $$ A=\left(\begin{array}{cccc} 0 & \frac{1}{...
user avatar
  • 15
0 votes
0 answers
123 views

Basic Homology Question on Directed Graphs – Rules of Orientation

SECOND EDIT: I start to understand (a bit) what is going on, but still an answer is much needed. Below I edited the question (along with the title) to point out the new little things I got. FIRST ...
user avatar
  • 3,799
0 votes
0 answers
86 views

De Bruijn sequence and graphs

Claim: In every De-Bruijn sequence all characters have the same number of occurrences. True/False? We went over De-Bruijn sequence in our algorithms class and I don't understand it at all. Running a ...
user avatar
3 votes
2 answers
219 views

How many walks of length 8 are there in G

Let G be the following directed graph How many walks of length 8 are there in G, from vertex A to vertex H? One of the walk I found is this: $A \to B$, $B \to F$, $F \to E$,$E \to A$, $A \to B$,$B \...
user avatar
  • 325
2 votes
1 answer
61 views

How many different ways can single directed edge be added.... (graph theory)

Let G be the following directed graph: In how many different ways can a single directed edge be added to G3 so that there is a cycle of length 8 starting at vertex A? I tried a few ways of inserting ...
user avatar
  • 325
0 votes
0 answers
37 views

not quite biconnected component in DAGs

In undirected graphs, a "biconnected component" is a maximal subgraph containing no cut-vertices, that is, vertices whose deletion increases the number of connected components. For directed ...
user avatar
  • 168
0 votes
0 answers
39 views

Conditional Independence on Directed Graphs

In my lecture material, there is given following directed graph: a-->c-->b The graph can be represented by the factorization: $$p(a,b,c)=p(a)p(c|a)p(b|c)$$ The task is to check, whether $a$ and ...
user avatar
0 votes
0 answers
96 views

Distance between vertices in a directed graph

We know that an unweighted undirected graph $G = (V(G), E(G))$ with the geodesic distance $d_{G}$ is a metric space (if we allow $d_{G}$ to attain $\infty$ or if $G$ is connected)(we'd better say an ...
user avatar
  • 246
1 vote
2 answers
95 views

Canonically enumerating all finite transversals of this curious labeled directed graph

In a paper I am working on, a puzzling "game" has arisen. In this problem, I am trying to canonically enumerate all ways of traversing a specific labelled directed graph. However, this is ...
user avatar
  • 3,766
2 votes
1 answer
72 views

Show that the set of nonnegative numbers partially ordered by divisibility has a unique maximal element.

I came across the following question while studying partial orders: Consider the nonnegative numbers partially ordered by divisibility. Show that this partial order has a unique maximal element. ...
user avatar
  • 45
0 votes
1 answer
65 views

Covering edge in a DAG

The book from which I am studying graph theory has this definition of a covering edge: If $a$ and $b$ are distinct nodes of a digraph, then $a$ is said to cover $b$ if there is an edge from $a$ to $b$...
user avatar
  • 45

1
2 3 4 5
7