Eddy23

3 Questions
0 Answers

0

634

1

+12

graph algorithm problem

"Given a DAG (directed acyclic graph) G=(V,E) with weighted edges. Suggest an O(|V|+|E|) time algorithm for finding the weight of the maximum weight path in G". I know I need topoligical sort here, but how can I continue from this?

Eddy23 Oct 5, 2015

0

747

0

+12

graph theory question

the question: Let it be G a planar graph, 3-colorable, in which every face is triangle (including the outer face). prove that G contains euler circuit.
so, I have tried to prove that for some v vertex of G his degree is even, but I didn't succeed. read more ..

difficulty advanced

Eddy23 Jun 7, 2015

0

619

0

+12

regular graph question

let it be G=(V,E) bipartite connected graph, r- regular when r>=2.
prove that there is a path which his size is at least 2r-1.
how can I solve this?

difficulty advanced

Eddy23 May 24, 2015