Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
HELP URGENT! greedy algorithm

Subject: HELP URGENT! greedy algorithm

From: Rae S.

Date: 20 Mar, 2011 08:12:05

Message: 1 of 3

I have a symmetrical nxn matrix and I am deleting an edge each time. Except before I delete the edge, i have to make sure the matrix is still connected and acyclic. How else would I put this in MATLAB?

thanks :)

Subject: HELP URGENT! greedy algorithm

From: Roger Stafford

Date: 20 Mar, 2011 18:33:04

Message: 2 of 3

"R. S." wrote in message <im4csk$9p9$1@fred.mathworks.com>...
> I have a symmetrical nxn matrix and I am deleting an edge each time. Except before I delete the edge, i have to make sure the matrix is still connected and acyclic. How else would I put this in MATLAB?
>
> thanks :)
- - - - - - - - - -
  I assume by 'connected' and 'acyclic' you are referring to the associated graph of the matrix. If I understand this concept correctly, a 'tree' is both connected and acyclic. By removing any of its edges, you are certain to make it disconnected. If you add any edge you are certain to make it no longer acyclic. Therefore I don't understand what you are trying to do when you use the word 'still' in "make sure the matrix is still connected and acyclic". Can you please explain what you mean?

Roger Stafford

Subject: HELP URGENT! greedy algorithm

From: R. S.

Date: 20 Mar, 2011 19:24:04

Message: 3 of 3

"Roger Stafford" wrote in message <im5h90$avv$1@fred.mathworks.com>...
> "R. S." wrote in message <im4csk$9p9$1@fred.mathworks.com>...
> > I have a symmetrical nxn matrix and I am deleting an edge each time. Except before I delete the edge, i have to make sure the matrix is still connected and acyclic. How else would I put this in MATLAB?
> >
> > thanks :)
> - - - - - - - - - -
> I assume by 'connected' and 'acyclic' you are referring to the associated graph of the matrix. If I understand this concept correctly, a 'tree' is both connected and acyclic. By removing any of its edges, you are certain to make it disconnected. If you add any edge you are certain to make it no longer acyclic. Therefore I don't understand what you are trying to do when you use the word 'still' in "make sure the matrix is still connected and acyclic". Can you please explain what you mean?
>
> Roger Stafford


Sorry I knew I didn't make the question very clear. I have a graph G (it is not a tree yet). I am going to delete the maximum edge one at a time considering the graph is still connected everytime to find a tree with exactly k number of edges.

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us