# Differences

This shows you the differences between two versions of the page.

 sav08:graphs_as_interpretations [2008/03/23 13:50]maysam English Grammer sav08:graphs_as_interpretations [2015/04/21 17:30] Line 1: Line 1: - ====== Graphs as Interpretations ====== - - Directed graph is given by a set of vertices $V$ and a set of edges $E \subseteq V \times V$.  Graph is therefore specified by an [[First-Order Logic Semantics|interpretation]] $I = (V,\alpha)$ in languge ${\cal L} = \{edge\}$ with $\alpha(edge) = E$. - - Example: $D = \{1,​2,​3,​4\}$,​ $\alpha(edge) = \{ (1,2), (2,3), (1,3), (3,4) \}$. - - For a class of graph properties we can write down a formula $F$ such that property holds for graph iff $F$ is true in the interpretation $I$ representing the graph. - - **No self-loops:​** - $- \forall x.\ \lnot edge(x,x) -$ - - **Undirected graph:** - $- ​\forall x.\ edge(x,y) \rightarrow edge(y,x) -$ - - **Tournament:​** - $- ​\forall x, y.\ (edge(x,y) \lor edge(y,x)) \land \lnot (edge(x,y) \land edge(y,x)) -$ - - Note: there is no formula $F$ in this language ${\cal L} = \{edge\}$ that characterizes property "graph has no cycles"​. ​ All properties expressed in first-order logic on graphs are "​local"​. Intuitively,​ formula with $k$ universal quantifiers says that if we pick any set of $k$ vertices in the graph, then they (and their close neighbors) can induce only one of the finitely many specified subgraphs. - - * [[http://​citeseer.ist.psu.edu/​benedikt95relational.html|Relational Expressive Power of Constraint Query Language]] - * [[http://​citeseer.ist.psu.edu/​context/​64580/​0|H. Gaifman, On local and non-local properties, in Logic Colloquium '81, North Holland, 1982]] - - Many more properties become expressible if we take as domain $D$ the set of all subsets of $V$ and allow set operations in our language.