# Questions tagged [connected]

The tag has no usage guidance.

18 questions
Filter by
Sorted by
Tagged with
99 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 ...
25 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 ...
121 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 ...
43 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?
218 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 ...
37 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, ...
88 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 give a ...
770 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 ...
352 views

662 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: ...
38 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 ...
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 ...
356 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?
49 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 ...
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 ...