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

javascript - three.js lot of meshes optimization -

i'd use three.js render scene containing lot of small meshes create stacks. here's fiddle: http://jsfiddle.net/3bl6fbse/ i'd guys me optimizing code. can see, bit laggy because of low fps. i've written code fast, , m aware creating materials , meshes in loop bad practice. thing need know is: how optimize scene, not doing basic techniques creating materials , meshes outside of loop. i tried use meshes scale's property result ugly, there isn't "stack" effect. tried use mesh.copy ends on same bad performance. thanks
Read more

smartface.io - Proper way to change color scheme for whole application -

pls give me hint best way change color scheme whole smartface application: 1. statically (before building project) 2. dynamically (from within running application) if going change scheme 1 time, can change statically. can define new colors, , change old ones in .pge files. but if want change scheme colors more once or while using application, can in runtime dynamically. done in script files. objects properties such fillcolor can changed in scripts. i cannot 1 best changing in runtime looks better. example, can use editbox colors, , can use button, when pressed can change color scheme, etc.
Read more

Email notification in google apps script -

https://support.google.com/docs/answer/91588?hl=en i have sheet the cells filled in data pulled via apps script, website. pull in exact same data, not. on old sheets version use able emails when data "changes" different value. new sheets, email when new data pasted cells, though exact same data......and, can't set @ ranges anymore, entire document. there easy way watch cells when data changes, , email myself? this looks lot you're trying do. for checking whether value has changed after edit, this gives necessary information it. hence, know whether new value same 1 or not. implementing "workaround" talked in second link, able compare , send email myself if value changed. initiate onedit trigger goes off onedit function uses these lines after checks in place have passed. var email = "xyz@whatever.com"; mailapp.sendemail(email, "triggermail", "a change has occurred in sheet"); note: sends "notification...
Read more