Mathematics Stack Exchange
Mathematics 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.

Directed graphs, or digraphs, are used to represent asymmetric relationships between a collection of objects.

Formally, a directed graph is defined as consisting of:

  • a set of vertices;
  • set of ordered pairs of vertices, called arcs or directed edges.

In diagrams, vertices are represented by points, and each directed edge is represented by an arrow from its first vertex to its second.

Some special classes of directed graphs include:

  • Tournaments: directed graphs in which, for every pair of vertices, an edge exists in exactly one direction between them.
  • Directed acyclic graphs (DAGs), which contain no directed cycles.
400 questions
2
votes
1 answer

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?
Henrique Tannús
  • 21
1
vote
1 answer

Proving Redei's Theorem

Can someone prove Redei's theorem that every tournament has a directed Hamiltonan path in simple english? The articles I found on it are very abstract and the only video on the topic is in Hindi.
6ix9ine
  • 13
1
vote
0 answers

Directed graph problems for primary age kids

My 10 year old son is being given this class of question each week for homework but I'm a bit stumped on the best strategy to solve them. A spider lies in ambush for the ant as shown below. How many different ways are there for the ant to reach…
fiat
  • 113
1
vote
1 answer

Name of a digraph such that all its vertices are carriers?

I'm looking for the name of a digraph such that all its vertices have in- and out-degree of $1$, or, what is the same, the name of a digraph such that all its vertices are carriers.
Garmekain
  • 3,124
  • 13
  • 26
1
vote
0 answers

Terminology: induced graph and other related graphs

I'm creating graph viewing utilities for real world use cases. My input is technically a directed acyclic graph with labelled edges and nodes. As part of this I find myself generated graphs related to a graph in a number of different ways…
Att Righ
  • 111
1
vote
1 answer

Shortest path in weighted digraph, constrained to include a minimum number of nodes

Say you have a weighted digraph with n nodes. And you want to find the shortest path to all n nodes from a source node. But you are constrained by the fact that the shortest path must go through a minimum number of other nodes, but can only touch…
kmskms
  • 11
0
votes
1 answer

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 of edges $E' \subset E \ $ whose removal would…
Peter Sampodiras
  • 437
0
votes
0 answers

Intersecting paths in a directed graph

I am stuck with the proof. Computer simulation cannot find a counterexample. Given a directed graph (digraph) $G = (V,E)$ and two vertices $s,t \in V$ called the source and sink, we assume that there is a simple (without self-intersections) …
Vika
  • 447
0
votes
1 answer

Does Tarjan's algorithm actually find all SCCs?

So I learned about Tarjan's algorithm the other day and I'm not quite sure if I understand it 100% correctly. I read a lot about the statement that Tarjan's algorithm is able to decompose a directed graph (digraph) into its strongly connected…
user3182899
  • 5
0
votes
0 answers

Breadth First Search for Directed Graph

Consider the following graph I was asked to list the nodes of the graph in breath-first traversal, starting from node 0. My result is as follow I'm not sure about the 2 node. What do I do with nodes that connects like this to a graph and is my…
Clint Theron
  • 47
-1
votes
1 answer

Given a directed graph with 3 nodes, where order of nodes does not matter, how many graphs are possible?

No nodes have self referencing arrows. I tried solving on paper and got 14 graphs. 2 with 2 arrows, 4 with 3 arrows, 5 with 4 arrows, and 2 with 5 arrows, and 1 with 6 arrows. With 2 arrows: 1 points to 2 points to 3. 1 points to 2 and 3. With 3…
Al G Johnston
  • 35
-2
votes
1 answer

Directed Acyclic Graph of

I have the solution to a word problem, which seems like a directed acyclic graph and I do not see how the author came up with the edges they did. The problem is if Tie can be worn after shirt. Socks after trousers and shirt. Shoes can be worn after…
Sean
  • 1