# Appropriate Graph Theory Concepts

I am working in a different domain and I have very basic information about the graph theory concepts. Trying to map my problem into graph theory and looking for the concepts and algorithms applicable to my problem.

Part 1- Essentially, I am looking for graph discovery/exploration algorithm that should find out the entire graph, given a starting vertex and its edges to all its immediate neighbors. Assuming that the edges are non-directional and of same weight.

Part 2- Once the graph is found, we need to find out if there is any cycles in the graph. Not sure if this is even possible.

Part 3- Here it gets tricky for me to explain. The real world application is such that any node(vertex) will only have one parent and possibly 0-n children. I need to find out a node in the graph that is sort of in the center of the graph, i.e. the distance to reach from that node to any node that has 0 children, should be minimum. To my understanding the graph is similar to minimum spanning tree, as all the vertices are included and there is no cycle in the graph, what I am not sure is how find the root that is at the minimum distance to the leaf nodes.

I am looking for algorithms, pointers to algorithms, similar concepts applicable to this scenario.

• en.wikipedia.org/wiki/Cycle_(graph_theory)#Cycle_detection – mvw Jul 16 '15 at 8:18
• en.wikipedia.org/wiki/Graph_center – Gerry Myerson Jul 16 '15 at 8:56
• Could you give some context on what your domain is and what kind of application needs this particular approach? Each of the parts you describe are standard graph-theoretical concepts and I'm very curious what uses they have in their pristine form (students are always eager to know such things). – dtldarek Jul 16 '15 at 9:46
• I am working in power grid systems, which has many nodes and the connections between them are like edges in the graph. The nodes in the grid becomes online and offline and therefore a graph discovery is needed. Similarly, the distance from the supply to the outer nodes plays a significant role. – Novice Jul 17 '15 at 4:40