graph - Source and Sink in DAGs -


consider graph g dag. prove in graph g', obtained reversing edges of g, source(s)/sink(s) in g become sink(s)/source(s) respectively.

i can see i'm quite unable give formal proof it. me out. :')

by definition vertex indegree 0 called source , vertex outdegree 0 called sink.

reversing edges, indegree , outdegree interchanged each vertex. means if vertex v in g have indegree d1 , outdegree d2, v in g' has indegree d2 , outdegree d1.

vertex v source in g <=> v has indegree 0 in g <=> v has outdegree 0 in g' <=> v sink in g'.


Comments

Post a Comment

Popular posts from this blog

c++ - Difference between pre and post decrement in recursive function argument -

i have following sample code used pre-decrement void function(int c) { if(c == 0) { return; } else { cout << "dp" << c << endl; function(--c); cout << c << endl; return; } } this function give output input 4 : dp3 dp2 dp1 dp0 0 1 2 3 but when use post decrement void function(int c) { if(c == 0) { return; } else { cout << "dp" << c << endl; function(c--); cout << c << endl; return; } } output goes in infinite loop dp4 can explain me in detail why happens ? this happens because function(c--) called same value of c , when finishes c decremented. recursively called, hence called same value no chance of return , hit stack overflow error. assume this, int x = 1, y = 0; y = x++ result y == 1 , x == 2. if y = ++x , bot x , y 2.
Read more

javascript - How to insert selected radio button value into table cell -

i have 5 radio buttons <input type="radio" id="rating">1 <input type="radio" id="rating2">2 <input type="radio" id="rating3">3 <input type="radio" id="rating4">4 <input type="radio" id="rating5">5 i have 1 table <table id="mytabledata" border="1" style="width:100%"> <tr id="templaterow"> <th>ratings</th> </tr> </table> one add button <input type="button" id="add" value="add" onclick="addradiovalue()"> i've written code dynamically add rows table, when select radio button , click on add button, value of selected radio button should inserted new cell within table ratings. i able thing text box, i'm not able radio button. can me? your problems didn't have name set on radios , tryi
Read more

css - Transitioning Transforms in Safari look terrible/shaky/stuttering -

i have few functions based on scrolling user moves elements , down along page (imitating scroll effect.) in order make little smoother using transition: transform 0.7s cubic-bezier(0.49, 0.47, 0.63, 0.85); (with proper vender prefixing). the problem works great except in safari. there -webkit-transition: -webkit-transform 0.7s cubic-bezier(0.49, 0.47, 0.63, 0.85); causes animation jerk around , gives vibrating effect. have been reading on ages , have tried setting perspective property , backface properties no luck. is there way fix this/has seen this? , safari not allow transitioning transforms? any in understanding problem amazing. i found fiddle http://jsfiddle.net/3yfspjlt/ shows problem. if doesn't blink @ first keep scrolling , down. for curious code, more curious why bug happens in safari specific use case. (although of course trying find answer). js file getelementpositions: function(){ var de = document.documentelement; var windowhight = wind
Read more