Stack Exchange Network

Stack Exchange network consists of 174 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 [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 ...