4 ms·

> {{V,E}: V = {a,b,c,d,e}, E = {{a,b},{a,c},{b,d},{c,e}}} possibly accompanied by a statement as to whether edges are directed or not. From a math notation poi

by vog 10y ago

> {{V,E}: V = {a,b,c,d,e}, E = {{a,b},{a,c},{b,d},{c,e}}} possibly accompanied by a statement as to whether edges are directed or not. From a math notation point of view, this statement is not needed. If your edges are directed, denote your edges not as sets (which are always unordered in math), but as ordered pairs instead: {{V,E}: V = {a,b,c,d,e}, E = {(a,b),(a,c),(b,d),(c,e)}}

YeGoblynQueenne 10y ago
Thanks. Or you can always use what I think is slightly informal notation, where a directed edge is notated as a -> b (I've seen that in textbooks, but I'm not sure where it's coming from).
- vog 10y ago
  Haven't seen this notation in text books so far, but I guess one of the following 3 things happened: (1) The notation a->b was defined as a simple shorthand, i.e. a->b := (a,b). (2) The notation a->b was defined to be the graph consisting of just a, b and the edge, i.e. a->b := ({a,b}, {(a,b)}) ... this may be followed by some algebraic rules about how to combine small graphs to build larger graphs. (3) The notation a->b may be a somewhat misused notation for functions, meaning the only possible function from set {a} to set {b}, i.e. the function that maps a to b. If you define a function to be a relation (i.e. a set of pairs) where the first elements are unique, then this is acually equal to {(a,b)}, i.e. the set containing exactly this one pair. Interpretation (3) might look somewhat contrieved, but it actually isn't that much of a stretch, given the connections between graph theory and function structures through category theory.
  - YeGoblynQueenne 10y ago
    I believe it's (1) and I think it might originate in Judea Pearl's textbook on causality [1], particularly the section on the IC algorithm. I've also encountered it in a bunch of papers on graph reconstruction, by Wermuth, Lauritzen, Spirtes and Glymour (not all in one go, I don't think). For instance, see [2]. I guess it's convenient notation for a typical step in those algorithms, where two edges are oriented towards a common vertex- shown as A -> B <- C or similar. That's a little more concise than {(A,B),(C,B)} but also more intuitive when the intention is to show how to (re)construct a graph from dependence relations, as those algorithms usually do. ___________________ [1] Causality; models, reasoning and inference: http://bayes.cs.ucla.edu/BOOK-2K/ http://bayes.cs.ucla.edu/BOOK-2K/ [2] A Fast Algorithm for Discovering Sparse Causal Graphs; Peter Spirtes & Clark Glymour: http://repository.cmu.edu/cgi/viewcontent.cgi?article=1316&context=philosophy http://repository.cmu.edu/cgi/viewcontent.cgi?article=1316&c...

by vog 10y ago

YeGoblynQueenne 10y ago

Thanks. Or you can always use what I think is slightly informal notation, where a directed edge is notated as a -> b (I've seen that in textbooks, but I'm not sure where it's coming from).

vog 10y ago
Haven't seen this notation in text books so far, but I guess one of the following 3 things happened: (1) The notation a->b was defined as a simple shorthand, i.e. a->b := (a,b). (2) The notation a->b was defined to be the graph consisting of just a, b and the edge, i.e. a->b := ({a,b}, {(a,b)}) ... this may be followed by some algebraic rules about how to combine small graphs to build larger graphs. (3) The notation a->b may be a somewhat misused notation for functions, meaning the only possible function from set {a} to set {b}, i.e. the function that maps a to b. If you define a function to be a relation (i.e. a set of pairs) where the first elements are unique, then this is acually equal to {(a,b)}, i.e. the set containing exactly this one pair. Interpretation (3) might look somewhat contrieved, but it actually isn't that much of a stretch, given the connections between graph theory and function structures through category theory.
- YeGoblynQueenne 10y ago
  I believe it's (1) and I think it might originate in Judea Pearl's textbook on causality [1], particularly the section on the IC algorithm. I've also encountered it in a bunch of papers on graph reconstruction, by Wermuth, Lauritzen, Spirtes and Glymour (not all in one go, I don't think). For instance, see [2]. I guess it's convenient notation for a typical step in those algorithms, where two edges are oriented towards a common vertex- shown as A -> B <- C or similar. That's a little more concise than {(A,B),(C,B)} but also more intuitive when the intention is to show how to (re)construct a graph from dependence relations, as those algorithms usually do. ___________________ [1] Causality; models, reasoning and inference: http://bayes.cs.ucla.edu/BOOK-2K/ http://bayes.cs.ucla.edu/BOOK-2K/ [2] A Fast Algorithm for Discovering Sparse Causal Graphs; Peter Spirtes & Clark Glymour: http://repository.cmu.edu/cgi/viewcontent.cgi?article=1316&context=philosophy http://repository.cmu.edu/cgi/viewcontent.cgi?article=1316&c...