Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision | Next revision Both sides next revision | ||
|
sav08:graphs_as_interpretations [2008/03/19 15:44] vkuncak |
sav08:graphs_as_interpretations [2008/03/19 16:16] vkuncak |
||
|---|---|---|---|
| Line 3: | Line 3: | ||
| Directed graph is 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$. | Directed graph is 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$. | ||
| - | For several properties of graphs we can write down a formula $F$ such that property holds for graph iff $F$ is true in the interpretation $I$ representing the graph. | + | 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:** | **No self-loops:** | ||