Graph theory: definition of bridge

[jm58660]

is_cut_edge() says "A cut edge (or bridge) is an edge that when removed increases the number of connected components.", bridges() says "A bridge is an edge whose deletion disconnects the graph. A disconnected graph has no bridge."

Which definition we should use?

In any case there are missing crosslinks is_cut_edge() <-> is_cut_vertex() etc.

Depends on #24163

CC: @dcoudert

Component: graph theory

Issue created by migration from https://trac.sagemath.org/ticket/24159

[tscrim]

comment:1

IMO, the former for the Tutte polynomial.

[jm58660]

comment:2

Replying to @tscrim:

IMO, the former for the Tutte polynomial.

OK. Is there any better way to make change than add a "NOTE: Prior to version 8.x this function..."?

[tscrim]

comment:3

Not to my knowledge. In some ways, you could argue that one of the behaviors is a bug due to incompatible definitions, so any sort of deprecation/warning is not necessary. Although I think of sthe pacebar... However, this might be a change of subtly worthy enough for a sage-devel ask.

[dcoudert]

comment:4

You could simply say that a bridge is a cut edge if and only if the graph is connected ?

[jm58660]

comment:5

Easier to wait for #24163 before this.

[jm58660]

Dependencies: #24163

[adarsh-kishore786]

comment:6

In my opinion, the first definition is the more apt. In the second definition, the problem is in the line "A disconnected graph has no bridge".

This is not true as the individual connected components of a graph are subgraphs in themselves and they also can have bridge edges.