Re: Determining the type of the graph

Correction - biconnected graph has no vertex such that removing the
vertex would make it disconnected.

I imagine testing for this in the following way:

-have a flag per vertex to mark it as deleted for the purpose of the
test (or, if graph is not too big, make a copy excluding one vertex)

-test the graph for connectednes by starting from one vertex and
marking all other vertices visited through its edges (and edges of its
neighbors, etc.). In the end all vertices should be marked proving that
every vertex can be reached from selected source vertex. Presumably
that is sufficient to prove that graph is connected.

However, the whole point of my questions is in the fact that I am
unsure about efficiency and correctness of algorithms that I can devise
from my understanding of various definitions and would thus prefer some
reference.

Tony

.

Relevant Pages

  • Re: excellent article on global warming
    ... Klipstein) wrote: ... and the arctic ice is below long term trend ... When I want to know what 'his' graph is I look at 'his' graph. ... The second is the correction. ...
    (sci.electronics.design)
  • Re: walks in graphs
    ... I forgot my most important correction: A Hamiltonian Circuit is ... a closed path through a graph that visits each node EXACTLY once, ...
    (sci.math)
  • Re: sawtooth*cotangent sums (variation on Dedekind sums)
    ... A correction: ... then the graph and the examples really refer to ... I have a second graph ... ... David Bernier ...
    (sci.math)