Questions tagged [connected-components]
The connected-components tag has no usage guidance.
45
questions
1
vote
1
answer
39
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.♦
- 154k
0
votes
1
answer
28
views
How reversing the edges of the graph not altering the original conditions?
I was going through the main idea of solution to this problem. I could not assimilate the idea of reversing the edges and then using that graph to check if node 1 is reachable from all others.
How ...
- 13
1
vote
1
answer
62
views
Infinite Graph with Finite Degree
Let $G$ be an undirected graph with an infinite number of vertices (and edges), and assume it is connected in the sense every $u,v$ have at least one path connecting them. Assume each vertex has a ...
- 494
0
votes
1
answer
28
views
Find connected components in a graph of computer network with parallel pairwise tests
I have N nodes, a node might have an undirected edge to other nodes, resulting in K connected components (K<=N, K unknown).
I can test if a given pair is connected. In each step in time, I can run ...
- 101
1
vote
0
answers
93
views
Reverse one edge to make the most expansive strongly connected component
Problem statement
We're given a directed simple acyclic graph with weighted vertices. Find an edge $e$ such that reversing it would create a strongly connected component (SCC) whose price is maximal. ...
- 129
2
votes
1
answer
364
views
Deciding if a graph is "Single Connected"
The definition of "Single Connected" is that for every $u,v \in V$ there is at most a single simple path from $u$ to $v$, and at most a single simple path from $v$ to $u$.
The objective is ...
- 315
1
vote
2
answers
114
views
A graph is strongly connected iff every non-trivial cut contains an edge
As the title states, I am asked to prove that a directed graph $G=(V,E)$ is strongly connected iff for all non-empty subsets $\emptyset \neq S \subset V$, the cut
$\delta(S) \neq\emptyset$, where
$$\...
- 315
1
vote
1
answer
116
views
(Directed) Graphs: Minimal Vertices Subset With No Outgoing Edges
I've been trying to study some graph algorithms and, as part of it, prove a bunch of graph theorems in order to practice my ability to do theoretical work with graphs.
Specifically, I've been trying ...
- 113
3
votes
1
answer
102
views
Efficiently determine which nodes should leave a graph while maintaining connectedness
Suppose I have a graph with node weights, where a weight is either -1 or a positive integer. For example:
If a node has weight -1, it is "happy", and cannot be kicked out of the graph.
If a ...
- 133
2
votes
1
answer
74
views
Make maze connected by removing internal walls
Recently I've stumbled upon a strange graph problem. Here is a brief description.
Given $n\times m$ matrix with $2n + 1$ rows such that each row contains $2m + 1$ characters "+", "-&...
- 123
0
votes
0
answers
28
views
Graph with constant edge connectivity that remains connected after edge removals
I have an undirected graph $(V, E)$ with constast edge connectivity $\lambda$. Each edge is sampled independently with probability $min\{1,\frac{c \ln n}{\lambda}\}$ for some $c > 0$. I need to ...
- 159
0
votes
2
answers
488
views
Algorithm for Getting Largest Connected Component From List of Touching Pairs
I have a program which finds the touching pairs of a given value in a binary image. For example, consider the below image:
...
1
vote
0
answers
43
views
Finding highly-connected regions of graphs
I have a large network of 10,000 nodes and I am trying to identify subgraphs which are clique-like, in that they share many connections. I don't a priori know how many subgraphs fit this criteria.
To ...
- 11
0
votes
0
answers
51
views
I do not understand a way of proving the correctness of the algorithm to compute the Strongly Connected Components
"Introduction to algorithms" also known as CLRS, proves the correctness of the algorithm to compute the Strongly Connected Components in two ways, one of which is
Here is another way to ...
- 212
2
votes
0
answers
77
views
How to mathematically prove that a topological ordering on a cyclic graph will topologically sort its Strongly Connected Components?
Let's have a standard topological ordering algorithm (from CLRS):
...
- 212
0
votes
1
answer
342
views
What is the relation between Topological Sort and Strongly Connected Components?
Both the Topological Sorting algorithm and the algorithm to find Strongly Connected Components build a stack whose top is the last visited vertex.
I find difficult to find an explaination because ...
- 212
2
votes
1
answer
218
views
Minimum vertices to remove from a graph so that no path exists between two given vertices anymore
Given an undirected graph $G=\{V, E\}$ with its vertices numbered from $1$ to $V$, given two vertices $s$ and $t$ $(1 \leq s \lt t \leq V)$, what is the minimum number of vertices (except $s$ and/or $...
0
votes
3
answers
558
views
O(m) time algorithm to check for a strongly connected graph
Given a directed graph G=(V,E) how can I check to see if it is strongly connected i.e.
every vertex is reachable from every other vertex.
what's a good algorithm to check for this that runs in O(m) ...
user141218
3
votes
2
answers
698
views
Efficiently check if removing an edge splits a strongly connected component
I have a strongly connected component (SCC) of $n$ vertices. Let $n_1n_2$ be an edge between two vertices $n_1$ and $n_2$ in this SCC. Is there an efficient algorithm to check if removing the edge $...
- 123
1
vote
1
answer
29
views
Enumerate all connected components that could be created from removing k edges?
I have a simple connected undirected graph $G=(V, E)$ and I would like to enumerate all possible connected components that arise from removing $k$ edges in $E$. A naive way is to remove each $k$-tuple ...
- 211
1
vote
1
answer
203
views
Minimal cut of a directed graph such that disjoint elements are strongly connected
Given an arbitrary directed graph $G$ (which may not necessarily be connected) find a minimum set of edges $S\subseteq E$ such that every disjoint component of $G(V,E\cap S')$ is strongly connected.
A ...
- 13
2
votes
1
answer
138
views
find the strong component containing the vertex v
I'm trying to solve this question for practising purposes:
"Describe a linear-time algorithm for computing the strong component containing a given vertex v. On the basis of that algorithm, ...
- 55
3
votes
1
answer
510
views
Fast algorithm for finding the size of each connected component in a graph of 2D points
I've been thinking about this for a while now. Given a graph $G$ of 2-dimensional points (we draw the edges based on a "threshold" distance), find $s_1, s_2, \dots, s_k$, the sizes of all ...
- 133
1
vote
1
answer
405
views
Longest path in a strongly connected component
So if we assume that we have some strongly connected component G with n vertices. I would like to find the length of the longest path in that component.
My idea is: In a strongly connected component ...
- 27
4
votes
1
answer
2k
views
The number of connected components in the context of cyclomatic complexity
Cyclomatic Complexity is defined with reference to the control flow graph of the program through this formula (borrowed from Wikipedia):
...
- 217
1
vote
0
answers
52
views
Graph dynamic connectivity
Let $G=(V,E)$ be an undirected graph. I would like to maintain information about the connected components of this graph(I want to be able to tell in what component particular node is lying). The graph ...
0
votes
0
answers
139
views
Why we take decreasing order of finishing times and NOT increasing order of discovery times in kosaraju algorithm?
We take decreasing order of finishing times in $G^t$ (transpose of Graph G) to know whther the path exists in other direction as shown below. But why can'nt WE take increasing order of discovery time ...
0
votes
1
answer
59
views
How can I examine the subnetworks of a nearly fully connected graph?
I have an almost fully connected graph in python with roughly 3k nodes and 9M edges. Each node in this graph is represented by a point in R3 and each edge represents the distance between them with a ...
3
votes
0
answers
40
views
Components of subset partial order
Given a collection C of sets, there are a number of proposed algorithms for building the subset partial order, e.g. this paper.
But is there any work on algorithms ...
- 177
2
votes
0
answers
66
views
But How do it Remembers?*
It is a joke with the title of a book I am reading: "But how do it Know? - The Basic Principles of Computers to Anyone".
The author is explaining a basic unit of memory with NAND gates:
I ...
- 21
0
votes
1
answer
260
views
Finding the connected subgraph of a given size with maximum number of edges, that includes a given vertex
Consider an undirected graph $G = [V,E]$. Let $V$ be the set of vertices: $V = \{v_1,..,v_n\}$ and $E$ be the set of edges. Let $C$ be the connected component that contains vertex $v_1$. I want to ...
- 87
0
votes
2
answers
84
views
Finding connected components without building the graph first
What are good algorithms for finding connected components in a graph defined by a set of elements X, where each x in ...
- 177
0
votes
2
answers
30
views
Doubt regarding strong component in a graph
I know that strong component in a graph means between any 2 vertices there should be bi-directional path.
My doubt is cycle is always a strong component. can there be any other subgraph with some ...
1
vote
1
answer
144
views
On the complexity analysis of quick-union in Algorithms by Sedgewick and Wayne
I am currently studying Algorithms, Fourth Edition by Sedgewick et al. On page 226, there is an analysis of the quick-union algorithm's find() method's worst case.
This is the algorithm:
...
- 149
1
vote
0
answers
51
views
Remove vertices to get k-connected components
In a graph, I need to remove some vertices in order to get at least k-connected components. The no. of removed vertices should be low. Is there a heuristic that I could follow for this?
- 11
3
votes
1
answer
81
views
Equivalence of states between two "quasi-deterministic" strongly connected Büchi automata accepting the same $\omega$-language
Hope someone can point me to the right direction to solve this problem.
Premise.
I call quasi-deterministic Büchi automaton (qDBA) a Büchi automaton $B = \langle S, \Sigma, S_0, \delta, F \rangle$, ...
- 33
7
votes
0
answers
233
views
When would Kosaraju's algorithm be a better choice than Tarjan's for strongly connected components?
I know both have runtime complexity $\mathcal{O} (V+E)$, but Tarjan's algorithm does a single DFS pass, whereas Kosaraju's does two DFS passes. Both need extra space (e.g. a dynamic set, often a stack,...
2
votes
1
answer
156
views
Bridges and Edge Disjoint Paths
So , Basically assume there is a graph $G$ which has no bridges. Is it always true that there exists two edge disjoint paths between any two vertices in the Graph ?
$\text{My Attempt at the Proof}$:-
...
3
votes
2
answers
208
views
Articulation points (or cut vertices), but only subset of vertices need to be connected
I know we can find all articulation points efficiently in a graph using DFS.
But what if not all nodes need to be connected, but instead we have set of node pairs that need to communicate (there is ...
- 31
4
votes
1
answer
210
views
Computing a pre-topological sort using a BFS/a queue
Computing a topological sort in a DAG using a queue simply amounts to putting the nodes with indegree 0 in a queue, and going through the queue removing these nodes from the graph and adding the nodes ...
- 141
3
votes
1
answer
1k
views
Add edges to undirected graph to make connected and minimize longest path
I am trying to find an efficient algorithm to solve to following problem: Given an undirected disconnected graph, I want to add as few as possible edges to make to graph connected while minimizing the ...
- 33
2
votes
2
answers
391
views
Implementing Tarjan's strongly connected components algorithm in a language without exceptions or undefined behavior
I asked this question on Stack Overflow, but I have not obtained an actual answer to the question.
Tarjan's strongly connected components algorithm is stunningly beautiful, and inexpressible in a ...
- 405
3
votes
0
answers
33
views
Maintaining SCCs in directed graphs (on-line, under edge deletion) with ES-trees
I'm interested in efficiently maintaining the set of strongly connected components (SCC) in a directed (unweighted) graph under edge deletions only. While searching for ways I came across an article [...
- 31
2
votes
1
answer
287
views
Is a simple graph connected, if every node has at least one adjacent edge and $|E|\ge |V|-1$?
Let $G=(V,E)$ be an undirected graph without self-loops or parallel edges.
Is the following statement true?
If $|V|=n, |E|\ge n-1$ and every node has at least one adjacent edge, then $G$ is connected....
- 659
2
votes
1
answer
2k
views
How to generate random adjacency matrix with given number of components in graph
I am building a graph package in C and a part of the work involves generating a random graph with a given number of components in the graph.
For example, if I wanted to generate a graph of 50 ...
