Opened 12 years ago

Closed 11 years ago

# Bug in biNodeConnected()

Reported by: Owned by: Alpar Juttner Balazs Dezso major LEMON 1.3 release core hg main kbsandor@…

### Description

The attached code and `.lgf` shows an example where `biNodeConnected()` gives the wrong answer. It's probably about the handling of isolated nodes.

The bug was reported by Sándor Kisfaludi-Bak.

### comment:1 Changed 12 years ago by Balazs Dezso

Currently, the bi-node-connected components are defined as an equivalence relation on the edges in the documentation. Two edges are in the same class, if there is a circle which contains both edges.

By this definition, isolated nodes do not break the bi-node-connectivty property. Unfortunately, it's not intuitive, so we might need to change the definition, and we can require that the graph should be connected.

For bi-edge-connected graphs, the equivalence relation is defined on the nodes (two nodes are in relation, when there are two disjoint paths which connect them), so isolated nodes make the graph disconnected.

### comment:2 Changed 12 years ago by Alpar Juttner

According to wikipedia (and to my knowledge)

In the mathematical discipline of graph theory, a biconnected graph is a connected graph with no articulation vertices.

To make things a bit more complex it also adds that

The property of being 2-connected is equivalent to biconnectivity, with the caveat that the complete graph of two vertices is sometimes regarded as biconnected but not 2-connected.

Anyway, we should follow the above definition for the output of `biNodeConnected()`.

### comment:4 Changed 11 years ago by Alpar Juttner

I got confused a bit. Are empty graphs of 0 and 1 vertex bi-node-connected?

### comment:5 Changed 11 years ago by Alpar Juttner

The wikipedia definition for bi-node-connected is somewhat ambivalent. Instead, I suggest considering it to be equivalent to 2-node-connected, which has a clear definition:

A graph G=(V,E) is k-node-connected if

• G has at least k+1 vertices and
• the result of deleting any (perhaps empty) set of fewer than k vertices is a connected graph.

What about `biEdgeConnected()`? Does it work properly for small graphs?

### comment:6 follow-ups:  7  9 Changed 11 years ago by Balazs Dezso

Uploaded a new patch [792b426a35f0], which uses the connected graph with no articulation point definition. In this case, we need to check that there are no isolated nodes in the graph, or there is only one isolated node and there are no other nodes in the graph.

Whether biEdgeConnected() is valid, it just depends on which definition do we follow.

### comment:7 in reply to:  6 Changed 11 years ago by Alpar Juttner

Whether biEdgeConnected() is valid, it just depends on which definition do we follow.

Hmmm. Very deep observation, indeed... :)

To be more serious, wikipedia says:

Let G = (E,V) be an arbitrary graph. If G' = (E \ X,V) is connected for all X ⊆ E where |X| < k, then G is k-edge-connected.

This looks fine, but. It means that the 1-vertex empty graph is 2 connected, which I'm actually fine with. However, wikipedia also adds that

Minimum vertex degree gives a trivial upper bound on edge-connectivity. That is, if a graph G = (E,V) is k-edge-connected then it is necessary that k ≤ δ(G), where δ(G) is the minimum degree of any vertex v ∈ V

This certainly false for the 1-vertex empty graph.

All in all, I think it is up to us how we define two edge connectivity in this singular case. My proposal is to just follow the definition above, thus 1-vertex empty graph will be 2-edge-connected (in fact, k-edge-connected for any k)

### comment:8 Changed 11 years ago by Alpar Juttner

Looking at the code, the current implementation for `biEdgeConnected()` seems to perfectly follow the definition above.

### comment:9 in reply to:  6 Changed 11 years ago by Alpar Juttner

Uploaded a new patch [792b426a35f0], which uses the connected graph with no articulation point definition. In this case, we need to check that there are no isolated nodes in the graph, or there is only one isolated node and there are no other nodes in the graph.

But this one does not follow the above definition of 2-vertex-connectedness. However, it is more in line with the definition of 2-edge-connectedness.

### comment:10 Changed 11 years ago by Alpar Juttner

Resolution: → fixed new → closed

I rebased the latest patch as [552e3d1242c6] and added some more clarification to the doc ([70b199792735]). They are both merged to branches 1.1, 1.2 and main.

I think we can now close the ticket.

Note: See TracTickets for help on using tickets.