Questions about graphs in which every edge is associated with a weight.
-2
votes
0answers
51 views
Convert undirected graph to a directed graph [duplicate]
is it possible to convert G to a directed graph by assigning directions to each
of its edges so that every node in C has indegree 0 or outdegree 0, and every other
node in G has indegree at least 1?
...
3
votes
2answers
384 views
Modifying Dijkstra's algorithm for edge weights drawn from range $[1,…,K]$
Suppose I have a directed graph with edge weights drawn from range $[1,\dots, K]$ where $K$ is constant. If I'm trying to find the shortest path using Dijkstra's algorithm, how can I modify the ...
5
votes
1answer
207 views
Minimum s-t cut in weighted directed acyclic graphs with possibly negative weights
I ran into the following problem:
Given a directed acyclic graph with real-valued edge weights, and two vertices s and t, compute the minimum s-t cut.
For general graphs this is NP-hard, since one ...
5
votes
2answers
93 views
An edge that connects more than two nodes in a graph?
Is there a way to create a single edge on a graph that connects 3 or more nodes? For example, let's say that the probability of Y occurring after X is 0.1, and the probability of Z occurring after Y ...
6
votes
1answer
541 views
Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?
If a weighted graph $G$ has two different minimum spanning trees $T_1 = (V_1, E_1)$ and $T_2 = (V_2, E_2)$, then is it true that for any edge $e$ in $E_1$, the number of edges in $E_1$ with the same ...
