What is the relation between the topological notion of closure and the closure of a node in a graph? Here, by the closure of a node I mean its closed neighborhood. I came across this definition in p.662 of Murphy's Machine Learning: A Probabilistic Perspective (an excerpt containing the relevant page is available here).
I am aware of two ways to define a topology on a graph:
(1) Define a metric by $d(u,v)$ = (length of shortest path between $u$ and $v$), and then take the metric topology, which in this case is just the power set of the vertices (since for every node $u$ we have, for example, $B_{1/2}(u)=\{u\}$). (Note: this metric only makes sense for connected graphs, but for unconnected nodes $u$ and $v$ you could just define $d(u,v)=\infty$ and generate the topology the usual way.)
(2) Take as a subbasis the set of open neighborhoods of the graph (see this page).
In neither of these topologies is the closed neighborhood of a node always the closure of the node. In the first case, the closure of a node is always itself, so the closure is the closed neighborhood if and only if the node has no neighbors. In the second case, the closed neighborhood is also not always the closure. For example, say the graph is $(\{1,2,3\},\{23\})$. Then our subbasis is $\{\emptyset,2,3\}$, so our topology is $\{\emptyset,123,2,3,23\}$, so our closed sets are $\{\emptyset,123,1,12,13\}$; thus, the closure of $1$ is just itself.
Murphy, Kevin P., Machine learning: A probabilistic perspective, Cambridge, MA: MIT Press (ISBN 978-0-262-01802-9/hbk; 978-0-262-30616-4/ebook). xxix, 1067 p. (2012). ZBL1295.68003.
Answer
I think you've given a good argument that there's not a very close relationship. Another argument: topological closure is always a closure operator; in particular, the closure of a set equals the closure of the closure. This is not the case for closed neighborhoods in graphs, except in very simple cases.
No comments:
Post a Comment