I know this forum is not about algorithm but please can you help?

Question

Hi there. Please I need some help with the following problem which has given me headaches. Here it is: For a connected graph G the following algorithm is executed: -a queue Q is initialized with a graph G -while Q isn't empty -extract the first graph in Q and put it in H -determine A - a minimal articulation set in graph H -assuming that V1...  Vk are the sets of vertices of the connected components in which H is broken by A add to Q the following graphs: [A U Vi]H i =1 n The questions is to prove that the total number of graphs inserted in Q isn't greater that |G|*|G| My note: What does |G|*|G| mean? I was told that it means the number of vertices of graph G squared . Others told me that |G| might mean |V|*|E|. Which is which ? Please can you help? Thanks in advance and please forgive me for the inconvience of posting an algorithm thread in a forum about C# ! Cheers Adisor

aaniculaesei · Answer

Hi It is not about implementing the algorithm given. This is a theoretical problem. You are given this algorithm and you are asked to demonstrate mathematically that the number of inducted subgraphs entered in the queue Q isn't greater then the |G|*|G|. Bare in mind that the graph G is connected and if you think a little [AUVi]H are connected too. Note : [AUVi]H are the subgraphs inducted by the sets AUVi into graph G. Cheers Adisor P.S. Thanks for replying !

sacresp · Answer

|G| is the number of vertices. Have you tried implementing it?

aaniculaesei · Answer

Hi again  I've tried several forums which are supposed to be about algorithm and didn't get any answer . Please help. Thank you very much. Cheers Adisor