Questions tagged [connected]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
1answer
23 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 ...
0
votes
1answer
55 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 ...
1
vote
1answer
40 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?
2
votes
0answers
213 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
27 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
73 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 ...
4
votes
1answer
680 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
277 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\...
2
votes
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
130 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
646 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
3k 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
350 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
48 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
91 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
414 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 ...