Graph Theory

[meszaj]

my english is not very good. so please be patient... i am learning for an exam (algorithms and data structures) and i have a few questions on graphs. i am not blonde but nevertheless this graph theory is hard for me to understnd. it would be grateful if anyone could answer this and correct my answers.also a short describtion why would be great
would below algorithms work, if one from lower conditions is fulfilled:
1. instead of shortest paths we are looking for the longest paths respectively so, that we only replace conditions bigger-smaller (>,<)
2. Graph has cycles
3. The edges also have negative values
4. when the graph is only one path
5. when the graph is not connected (incoherent)
6. can edges in graph also have path length equal to 0
7. if the graph is one alone cycle (the whole graph is one cycle)

A) KRUSKALs ALGORITHM
1.no
2.
3.
4.
5.
6.
7.
B) PRIMs ALGORITHM
1.yes
2.no
3.no
4.
5.
6.
7.
C) DIJKSTRAs ALGORITHM
1.yes
2.no
3.no
4.
5.
6.yes
7.
D) Critical Path ALGORITHM ( longest possible path )
1.yes
2.no
3.yes
4.
5.
6.yes
7.

thnx in advance :)

[yiannakop]

Hi. A very good book for understanding graphs is:
R. Ahuja, T. Magnanti, J. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, 1993
I've used this book in the past, but I am afraid I don't remember much now. I think that the Dijkstra algorithm doesn't work with negative edges, whereas the Prim alg. and the Kruskal's algorithm work with negative edges. Also, I don't think there is any limitation for all 3 first algorithms for the case where the graph is one alone cycle.

[meszaj]

thnx for the book advise.

[mehdi62b]

Hello meszaj,
what a great question!,I know just KRUSKALs and PRIMs algorithm ....
and everything I tell you is for them ....
hope you found your answers and took your exam very well :wave:
can you help me find the answers too? ....

1. instead of shortest paths we are looking for the longest paths respectively so, that we only replace conditions bigger-smaller (>,<)
2. Graph has cycles
3. The edges also have negative values
4. when the graph is only one path
5. when the graph is not connected (incoherent)
6. can edges in graph also have path length equal to 0
7. if the graph is one alone cycle (the whole graph is one cycle)

I have some question about your conditions
condition 2.I cant get what you mean graph is something that may have also cycles if a graph doesnt have a cycles its called Tree
condition 4.if a graph has only one path its again a graph and these algorithm works correctly
condition 5.these algorithms only works for connected graphs
condition 6.a graph has only one cycle is again a graph and these algorithms work fine

in my opinion the answers are like these
A) KRUSKALs ALGORITHM
1.no
2.yes
3.yes
4.yes
5.no
6.yes
7.yes
B) PRIMs ALGORITHM
1.yes
2.yes
3.yes
4.yes
5.no
6.yes
7.yes

Hope I was right and you confirm my answers

----------------
Mehdi.:)