splitting of a graph into cycles and then into paths

Question

First of all, I should say I am not familiar with the Graph theory and also my mathematics knowledge is very poor. Anyhow I am using graph concepts for my analysis.

Basically, I am decomposing an undirected graph (say G) into cycles (closed graph). The specialty of my cycle is that they are the shortest cycles that one can traverse between two vertices (as they are cycle, starting and ending are same though). According to my example graph, my cycles are (1,4,5,1)(1,2,3,4,1)(7,9,8,7) (I neglect the cycles whose length is less than 3).

Edit: I use depth first search to get the cycles and then got the smallest cycles.

Later, I am further braking those cycles into directed paths. In here, I broke the cycles through the edges (through red lines in figure), so that I inserted starting and ending nodes for my new path graphs. So for the cycle (7,9,8,7)=> new directed paths are (a,9,c)(d,8,7,b) Edit: the further breaking is done only for selected cycles. It is just inserting a new vector and updating the elements. Any graph theory related algorithms doesn't involve here.

Then I do some analysis with my data.

I did all above things. So, my problem is how to describe the entire things with mathematical notations (without example like I said). This is very hard for me as I do not have even basics.

I was trying and googling but still cannot find a way to describe what I did. I guess, the thing what I did is clear for you.

So, Could you please help me, How to describe

1. decomposing a undirected graph into cycles (shortest cycles)
2. Cycle breaking via edges and make directed path graphs (as shown in figure)

with mathematical notation (according to graph theory)

I have seen many authors use different notations and symbols to define graphs and their sub graphs, but for me, I can not define such things as my basic are too poor. So, Please help me to say these things in a formal, mathematical way. Thanks in advance.

I have inserted sample figures to get idea also.

Note: I have add c++ tag as many computer scientists use graph theories and would like to have a response.

Answer 1

The first problem you might encounter in an attempt to put your operations in a mathematical description is your definition of the "shortest cycles" as cycles are typically defined as a sequence of vertices connected by edges in which the first one is also the last one.

Math crashcourse

In math a graph is typcally described by two sets V (like vertices) and E (like edges) The set E consisting of sets with two elements each of them being a vertex. Such as

• V = { v1, v2, ...., vn }

• E = { ..., {vi, vk}, ... }

Every set in E correspends to one edge in your graph.

As such a (connected) path is typcially defined as:

A sequence of vertices v1, ...., vn with the property that for every two consecutive vertexes in the sequence vi and vi+1 the set { vi, vi+1 } is an element of the set E.

(practically speaking: there is an edge from vertex vi to vertex vi+i)

A cycle is typically defined as a path with the property: v1 = vn (thus the first vertex is also the last one)

Whith this definition an your example already the sequence: 1, 4, 1 forms a cycle (in the mathematical sense)

As such every edge in your graph would count as a "shortest" cycle, while the examples given are definately longer!

You told that you

... neglect the cycles whose length is less than 3

this doesn't look to bad as a starting point for your description. Unfortunately I didn't completely understand the next steps you want to perform.

Advice

My advice, or the least the way I would approach the problem is to convert the rather long description to some kind of shorter algorithmic description while refining on exactly how you try to perform the task. This way getting to your final description shouldn't be too hard to accomplish. Especially don't forget to tell what exactly the input to your algorithm is. Even that doesn't seem to be too clear from your description.

• are you starting with a already known set of "shortest" cycles?
• or are you just given a graph as input and have to determine the "shortest" cycles yourself?
• if you detect them yourself how exactly is this done? Especially don't forget to tell about this part of the story if it applies as it seems to be one of the most crucial ones to your problem.