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
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.

[asadvakili]

There All;

I need the proof of Mader's Theorem:
Theorem 3.4.1. (Mader 1978)
Given a graph G with an induced subgraph H, there are always MG(H)
independent H-paths in G.

anyone can help?

[nuzzle]

i am not blonde ....

You mean you're no stupid right?

Well, then you should understand that this is something you need to do yourself.

I suggest you do your best, turn it in, and face the consequences. That's the only way for you to learn. Turning in someone else's thinking won't. Even a blonde can understand that.

[bniazmand]

Hello everyone ,

I have a question related to graph mapping .
I would like to know whether a tool exists that can view a graph with another layout ? For example showing an irregular (custom) graph on a 2d grid . For more information about my request , I have attached a photo to this post. I would be thankful to be assisted .

Kind Regards
Behrad Niazmand

[nuzzle]

It's considered rude to hijack other people's threads. It's better to ask a new question in a new thread.

But I have a question already. Is there some optimization criterion that rules the target layout?

[eransmith02]

I'd always loved making this my favorite subject , but it seems really difficult task :P