Edge Elimination Number

Question

From Erich Friedman's Math Magic, (problem #2 on that page) your challenge is to find the edge elimination number of a connected graph.

A single edge elimination is the removal of an edge from a graph, without disconnecting the graph, except for creating lone vertices. For instance, in the graph below, the two leftmost edges and the rightmost edge may be legally eliminated, but the center edge may not, because that would lead to two disconnected components larger than a single vertex.

An edge elimination sequence is the elimination of every edge in a graph in a specified order. Each elimination must be legal at the point in the sequence when it is performed. For instance, one legal edge elimination sequence on the above graph would be to remove the rightmost edge, then the center edge, then the top-left edge, then the bottom-left edge.

The edge elimination number of a graph is the number of different edge elimination sequences that a graph has. For instance, the above graph has an edge elimination number of 14. There are 4 sequences starting with the top left edge, 4 with the bottom left edge, and 6 with the right edge.

Input: The input graph is guaranteed to be connected. The graph will be given as a list of edges with labeled vertices. for instance, the above graph might be given as:

[(0,2), (1,2), (2,3), (3,4)]

Within that requirement, whatever format is most convenient for your language/code is fine. Don't cheese this. (e.g. no code in the vertex labels.)

Code: You may write a program taking input from the command line or from STDIN, or a function, or a verb, or your language's equivalent.

This is code golf, fewest bytes wins.

Tests:

One edge:
[(0,1)]
1

Path:
[(0,1), (1,2), (2,3), (3,4)]
8

Triangle with two additional edges off one vertex:
[(0,1), (1,2), (0,2), (0,3), (0,4)]
92

Randomly generated:
[(0, 2), (0, 4), (1, 2), (1, 4), (2, 5), (3, 4), (3, 5)]
1240

[(0, 2), (0, 3), (1, 3), (1, 4), (1, 5), (2, 3), (3, 4), (3, 5)]
16560

Again, this is code golf, fewest bytes wins. Please ask any clarifying questions, or tell me if I've done something wrong.

Answer 1

APL (77)

{0=⍴,⍵:1⋄C←0/⍨⍴V←∪∊G←⍵⋄0∊C⊣{C[V⍳⍵]:⍬⋄C[V⍳⍵]←1⋄∇¨⍵~⍨∊G/⍨⍵∊¨G}⊃V:0⋄+/∇¨⍵∘~∘⊂¨⍵}

This is a function that takes a list of edges as a graph, i.e.:

      {0=⍴,⍵:1⋄C←0/⍨⍴V←∪∊G←⍵⋄0∊C⊣{C[V⍳⍵]:⍬⋄C[V⍳⍵]←1⋄∇¨⍵~⍨∊G/⍨⍵∊¨G}⊃V:0⋄+/∇¨⍵∘~∘⊂¨⍵} (0 2)(0 3)(1 3)(1 4)(1 5)(2 3)(3 4)(3 5)
16560

(Incidentally, this takes about half a second on my computer.)

So the format is [[v1,v2], [v1,v2], ...]. To pass in a single-edge graph, you need to enclose it first, otherwise you get [0,1] instead of [[0,1]]:

      {0=⍴,⍵:1⋄C←0/⍨⍴V←∪∊G←⍵⋄0∊C⊣{C[V⍳⍵]:⍬⋄C[V⍳⍵]←1⋄∇¨⍵~⍨∊G/⍨⍵∊¨G}⊃V:0⋄+/∇¨⍵∘~∘⊂¨⍵} ⊂0 1
1  

Explanation:

• Base case 1 (empty graph):
  • 0=⍴,⍵:1: if the graph is empty, return 1: the current path has emptied the graph while keeping it connected.
• Base case 2 (unconnected graph):
  • C←0/⍨⍴V←∪∊G←⍵: store the list of edges in G, the vertices in V, and a 0 for each vertex in C.
  • {...}⊃V: See if the graph is connected. Starting with the first vertex:
    • C[V⍳⍵]:⍬: if the vertex has already been visited, do nothing
    • C[V⍳⍵]←1: mark the current vertex as visited
    • G/⍨⍵∊¨G: find each edge this vertex is connected to
    • ⍵~⍨∊: find all vertices involved in those edges, except the current vertex
    • ∇¨: visit all those vertices
  • 0∊C...:0: afterwards, if one of the vertices is not visited, the graph is no longer connected. The current path is invalid, so return 0.
• Recursive case:
  • ⍵∘~∘⊂¨⍵: For each edge, create the graph formed by removing that edge, along with any orphaned vertices, from the current graph.
  • ∇¨: For each of those graphs, find its edge elimination number.
  • +/: Sum those.

Answer 2

Pyth, 23

L?/1lbf!tfaYTbbsmy-b]db

Explanation:

L: defines a function, y, of one input, b. Returns the value of its body.

?: _ if _ else _

The first argument to ? will be the value returned if we terminate. The second will be the termination test, and the third will be the recursive case.

/1lb: If we terminate, there are two possibilities: we have reached a graph with 1 edge, or we have reached a clearly disconnected graph, which thus has more than one edge. /1lb is 1, floor divided by the length of the input graph. This returns 1 in the base case of a 1 edge graph, or 0 in any disconnected termination case.

faYTb: This is the inner filter of 2nd argument. It filters out every edge Y that overlaps with the edge T of the outer filter. a is setwise intersection.

!tfaYTb: ! is logical not, t is tail, so this will be True if there is exactly 1 edge sharing a vertex with T, or False otherwise.

f!tfaYTbb: This runs the above test on every edge in the graph. It is evaluated in a boolean context, and it is truthy if any edge in the graph shares no vertices with any other edge in the graph. If this is the case, we terminate, because the graph is either disconnected or has 1 edge. Note that there are some disconnected graphs that we do not terminate on, but their recursive calls will eventually terminate with a return value of 0.

smy-b]db: This is the recursive case. We take the sum, s, of the edge elimination number, y, of the graph with each edge removed. -b]d is b with the edge d removed, y-b]d is the EEN of that graph, and my-b]db is this value for d being each edge in the graph, and smy-b]db is the sum of those values.

Tests: (yQ runs the function on the input)

$ pyth -c 'L?/1lbf!tfaYTbbsmy-b]dbyQ' <<< '[(0,1)]'
1
$ pyth -c 'L?/1lbf!tfaYTbbsmy-b]dbyQ' <<< '[(0,1), (1,2), (2,3), (3,4)]'
8
$ pyth -c 'L?/1lbf!tfaYTbbsmy-b]dbyQ' <<< '[(0,1), (1,2), (0,2), (0,3), (0,4)]'
92
$ pyth -c 'L?/1lbf!tfaYTbbsmy-b]dbyQ' <<< '[(0,2), (0,4), (1,2), (1,4), (2,5), (3,4), (3,5)]'
1240
$ pyth -c 'L?/1lbf!tfaYTbbsmy-b]dbyQ' <<< '[(0,2),(0,3),(1,3),(1,4),(1,5),(2,3),(3,4),(3,5)]'
16560

Answer 3

Python, 228 bytes

p=lambda l,r,d:reduce(lambda y,x:p(y[0]|set(x),[],y[1])if(x[0]in y[0]or x[1]in y[0])else(y[0],y[1]+[x]),d,(l,r))
def c(h):
  k=0
  for i in range(len(h)):g=h[:i]+h[i+1:];k+=len(g)<2 or p(set(g[0]),[],g)[1]==[]and c(g)
  return k

One edge:

c([(0,1)])
1

Path:

c([(0,1), (1,2), (2,3), (3,4)])
8

Triangle with two additional edges off one vertex:

c([(0,1), (1,2), (0,2), (0,3), (0,4)])
92

Randomly generated:

c([(0, 2), (0, 4), (1, 2), (1, 4), (2, 5), (3, 4), (3, 5)])
1240
c([(0, 2), (0, 3), (1, 3), (1, 4), (1, 5), (2, 3), (3, 4), (3, 5)])
16560

Explanation:

In the first Statement I create a function that checks if a given graph d is connected.

 p=lambda l,r,d:reduce(lambda y,x:p(y[0]|set(x),[],y[1])if(x[0]in y[0]or x[1]in y[0])else(y[0],y[1]+[x]),d,(l,r))

The idea of this is: You have to reduce a graph with the given edge-tuples to a list which contains every connected point, called connected_set and a list with all not-connected-yet tuples, called not_connected. Core is the reduce-function, which is a built-in what calls every a given function with two parameters for each element in a list. Reduce works so: reduce(callable, list, initial)

1. callable(initial, list[0]) returns element
2. callable(element, list[1]) ...
3. callable(element, list[n])

For given code I return a tuple contained of (connected_set, not-connected-yet). The initial value is the connected_set containing of the first found point of the graph. the not-connected-yet is initial en empty list.

lambda y,x:p(y[0]|set(x),[],y[1])if(x[0]in y[0]or x[1]in y[0])else(y[0],y[1]+[x])

means:

def reducer((connected_set, not-connected-yet), element):
    #an edge is connected, if left or right point is in connected_set
    if element[0] in connected_set or element[1] in connected_set:
        #add both points to connected_set
        connected_set |= set([x[0], x[1])
        #resolve not-connected-yets
        check_graph(connected_set, not-connected-yet=[], list=not-connected-yet)
        return (connected_set, not-connected-yet)
    else
        return (connected_set, not-connected-yet + [element]

def check_graph(connected_set, not-connected-yet, list):
    return reduce(reducer, list, (connected_set, not-connected-yet))

A Graph is connected, when check_graph returns a tuple, which second element is an empty list.

The rest is addition:

def c(h):
  k=0
  for i in range(len(h)):g=h[:i]+h[i+1:];k+=len(g)<2 or p(set(g[0]),[],g)[1]==[]and c(g)
  return k

means readable:

def count_graph(graph)
    sequences = 0
    #iterate over the possibilities to eliminate an edge on given graph
    # e.g.: graph = [1, 2, 3]
    # i=0: parted_graph = [2, 3]
    # i=1: parted_graph = [1, 3]
    # i=2: parted_graph = [2, 3]
    for i in range(len(graph)):
        parted_graph = graph[:i] + graph[i+1:]
        if len(parted_graph) < 2:
            # a graph with one edge is result of a sequence so raise num
            sequences += 1
        else:
            # continue eliminating if graph is connected
            if check_graph(set(parted_graph[0]), [], parted_graph)[0] == []:
                sequences += count_graph(parted_graph)
    return sequences