Un lenguaje de primer orden para grafos

Question

Dejemos que $L$ sea un lenguaje de primer orden con una relación $E(x,y)$ . Podemos pensar en variables $x,y,z...$ como representación de los vértices y $E(x,y)$ representando "Hay una arista incidente en $x,y$ ". Necesito expresar en $L$ las siguientes afirmaciones:

1. El gráfico no tiene bucles

2. El gráfico no tiene aristas múltiples

3. Las aristas no están dirigidas

4. No hay ciclos de longitud 3

5. El grado de cada vértice es como máximo 2

Hasta ahora se me ha ocurrido:

1. $\forall x (\neg E(x,x)) $
2. Inseguro
3. Inseguro
4. $\forall x \forall y \forall z((E(x,y)\wedge E(y,z))\rightarrow\neg E(x,z)) $
5. $\forall a \forall b \forall c \forall d((E(a,b)\wedge E(a,c)\wedge E(a,d)\rightarrow((b=c)\vee(c=d)))) $

Agradezco la ayuda con los demás

Answer 1

En primer lugar, las formulaciones lógicas de las propiedades de los multigrafos requieren tener variables separadas para los vértices y las aristas (véase https://en.wikipedia.org/wiki/Logic_of_graphs ). Por lo tanto, la lengua $L = \{ E \}$ que consiste en una única relación binaria, como se ha indicado anteriormente, no es el lenguaje apropiado para los multigrafos, pero sí lo es para los grafos simples.

Dado que las propiedades teóricas del modelo de los multigrafos requieren tener variables separadas para los vértices y las aristas, el lenguaje singleton $L = \{ E \}$ no puede utilizarse para construir afirmaciones como "el grafo no tiene aristas múltiples".

En la lengua $L = L_{\text{simple}} = \{ E \}$ de los gráficos simples, el $L$ -sentencia $$\forall u \ \forall v \left( E(u, v) \Longrightarrow E(v, u) \right)$$ es el axioma para los grafos no dirigidos

Obsérvese también que el $L$ -La frase dada para la cuarta afirmación anterior no es del todo correcta si se permite que los grafos considerados en el contexto de este problema tengan múltiples aristas. La frase original $$\sigma_4 = \forall x \ \forall y \ \forall z \ E(x, y) \wedge E(y, z) \Longrightarrow \neg E(x, z)$$ no expresa exactamente que "no hay ciclos de longitud 3" si se permite que los grafos considerados en el contexto de este problema tengan múltiples aristas. Por ejemplo, consideremos el $L$ -dada por el multigrafo (no dirigido) $C_{2} = \{ \{ v_1, v_2 \}, \{ e_1, e_2 \} \}$ , donde $e_1$ y $e_2$ ambos unen los dos vértices en $V(C_{2})$ . En este caso es obviamente cierto que $C_{2} \models \sigma_{4}$ porque $$E(v_{1}, v_{2}) \wedge E(v_{2}, v_{1}) \Longrightarrow \neg E(v_{1}, v_{1})$$ y $$E(v_{2}, v_{1}) \wedge E(v_{1}, v_{2}) \Longrightarrow \neg E(v_{2}, v_{2}).$$

Answer 2

(3). Para decir que las aristas son no dirigidas, basta con decir $\forall x \forall y (E(x,y) \leftrightarrow E(y,x))$ .

(2). Si sólo tiene el predicado $E(x,y)$ si hay una arista, entonces no se puede expresar nada relacionado con la multiplicidad de aristas (además de la presencia o ausencia). Sin embargo, se podría utilizar el gráfico de incidencia como estructura lógica subyacente, y tener un objeto $e$ representando cada arista, y en lugar de $E$ tiene un predicado $\in$ que le indica el vértice $x$ pertenece a $e$ . Entonces, si tienes un borde múltiple tendrás $e_1$ y $e_2$ que están conectadas a $x_1$ y $x_2$ (con $e_1 \neq e_2$ etc.). En este lenguaje la ausencia de bucle se expresa por la ausencia de aristas de grado $1$ . Además, esta forma alternativa de ver la lógica de primer orden de los grafos tiene exactamente la potencia expresiva del marco clásico cuando se restringe a los grafos. Puedes leer más sobre ello en el trabajo de Courcelle.