Questions tagged [connected]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
0answers
66 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 ...
1
vote
0answers
19 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, ...
1
vote
1answer
54 views

Is every graph with minimum degree $n/2$ connected?

Claim: Let $G$ be a graph on $n$ nodes, where $n$ is an even number. If every node of $G$ has degree at least $n/2$, then $G$ is connected. Decide whether the above claim is true or false, and ...
3
votes
1answer
548 views

Tarjan's SCC : example showing necessity of lowlink definition and calculation rule?

Several questions (1, 2) have been asked about this topic already but I am trying to be more specific. In Tarjan's SCC algorithm, the calculation of lowlink when encountering a vertex which is ...
2
votes
1answer
214 views

number of connected subgraphs of $G$ with at most $ k>0$ vertices

Suppose we have an undirected graph $G=(V,E)$ with $n$ vertices and with max degree of $d>0$. I need to prove that number of connected subgraphs of $G$ with at most $n\geq k>0$ vertices is $M\...
1
vote
3answers
1k views

Connected components of the graph on $[n]$ in which $i,j$ are connected if $\mathrm{gcd}(i,j) > g$

I recently got asked the following question: A set of $n$ cities are numbered from 1 to $n$. Given a positive integer $g$, two cities are connected if their greatest common divisor is greater than $...
1
vote
0answers
122 views

Counting the number of connected components in a dynamic plane graph

I'm working on the following problem: let $G = (V, E)$ be a connected, planar graph. Our goal is to find a $d$-partition of $G$, $P = \{V_1, \ldots, V_d\}$, such that $G[V_i]$ is connected, and $\min_{...
2
votes
1answer
610 views

Strongly connected and completely specified Moore equivalent of a Mealy Machine

Problem: Prove that if a Mealy machine is strongly connected and completely specified, the corresponding Moore machine will also be strongly connected and completely specified. My approach so far: ...
1
vote
1answer
36 views

Connected Components - Linear Decision Trees

What does connected components mean in the context of non-graphs? Graphs have vertices and the vertices are connected by edges. Hence, you can build a spanning tree (for example) by systematically ...
4
votes
1answer
2k views

Algorithm to determine which vertices/edges would disconnect undirected graph if removed

Is anyone aware of an algorithm to determine which vertices/edges would disconnect an undirected graph if removed? For all vertices/edges. Of course I could run a BFS for each vertex and for each ...
2
votes
1answer
340 views

Algorithm for finding connected components checking as few edges as possible

Is there a good algorithm to find connected components in undirected graphs with at the lowest possible costs given as the total weight of the edges being checked?
1
vote
1answer
47 views

Is it possible to turn an eulerian NFA into a linear size DFA?

In general, there exists NFAs of size n whose smallest equivalent DFA requires 2^n states. But if we restrict ourselves to NFAs whose graph is eulerian, is it possible to turn any such NFA of size n ...
4
votes
1answer
86 views

Maximum set of equalities, subject to some inequalities

I have $n$ variables $x_1,\dots,x_n$. I'm given a set $E$ of equalities (each of the form $x_i=x_j$ for some $i,j$) and a set $I$ of inequalities (each of the form $x_i \ne x_j$ for some $i,j$). I ...
1
vote
1answer
376 views

Check if given vertices form a connected subtree in a graph

The approach described in this question is wrong. It'll find false positives for disconnected components with multiple vertices. See D.W.'s answer for a reliable alternative. This might be a simple ...