Questions tagged [connected]
The connected tag has no summary.
27 questions
2 votes
0 answers
57 views
Testing hidden connectivity of vertex pairs in graph
I have a problem from graph theory for which I could need some theoretical background and, if possible, ideas for an algorithm. Suppose we have a "usual" graph $G =(V,E)$ with finitely many ...
- 181
1 vote
1 answer
398 views
Minimum edges removed to turn a strongly connected graph into an acyclic graph
If I start with a directed graph that is strongly connected, is there a straightforward way / algorithm to find the smallest set of edges to remove, such that the result is a directed but acyclic ...
2 votes
1 answer
371 views
Boolean constraints for a connected component of a graph
Suppose I have an undirected graph $G=(V,E)$, and boolean variables $x_v$ (one for each vertex $v \in V$). These variables select a subset $S \subseteq V$ of vertices, namely the vertices $S=\{v \mid ...
D.W.♦
- 169k
1 vote
3 answers
375 views
Algorithm to find Minimal Spanning Subgraph
I'm attempting to solve this problem: Given an undirected connected graph $G=(V,E)$ with $\mathrm{weight}(e)>0$ for all $e \in E$, and a subset $S \subseteq V$, we define that a sub-graph $H=(V',E')...
- 377
0 votes
0 answers
222 views
In a connected graph, determine all nodes reachable with a "edge-simple" path from node A to node B
I'm asked to write an algorithm which determine all points which appear in a "edge-simple" path connecting node A and node B, i-e a path which doesn't go 2 times in the same edge, but it can ...
- 1
1 vote
1 answer
238 views
SAT formula for connected graphs on the grid
In the answer to an earlier question "SAT algorithm for determining if a graph is disjoint" a formula is constructed that is satisfiable iff a given graph is connected. The formula uses a ...
- 31.6k
2 votes
1 answer
119 views
Select fixed-size connected induced subgraphs in a graph
I have a connected graph with $nk$ vertices, and would like to select $n$ disjoint induced subgraphs with $k$ vertices such that each subgraph is connected, selecting one out of all possible solutions ...
- 281
0 votes
1 answer
147 views
Decidability of directed strongly connected graphs
Consider the problem of determining if a directed graph is strongly connected. How to phrase it as a language and prove that it's decidable. My Thoughts : To think of decidability given a graph I ...
- 59
5 votes
3 answers
2k views
How to prove that the dual of the dual of a connected planar graph $G$ is isomorphic to $G$?
I find in many references the fact that if $G$ is a connected planar graph, then for any embedding, $G^{**} \cong G$. However, all those references either say that this fact is trivial, or give the ...
- 18.5k
3 votes
1 answer
3k views
Determine whether removing a node on a graph will disconnect the graph [duplicate]
I have an undirected unweighted graph with a single component. I want to know if removing a given node will disconnect the graph. I know that I can remove the edges to the node and then use DFS to get ...
user121627
2 votes
1 answer
51 views
Stretegy to find the min expected cost on a series graph with edge probability pi and search cost ci
In a series graph, each edge $e_i$ exists with probability $p_i$. And if you want to examine the existence of edge $e_i$, it will cost you $c_i$. I want to test the connectivity between source $s$ and ...
- 21
0 votes
1 answer
2k views
Efficiently remove nodes from a connected graph
Suppose you have a connected graph and want to remove k nodes such that the result is still connected. How could you do this efficiently? It occurs to me that you ...
- 387
2 votes
1 answer
318 views
if a graph G(V,E) is connected $|E|\geq|V|-1$
If a graph G(V,E) is connected the number of edges is at least the number of Vertices-1. It is pretty evident if you think about it but how do i prove it formally?
- 99
2 votes
0 answers
266 views
Given undirected and connected graph G=(V,E). Prove for any DFS run: for any u,v∈V if u.d>v.d then u.d−v.d≥δ(u,v)
Given undirected and connected graph $G = (V,E)$. Prove for any DFS run: for any $u,v \in V$ if $u.d>v.d$ then $u.d − v.d ≥ δ(u,v)$ $δ(u,v)$-distance of a shortest path (not necessarily unique) in ...
- 21
1 vote
0 answers
330 views
Decremental connectivity on general graphs
I'm looking for an efficient solution to the problem of tracking the number of connected components in a general graph under edge deletions. General connectivity algorithms like that from Holm, ...
- 11