0

Consider the following undirected graph:

    a  
   / \  
 /     \  
b-------c  
 \     /  
  \   /  
    d

From the top-voted answer to Finding all cycles in undirected graphs I recently learned that the term Simple Cycle includes all three of the cycles in this graph: abca, bcdb, and abdca. (I originally thought Simple Cycles would only include abca and bdcb.)

Yet the Euler Equation would tell me that there are E - N + 1 = 5 - 4 + 1 = 2 cycles

Clearly these 2 cycles would be abca and bcdb.

What is the correct term for just those cycles?

Community
  • 1
philologon
  • 215
  • Also, considering this answer (http://math.stackexchange.com/a/1221374/61558) and the comment under it, could there be ambiguity in this terminology? – philologon Apr 10 '17 at 23:02
  • Are you looking for the boundary cycles of the faces in the particular drawing of the graph you're looking at? Those won't be the same if you consider a different drawing of the same graph. – hmakholm left over Monica Apr 10 '17 at 23:03
  • Yes, that is what I am looking for. The only type of different drawing I can envision is one where d is moved so that edge bd crosses two other edges. Is there some other drawing (transformation) that I am not anticipating? And if so, what is the Euler Equation actually counting? – philologon Apr 10 '17 at 23:05
  • 1
    @Smylic: I think that's true for polyhedral (i.e. 3-connected) graphs, but planar graphs are a slightly larger class where the faces are not always intrinsically determined. – hmakholm left over Monica Apr 10 '17 at 23:13
  • @Smylic, yes, I noticed that I could put d inside the abca triangle. But there are still just two faces: abca and bcdb. Is this the term I am looking for? Face? – philologon Apr 10 '17 at 23:15
  • 1
    @philologon: If you put d inside the triangle, the (inner) faces are now bcdb and abdca. – hmakholm left over Monica Apr 10 '17 at 23:18
  • @HenningMakholm yes, this helps me understand it a little better. I am also seeing how this means I need to ask a new question -- my higher-level problem has to do with cuts and possibly commodity flow. We will be avoiding computing flow rates if we can -- we just need to know about whether a cut converts one graph into two. – philologon Apr 10 '17 at 23:23

1 Answers1

2

You seem to be looking for the cycles that form the boundaries of the inner faces of the graph -- in a particular planar drawing of it.

Note that this can depend on which drawing of the graph you're looking at. For example, consider this graph:

  B------C
 / \    / \
G---A  D---H
 \ /    \ /
  F------E

Here, if I understand you correctly, one of the cycles you want to consider is ABCDEF. However if instead we draw the same graph as

  B------C
 / \    / \
G---A  H---D
 \ /    \ /
  F------E

then ABCDEF suddenly doesn't border a face (not even the outer one).

The number of faces is still the same (due to the Euler formula), but they're different ones.

hmakholm left over Monica
  • 286,031
  • Is there a concept of faces with the shortest edge distance (by edge count)? In such a case as this, that would still identify abca and bcdb, omitting abdca as I was naively thinking it ought to be anyway – philologon Apr 10 '17 at 23:29
  • 1
    @philologon: Not really -- for this particular example, ABCDEF and ABCHEF have the same length, but both cannot be faces at the same time. – hmakholm left over Monica Apr 10 '17 at 23:30
  • In my application (I think) it will not matter which Cycle wins the race to be counted as a face, but I will be favoring shorter circuits. – philologon Apr 10 '17 at 23:39