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 'Two interesting number theory tricks'

First trick I learned this one a long time ago and have used it to entertain and amuse young kids. Ask your friend to write down a three-digit number without showing it to you. Then ask him or her to rearrange the digits to form a new three-digit number. After that, write whichever is the larger number above the other number, and then subtract the smaller from the larger, making sure that you don't see any of the numbers. Then ask the young "victim" to tell you any two of the digits of the...
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