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
32 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 ...
1
vote
0answers
19 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 ...
0
votes
0answers
14 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
40 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
20 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 ...
1
vote
2answers
23 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
29 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
36 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
24 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
39 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
75 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
46 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
22 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
205 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
25 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
77 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
99 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
116 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
35 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
32 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
37 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
33 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
17 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
55 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
30 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
45 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
323 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
315 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
170 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
48 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 ...
1
vote
1answer
69 views

Connected digraph, the rank $M=V-1$

As shown above, how to prove the rank of the incidence matrix is $V-1$? First, I figure out that the incidence matrix of a digraph will have 1 or -1 (and zero also) in each column (that are edges). ...
1
vote
1answer
24 views

If an orientation of a tree graph has no source vertices, must the in-degree of each vertex in said orientation be equal to one?

Given any polytree $T$ (any orientation of a tree graph) such that $\forall v\in V(T)(\text{indeg}(v)\neq 0)$ does this imply that $\forall v\in V(T)(\text{indeg}(v)=1)$? I'm pretty sure its true, but ...
2
votes
2answers
123 views

Paths must cross in Lindström-Gessel-Viennot on the lattice

The following question (which I am going to answer myself) serves to close a little gap in some combinatorial proofs that use the Lindström--Gessel--Viennot lemma. Namely, I will show a little lemma, ...
0
votes
1answer
46 views

Prove a DAG can be obtained by an undirected graph's longest cycle

Let G(V, E) be a finite undirected graph and let κ be its longest undirected cycle. Prove that it is always possible to obtain an orientation ω(κ) in which κ is topologically sorted and hence its ...
1
vote
1answer
48 views

incidence matrix of a mixed graph

I have read about incidence matrix of a mixed graph but without example. All examples I saw were either for undirected graphs or for directed graphs but not for mixed graph. What will be the ...
1
vote
1answer
23 views

a locally confluent and terminatting rewrite system is complete

I want to prove that every locally confluent rewrite system is confluent. Since I know very little about rewrite systems and logic, I tried looking at it as a digraph with no external infinite paths ...
3
votes
1answer
54 views

Split hateful people into groups that can exist in harmony (color a graph)

There are 51 people. Each person hates exactly 3 other people (who may or may not reciprocate). We need to split them into $n$ groups so that all groups exist in harmony. What is min $n$? Edit We ...
0
votes
0answers
29 views

Information about spanning sets in a directed graph

First of all, apologies for the potentially misleading wording in the question. I am not looking for information exactly about a spanning set (spanning tree) but I do not know what else to call it. ...
0
votes
0answers
24 views

Graph algorithm to find the most likely ancestor of a node

I'm working on the Wikipedia Category Graph (WCG). In the WCG, each article is associated to multiple categories. For example, the article "Lists_of_Israeli_footballers" is linked to multiple ...
4
votes
1answer
61 views

Is this graph a tree and how do you reason it correctly?

Is this graph a tree? I'm not sure if my answer and especially my reasoning is correct? A tree is an undirected graph where two arbitrary vertices are connected by exactly one path, e.g. a graph is ...
29
votes
7answers
3k views

How do you correctly reason that this directed graph is acyclic?

How can you correctly reason that this directed graph is acyclic? I can only visually say that this graph is acyclic because there is not a single path in the graph where the starting vertex is ...
1
vote
1answer
24 views

How to compute the maximum number of flights possible

The following figure represents a graph of the possibile flights from one airport to another. Note that a flight should always originate from $0$ and terminate at $2$. Find the maximum possible number ...