# 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.

154 questions
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 ...
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 ...
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$...
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 ...
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 ...
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....
0answers
25 views

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$ ...
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 ...
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 ...
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!
1answer
48 views

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 ...
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 ...
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-...
0answers
187 views

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$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
1answer
48 views

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 ...