MHB How to determine whether a graph is connected or not?

  • Thread starter Thread starter yakin
  • Start date Start date
  • Tags Tags
    Graph
Click For Summary
To determine if a graph is connected, one can use standard search algorithms like Breadth-First Search (BFS) or Depth-First Search (DFS). Start the search from any node and track the visited nodes throughout the process. After the search completes, check for any unvisited nodes; if any exist, the graph is not connected. If all nodes are visited, the graph is confirmed to be connected. This method provides a practical approach to assessing graph connectivity.
yakin
Messages
42
Reaction score
0
How to determine whether a graph is connected or not?
 
Physics news on Phys.org
If you mean an algorithm, you can just use a standard search (BFS, DFS) starting from any point in the graph, keeping track of visited nodes. Once your search ends, check if there are any nodes that were not visited - if so, the graph is not connected, otherwise it is connected (can you prove this rigorously?).
 

Thread 'Hypothesis testing: Defining H0, HA hypotheses so that ( H_A)_A' makes sense'

The standard _A " operator" maps a Null Hypothesis Ho into a decision set { Do not reject:=1 and reject :=0}. In this sense ( HA)_A , makes no sense. Since H0, HA aren't exhaustive, can we find an alternative operator, _A' , so that ( H_A)_A' makes sense? Isn't Pearson Neyman related to this? Hope I'm making sense. Edit: I was motivated by a superficial similarity of the idea with double transposition of matrices M, with ## (M^{T})^{T}=M##, and just wanted to see if it made sense to talk...
View full post »

Similar threads

MHB Graph: showing that diameter is greater than average pairwise distance
  • · Replies 4 ·
Replies
4
Views
3K
Undergrad Number of edges in a tree digraph
  • · Replies 5 ·
Replies
5
Views
2K
MHB Are Events in Random Graphs from G(n, 1/2) Independent?
  • · Replies 1 ·
Replies
1
Views
2K
MHB How many edges does the graph have?
  • · Replies 4 ·
Replies
4
Views
2K
MHB Graph Grammer Function For Two Exotic Graphs Question please.
  • · Replies 4 ·
Replies
4
Views
2K
MHB Determine the diameter of the graph
  • · Replies 10 ·
Replies
10
Views
2K
MHB Bipartite Graphs: Does $\alpha(G) =|U|$?
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Proof involving functional graphs and the injective property
  • · Replies 3 ·
Replies
3
Views
1K
MHB Minimum Degree of a Random Graph (Probabilistic Method)
  • · Replies 1 ·
Replies
1
Views
2K
MHB Understanding Two Graph Theory Problems
  • · Replies 2 ·
Replies
2
Views
2K