Questions tagged [graphs]
Questions about graphs, discrete structures of nodes which are connected by edges. Popular flavors are trees and networks with edge capacity.
2
votes
1answer
23 views
Mean geodesic distance between two points in Delaunay Graph
If I have a Delaunay Graph, what is the mean geodesic distance between two randomly chosen nodes.
I know that in a small world network, it is in O(log(N)), with N being the number of nodes.
Thank you!...
0
votes
0answers
56 views
Convert undirected graph to directed graph with specific condition
undirected graph is given which has M edges and N vertices we have to convert every edge from u-v to u->v or v->u such that indegree of every vertex is even.Which method or algorithm is suited for ...
3
votes
3answers
86 views
Undirected graph with exponential number of simple cycles
Hey I am new to graph theory and this question has me stuck for hours.
What is an example of undirected graph with n nodes where the number of simple cycles is exponential in n.
I was looking at ...
1
vote
1answer
29 views
Graph theory: determining maximum number of edges
Based on the question below, can someone please explain to me the reasoning behind why the maximum number of edge is 5/2|V|? I don't find the particular reasoning in the solution to be that helpful ...
0
votes
0answers
16 views
Finding shortest cycle in graph with positive weights
Given a graph G, with all positive weights, find the shortest cycle length in O(V^3)
My idea is, negate al the edges, apply floyd-warshall algorithm and then for all $i$, find the largest $M[i][i]$ ...
3
votes
1answer
38 views
Strongly connected orientations of undirected graphs
I'm trying to prove the following.
There exists a strongly connected orientation of a connected, undirected graph $G$ if, and only if, $G$ has no bridge.
(An orientation of an undirected ...
0
votes
2answers
36 views
Shortest distance from multiple points to one point
I am looking for an algorithm to find the shortest distance from multiple nodes to one end node. For example let $v_1,v_2,\dots,v_r$ be the nodes on a graph with distance $d_1,d_2,\dots,d_r$ to the ...
0
votes
0answers
19 views
Aproximation of longest path in undirected graph from given point
I'm looking for a algorithm suitable to find possibly the longest path (by count of nodes) in given undirected graph and starting node in some time resime. Is there any know algorithm for that?
1
vote
1answer
30 views
What happens if I replace $<$ with $\le$ in Dijkstra's algorithm?
The following is Dijkstra's algorithm for finding the shortest path in a graph. I know something wrong happens if I replace d[u] + weight(u,v) < d[v] with ...
0
votes
0answers
44 views
Intuition behind Floyd-Warshall being faster
I know the Floyd-Warshall, and I also clearly understand the proof of running time of $O(V^3)$ of F-W algorithm. However, consider this algorithm:
Let $dp[i][j][n]$ denote the shortest path from $...
3
votes
2answers
54 views
Calculate the number of cycles of a Cactus graph?
Considering a cactus graph $G = (V, E)$, defined as:
A graph is a cactus if every edge is part of at most one cycle.
There is a way to calculate the number of cycles in this graph given only $n= |...
1
vote
1answer
17 views
Tracing a polynomial algorithm for the problem of maximum-weight independent set
It should be a very easy question, but I am a little bit confused.
According to party optimization post, the Maximum-weight Independent Set for trees can be found in the poly-nominal time using ...
-1
votes
0answers
16 views
Pseudocode of calculating an Euler tour
In the context of Christofides' algorithm, not that I think it matters. How do you calculate an Euler tour?
context: https://en.wikipedia.org/wiki/Christofides_algorithm#example
This is what I think ...
0
votes
2answers
35 views
Finding shortest path between two nodes with a set of forbidden nodes
I have undirected and unweighted graph, in which I would like to find the shortest path between two entered nodes. There is also a set of forbidden nodes. How to find the shortest path, if I am ...
21
votes
5answers
3k views
Do any two spanning trees of a simple graph always have some common edges?
I tried few cases and found any two spanning tree of a simple graph has some common edges. I mean I couldn't find any counter example so far. But I couldn't prove or disprove this either. How to ...
0
votes
1answer
34 views
Proving that a spanning tree of graph is not a minimum
Let $G$ be an undirected and connected graph. Let $T$ be a spanning tree of $G$ with edges weights: $w_1 \le, w_2 \le ... \le w_{n-1}$ which are responing to the edges. $e_1,e_2,...,e_{n-1}$.
Now I ...
0
votes
1answer
29 views
More efficient maximum bipartite matching
I've been looking into weighted matching in bipartite graphs and am currently looking at maximum matchings in weighted bipartite graphs. As I've been reading and poking around at different books and ...
1
vote
2answers
24 views
Minimum number of components in graph
Minimum number of components in graph where we have 69 vertices and 43 edges. I think the best way is to create a path? One path and the rest would be isolated components. Since in path we use only ...
0
votes
0answers
12 views
Number of automorphisms 4 cyclic graphs with one vertex in common has?
Number of automorphisms 4 cyclic graphs with one vertex in common has? I know that cyclic graphs Cn, n is number of vertex, have 2*n automorphisms. So I think the solution is 2(n-1). Correct?
2
votes
1answer
88 views
Does a Vertex Cover exist?
This should be a simple question, but I am a little bit confused.
A proof on page 556 of Algorithm Design says:
"Let $e=(u, v)$ be any edge of $G$. The graph $G$ has a vertex cover of size at most $...
0
votes
0answers
8 views
How do I extend bellman-ford, to limit the number of edge-traversals (k), that are permitted?
How do I extend this bellman-ford, so I can limit the number of edge-traversals (k), that are permitted?
And no, it's not just a matter of limiting the outer loop to run k times, since BF updates ...
3
votes
2answers
78 views
Are edges in a minimum spanning tree not heavier than respective edges in another spanning tree?
Let $G$ be an undirected connected weighted graph, and let $T$ be a minimum spanning tree of $G$ with edge weights: $w_1 \le w_2 \le ... \le w_{n-1}$.
Now let $T'$ be some other spanning tree of $G$ (...
2
votes
1answer
41 views
Are you allowed to change the specifications of a problem when doing reductions?
I'm doing a polynomial time reduction from problem A (known graph problem) to problem B (funky and specific longest path problem). There is a lot of demands on how problem B is supposed to be solved. ...
1
vote
1answer
29 views
Greedy algorithm to find Minimum Dominating Set in a tree
Is it possible to find minimum dominating set on a tree $G$ using a greedy algorithm?
0
votes
0answers
26 views
How to modify Bellman-ford to account for a max-number of edge-traversals allowed
How can i modify Bellman-ford to account for this restriction?:
only allowed a certain number of edge-traversals (k) to go from source-node to target-node?
The algorithm runs on graphs with:
0, 1 ...
1
vote
1answer
20 views
Color a graph using k colors, k>4, with the most equal distribution of colors
Given a planar graph G with $N$ nodes, 4 colors are enough to color each node, so that adjacent nodes have different colors.
Let $k > 4$. Is there an algorithm to color the nodes with $k$ colors, ...
-4
votes
0answers
39 views
ACM Swiss Subregional Contest Graph Problem [closed]
I am not sure how to find a solution to this problem that runs within the time limit.
Edit: what I’m asking for is a solution whose complexity is on the order of V+E (judging from the time limit) ...
0
votes
0answers
15 views
a distributed graph clustering
I have a connected undirected graph. I looking for clustering algorithms, preferabaly distributed, for partitioning the nodes of these graphs. I need algorithms that cluster each given graph in a way ...
1
vote
3answers
27 views
Intuitive proof for a tree with n nodes, has n-1 edges
I am interested in an intuitive proof for "any binary tree with $n$ nodes has $n-1$ edges", that goes beyond proof by strong induction.
0
votes
0answers
23 views
Help with understanding Kleitman–Wang algorithm
I have a problem in which I need to solve the realization for a directed graph when I am given the in and out degrees for n number of vertices. A hint was to use network flows. I know that the ...
0
votes
1answer
17 views
Minimum perfect matching with uneven vertices?
Given this graph, what is the minimum perfect matching? What do you do, when there is an uneven number of vertices?
1
vote
1answer
98 views
Need help to come up with definitive proofs with regard to Planar Graphs
I was working through a few problem sets and came across this question
Suppose there is a connected planar simple graph $G$ with $v$ vertices such that all its regions are triangles (a cycle ...
1
vote
0answers
13 views
Matrix represents weighted graph
In a question I've been given a 5x5 matrix that I'm told represents a weighted graph, and no other information. Here is an example:
0 4 5 2 2
3 0 3 3 1
1 3 0 5 2
2 4 4 0 2
2 3 2 5 0
My question is, ...
2
votes
1answer
115 views
Directed HAM Cycles with Additional Constraints to SAT
The $n$ dimensional hypercube $Q_n$ is a graph that has a vertex $v_s$ for each string $s \in \{0, 1\}^n$ and an edge between two vertices $v_s$ and $v_t$ if and only if the Hamming distance between $...
2
votes
1answer
34 views
Alternate proof of the Caro-Wei theorem for lower bounding the independence number
Let $G$ be a graph on $n$ vertices whose degree sequence is $d_1,d_2,...,d_n$. Let $\alpha(G)$ denote the size of maximum independent set of $G$, i.e., the size of a maximum subset of vertices of $G$ ...
2
votes
1answer
96 views
Christofides algorithm (by hand) (suboptimal solution - is it my fault?)
I would like to calculate an eularian path using Christofides algorithm on this graph: (Focus on the first number in each box representing the distance)
$\alpha$ denotes the start and end vertex of ...
0
votes
1answer
57 views
Karp hardness of minimum number of arc reversals needed to turn a graph into an Eulerian one
What is the complexity of this problem
EULERIAN ARC REVERSAL
Input: a directed graph $G(V,A)$ and an integer $k$
Output: YES if $k$ arc reversals are enough to transform $G$ into an ...
1
vote
0answers
47 views
Graph with two classes of nodes A and B: densest subgraph with same node classes cardinality
I'm searching (without results) a problem that can be reduced to finding the densest subgraph with the same cardinality between two classes of nodes.
Consider a graph with nodes of class A and nodes ...
3
votes
1answer
49 views
Algorithm for minimizing the number of “inversions” in a graph
Given the following graph:
With the assumptions below:
A node on the left is linked to several nodes on the right
Nodes on the right are paired together: one is black, one is white
Each pair of ...
4
votes
1answer
19 views
In ISGCI, unit interval graphs are denoted as ($C_{n+4}$,$S_3$,claw,net)-free. Is this an accurate notation?
When I search unit interval graphs in ISGCI, it says that the unit interval graphs (UIG) are equivalent to ($C_{n+4}$,$S_3$,claw,net)-free graphs.
I am confused about the definition of an $S_3$ graph....
0
votes
0answers
21 views
Bellman-Ford shortest path [duplicate]
I've been trying to prove that if I'm given a directed weighted graph with no negative cycle, then there exist an order on the edges such that after the first iteration I will get the shortest paths.
...
0
votes
0answers
38 views
In a directed graph G, detect if there is a path that visits each node at least once
I'm trying to prove that Given a directed graph G,we can't detect if there is a path that visits each node at least once,
I’m trying to use the fact that: detecting if a directed graph has a Hamilton ...
1
vote
1answer
41 views
Behaviour of Dijkstra in Case of Negative Edge Weight [duplicate]
I came across a serious doubt regarding the implementation of the Dijkstra algorithm and hence wanted to discuss.
For the given below graph
What should be the Cost to reach Node G from Source Vertex ...
0
votes
1answer
36 views
Cost of the MST of the graph [on hold]
Studying for a test in a computer science class and cannot figure out the answer to this question. Any help would be appreciated!
Although the picture shows a directed graph, please treat it as ...
0
votes
1answer
61 views
Deleting edges such that largest connected component has at most $n/4$ nodes
Let $G = (V, E)$ be a connected undirected graph with $n > 4$ nodes $V = \{v_1, v_2, \dots, v_n\}$ and $m$ edges.
Let $\{e_1, e_2, \dots , e_m\}$ be all the edges of $G$ listed in some specific ...
1
vote
1answer
44 views
proving correctness of algorithm about graphs with DFS
I need to prove/disprove the correctness of the following algorithm:
Let G be a simple, undirected and connected graph. The task is to find if the graph contains an odd cycle. The algorithm goes that ...
1
vote
1answer
24 views
Matrix of a graph and computational complexity
Given a simple undirected graph with no self-loops, $G = (V,E)$, where $V = {1,2,...,n}$, an $n × n$ matrix $A$ is said to be the adjacency matrix of $G$ if $A_{i,j}$ is $1$ if $(i, j) ∈ E$ and $0$ ...
2
votes
1answer
24 views
NP-Hard on Complete Graphs
I have a problem (A) on undirected graphs that I wish to show is NP-Hard. I can show that there is a reduction from a well known NP-Hard problem (B) to A by constructing an instance of A with a ...
2
votes
1answer
31 views
minimum number of nodes that traverse all the graph
In the following graph, we can traverse entire graph if we select the nodes 0 and 2. I am looking for an efficient algorithm which returns this two nodes. Note that this is neither vertex-cover ...
1
vote
0answers
37 views
Preferring forward edges to cross edges during graph DFS traversal
It's well known that depth-first search order of a graph is (usually) not unique, and multiple orders are possible depending on the order in which successors are processed for each node. Let's ...
