Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
7 views

Directed Graphs

I'm currently struggling with directed graphs. What does it mean when an allocated graph has a minimal vertex of p E P? What's a minimal element? What does it mean if something is acyclic and has a ...
1
vote
0answers
16 views

How to construct conceptual models for graphs?

Construct conceptual models for the following types of graphs, using either ORM (Object-Role Modeling), ER (Entity-Relationship), or UML Class Diagrams: Directed graphs consist of nodes and directed ...
0
votes
0answers
24 views

Formulate a labeled directed graph

Given a labeled directed graph $〈N,E,l〉$ with $N$ a set of vertices, $E \subseteq N\times N$ a set $L$ to edges. Let source and target be functions on $E$ such that source$(s,t)=s$ and target $(s,t)=t$...
0
votes
1answer
75 views

What is the equivalent of a tree for directed graphs?

A tree is defined as a connected acyclic undirected graph at page 171 of this online book. What is the equivalent of a tree for directed graphs? A connected acyclic directed graph (i.e. a connected ...
1
vote
1answer
35 views

Upper bounds on the solution to a directed route inspection problem

If for any strongly connected digraph $D$ we define $\lambda(D)$ to be the length of any shortest closed walk traversing every arc in $D$, then does there exist some constant $m\in\mathbb{R}$ such ...
0
votes
1answer
39 views

Need Algorithm or sequences of steps to solve this problem.

It's 2009 and you are staying in Oak City for the summer. Because of its history leading to people-centric urban planning, it has a free, well-planned, and timely public transit system, unlike the MTA....
2
votes
0answers
25 views

Meeting walks on directed graphs

Consider a directed graph $G = (V,A)$. For every vertex $v \in V$ we have $d$ directed edges out of $v$, which we'll denote $v(1), v(2), \dots, v(d)$. Given a sequence $i_1, i_2, \dots, i_\ell \in \{...
1
vote
1answer
9 views

How are the edges defined in this digraph?

So I am trying to understand how the number of edges are defined in this graph, I get that the number of vertices of L equals the number of edges of D, but what does the definition of E' mean for the ...
2
votes
1answer
54 views

Number of trails in a complete digraph with loops

Consider a directed graph $G_n = (V, E)$ where $V = \{v_1, ..., v_n\}$ and $E=\{e_{ij}\ \forall\ i,j\in [\![1,n]\!]\}$, ie. all possible edges exist, including from a vertice to itself. I'm trying to ...
0
votes
0answers
20 views

Obtaining spanning trees by eliminating one path from a graph

Consider a bridgeless connected graph $G=(V,E)$. Is it then always possible to find a spanning tree $T$ such that the complement $E\setminus T$ is a path? Now consider a spanning tree $T$, and choose ...
0
votes
0answers
26 views

How could I obtain this approximation of the May-Wigner theorem?

I'm trying to understand the complete proof of the May-Wigner theorem. We have a real random $n\times n$ matrix $B$ with its non-zero elements $B_{ij}$ are chosen independiently from a fixed ...
0
votes
0answers
18 views

nonnegative flow can be decomposed into a nonnegative linear combination of directed $s–t$ paths and directed cycles.

I was asked to prove the following: Let $D = (V, A)$ be a directed graph and $s, t ∈ V$ be distinct. If $f ≥ 0$ is an $s–t$ flow (that is, $f$ is an $s–t$ flow and $f$ is nonnegative) with $\text{...
0
votes
0answers
44 views

Weighted digraph with AND-OR vertices, search algorithm - independent solution from a vertex for which each involved vertex has same sub-solution?

I have a weighted digraph (with cycles) search problem where, given a known starting vertex, I wish to find the 'least weighted' solution to terminating vertices (there may be multiple solutions). In ...
2
votes
0answers
28 views

Chordal Graph to Directed Acyclic Graph

I have seen an exercise which says an undirected graph $G=(V,E)$ is chordal if and only if the edges of $G$ can be oriented with directions, such that the resulting graph $D=(V,A)$ has the following ...
1
vote
1answer
31 views

Path Property of Directed Acyclic Graphs

Suppose we are given a directed acyclic graph $G$, and each node is assigned a label with two real numbers like in the following example. We are given a set of source vertices and a set of sink ...
3
votes
2answers
43 views

Are diagrams of a quiver the same as small diagrams

I've just started to wrap my head around category theory, and came across two (from my perspective not obviously equivalent) definitions of a (small) diagram in a category $\mathcal{C}$: Definition 1 ...
0
votes
1answer
22 views

Sol'n in directed weighted cyclic graph to terminating vertex: such that all vertices along path have same independently given solution?

We’re trying to work out if, using a directed weighted cyclic graph, with one (in this example) ‘terminating’ vertex ‘Z’ (but potentially other terminating vertices are available): Is it possible to ...
2
votes
2answers
44 views

In how many different ways can I get from A to B?

I can only use horizontal and vertical arrows, like in the picture, and I must get from $A$ to $B$ using only $4$ horizontal arrows and $3$ vertical arrows. (One arrow counts as the line connecting ...
13
votes
4answers
2k views

What is a DAG (Graph Theory)?

I am reading this link on Wikipedia; it states the following definition is given for a DAG. Definition: A DAG is a finite, directed graph with no directed cycles. Reading this definition believes me ...
-1
votes
1answer
34 views

Algorithms to obtain all highest weight paths in directed acyclic graph

I want to identify all of the highest-weight paths between all of the start and end nodes of a directed acyclic graph with positive weights. Calculating the scores of all possible paths is ...
1
vote
1answer
37 views

Partitions of the set of vertices of a directed graph

Consider a directed graph and a partition $P$ of its set of vertices. We construct a new partition $P'$ of this set as follows: declare $v_1$ and $v_2$ to be in the same part of the partition $P'$ if ...
2
votes
1answer
29 views

Number of weak components in powers of imprimitive digraphs

Given any strongly connected digraph $G$ and any $n\in\mathbb{N}$ if we let $d(G)$ be the greatest common factor of the lengths of all the directed cycles in $G$ then does the $n^{\text{th}}$ power ...
1
vote
0answers
7 views

Can the Borda count be used to select a distribution and not just a single choice?

Suppose I have n individuals and n unique, indivisible objects of potential value. I want to allocate those objects so as to make total welfare as great as possible, subject to the constraint that no ...
2
votes
0answers
40 views

Kernel Graph problem

as a homework project I received Kernel Graph problem, which is defined as: Does $G$ possess a kernel, i.e. a subset $W$ of the nodes $V$ such that no two nodes in $W$ are joined by an edge in $A$ ...
6
votes
1answer
93 views

Dominating sets in tournaments; is $2^{n+1}-2$ tight?

A tournement is a directed graph such that for every pair of distinct vertices $\{x,y\}$, there is either an edge from $x$ to $y$ or from $y$ to $x$, but not both. I will use "$x\to y$" to mean "there ...
1
vote
0answers
34 views

Does a finite, strongly-connected, labeled digraph with no non-trivial automorphism always have a unique path?

Assume that a digraph is finite and strongly connected, and that all edges and vertices bear labels from some set. Let $f(v)$ be the label of vertex $v$, and $f(e)$ be the label of edge $e$. Say that ...
3
votes
1answer
33 views

Any standard name for this graph?

Is there any standard name for the three-vertices tournament which is not a directed triangle (equivalently, for the non-triangle orientation of $K_3$)? Thank you!
2
votes
1answer
48 views

Counting the directed paths in a particular directed graph

I want to find out how many directed simple paths from $s$ to $t$ are in the following directed graph $G=(V,E)$. $$\begin{align} V=&\{s, v_1, v_2,\ldots, v_n, t\}, \quad n=2k, k \in \mathbb{N} \\ ...
0
votes
4answers
48 views

What is the probability of passing through a node in a directed graph

Say I have a directed graph with no cycles like this one. And say someone travels along it choosing a random edge to go down at every node. We know that the person walking starts from node 0 and is ...
2
votes
1answer
26 views

A Complete Digraph is an Undirected Graph?

Can I consider the Undirected Graph as a special case of Digraphs where all edges points for both directions? A complete (completely connected) digraph turns to an undirected graph?
1
vote
1answer
20 views

Show that there are k directed walks from a to b in gamma having no common directed edge pairwise

Let $\Gamma$ be a digraph, $k$ a natural number and $a$, $b$ vertices in $\Gamma$ such that $$ \operatorname{outdegree}(a)-\operatorname{indegree}(a)=\operatorname{indegree}(b)-\operatorname{outdegree}...
0
votes
4answers
245 views

Can an undirected graph be disconnected?

This may be a rather trivial question but I am still trying to get the hang of all the graph theory terms. Nonetheless, I haven't found a source that explicitly says that an undirected graph can only ...
1
vote
1answer
26 views

Relation between cut families and existence of directed cycles

I would like to know what you think of the following statement and, in case it is true, how would you prove it. Consider a directed graph $G=(V,A)$ where every vertex has degree higher or equal than ...
1
vote
2answers
149 views

Having No Directed Cycles Guarantees a Vertex of Zero Outdegree

Is it true that a directed graph with a finite number of vertices and with no directed cycles has at least one vertex whose out-degree is zero? Here is my idea: Suppose there is no vertex with out-...
1
vote
0answers
187 views

What is the minimum number of edges a graph can have with strongly connected components of at least $3$ vertices each?

This is a homework question that has me stumped: Let $G$ be a directed graph with $\boldsymbol n$ vertices and $\boldsymbol k$ strongly connected components (with $1 < k \leq \left\lfloor\dfrac{...
1
vote
1answer
125 views

There exists a permutation $(A_1, \ldots , A_n)$ of the vertices $V =\{1,\ldots,n\}$ such that for all $i\in\{1,\ldots,n−1\}$, $(A_i,A_{i+1})\in E$.

Let $G = (V,E)$ be a directed graph on $n$ vertices, $V = \{1, \ldots,n\}$, such that for every pair of distinct vertices $i, j \in V$, exactly one of the two possible directed edges $(i, j)$ or $(j, ...
2
votes
1answer
36 views

How to to turn round robin word problem into formal argument?

A round-robin tournament consists of $n$ players and all possible games between any two players. Each game can result in win or loss of a player but no draws are allowed. A champion is a player $A$ ...
2
votes
0answers
40 views

Turning a regular directed graph into a regular graph

Let $G$ be a $k$-regular directed graph, that is, a directed graph such that each vertex has $k$ edges going in and $k$ edges going out of it, and suppose further that $G$ has no loops. We can ...
0
votes
0answers
61 views

Algorithm to remove “uninteresting” nodes in a DAG

If I have a directed, acyclic graph and I'm given some set of "interesting" nodes within that graph, is there an algorithm to remove other nodes and shorten the paths between the interesting nodes ...
1
vote
1answer
40 views

Does $A \perp B\mid C$ implies anything when we already know $A\perp B$?

I am confused with this conditional independence situation. If we already know $A$ and $B$ are independent random variables, is there any point of statement like $A\perp B\mid C$? Does it say anything ...
0
votes
0answers
19 views

Conditional Independence DAGS Prove/Disprove

I want to prove or disprove the following property (and provide the appropriate DAG if disproving): $X \perp Y | Z$ and $X \perp W | Y$ implies $X \perp W|Z$ I have already proven in an earlier ...
1
vote
1answer
65 views

Combinatorics- Dividing students into teams [duplicate]

A class of 37 is to be divided into teams, and each student in the class must be a member of exactly one team. However, each student dislikes three of their classmates. The dislike between students ...
0
votes
0answers
31 views

Does the transpose graph has the same number of topological sorts as the original graph?

I've just started Introduction to Algorithms, and I've encountered the following question: Let $G=(V,E)$ be a directed graph. Assume that G has exactly 1000 different topological sorts. What can be ...
1
vote
1answer
48 views

Ordered analogue of the chromatic polynomial

Let $G=(V,E), E\subseteq V^2$ be a finite directed graph. For $n\in\mathbb{N}$, consider $$\chi_{G}^{\leqslant}(n)=\#\Big\{f : V \to \{1, \ldots, n\}\ \Big|\ \big(\forall (u,v)\in E\big)\big(f(u) \...
1
vote
1answer
573 views

Laplacian of a directed weighted graph

I know that for a simple undirected graph $\mathcal{G}(V,E) $ the Laplacian matrix $L$ is defined as: $$ L:=D-A$$ where $D$ is the degree diagonal matrix and $A$ is the adjacency matrix of $\mathcal{G}...
0
votes
1answer
404 views

Graph theory - Shortest closed walk is a cycle?

So I'm trying to prove the lemma: "The shortest positive length closed walk through a vertex is a cycle." Defs: A closed walk is a walk that begins and ends at the same vertex. A cycle is a positive ...
1
vote
0answers
205 views

Say that a tournament T has 2-property, if for every distinct vertices u, w ∈ V ( T ), T has a (directed) u,w-path of length exactly 2.

Say that a tournament T has 2-property, if for every distinct vertices $u,w \in V(T)$, T has a (directed) u,w-path of length exactly 2. (In particular, if T has 2-property, then every vertex of T is a ...
0
votes
0answers
25 views

If $A$ is an adjacency matrix of a labeled multi-digraph is the $(i,j)^{th}$ coordinate of $A^n$ the number of directed $n$-walks from $i$ to $j$?

If $A$ is an adjacency matrix of a labeled multi-digraph is the $(i,j)^{th}$ coordinate of $A^n$ the number of directed walks from $i$ to $j$? I know this is true when $A$ is the adjacency matrix of a ...
0
votes
0answers
28 views

Digraph with incidence matrix M such that Mx=0

Q: Show that the solution space of $Mx=0$ is isomorphic to the flow space of $G$. The background info: a directed graph with incidence matrix $M$. In a previous lecture, a professor has demonstrated ...
1
vote
1answer
49 views

Minimum possible number of friendships

Here is the problem: There are 2000 people on a social network. Each person sends 1000 friend requests. Two people are friends if they've sent a friend request to each other. What is the minimum ...