Funciones, gráficos y matrices de adyacencia

Question

Uno piensa ingenuamente en las funciones (continuas) como en los gráficos ₁ (líneas dibujadas en un espacio de coordenadas bidimensional).

A menudo se piensa en los gráficos (contables) ₂ (vértices conectados por aristas) representados por matrices de adyacencia.

Eso es lo que aprendí desde el principio, pero sólo recientemente reconocí que los gráficos "dibujados" ₁ no son más que matrices de adyacencia generalizadas -continuas-, y por tanto gráficos ₁ son más o menos lo mismo que los gráficos ₂ .

Estoy seguro de que esto es un conocimiento común (quizás implícito) entre los matemáticos en activo, pero me pregunto por qué no lo aprendí explícitamente en ningún libro de texto sobre teoría de conjuntos o grafos que haya leído. Lo habría encontrado esclarecedor.

Mis preguntas son:

¿He leído mis libros de texto demasiado superficialmente?

¿Es la analogía anterior (entre gráficos ₁ y gráficos ₂ ) ¿engañosa?

¿O es la analogía demasiado obvia para ser mencionar?

Answer 1

Mi opinión: la analogía no es engañosa, no es demasiado obvia para ser mencionada, pero tampoco es terriblemente útil. ¿Le has encontrado una utilidad?

EDIT: Aquí hay otra forma de pensar en ello. A $\it relation$ en un conjunto $S$ es un subconjunto de $S\times S$ , es decir, es un conjunto de pares ordenados de elementos de $S$ . Una relación sobre $S$ puede verse como un grafo (dirigido), con un conjunto de vértices $S$ y el borde establece la relación. Dibujamos este grafo dibujando los vértices como puntos en el plano y las aristas como segmentos de línea (dirigidos) que conectan pares de puntos

Consideremos ahora "gráfica" en el sentido de "dibujar la gráfica de $x^2+y^2=1$ ." Esa ecuación es una relación sobre el conjunto de los números reales, y la gráfica se obtiene dibujando los miembros de esta relación como puntos en el plano.

Así pues, los dos tipos de gráfico son dos formas de hacer un dibujo para ilustrar una relación en un conjunto.

Answer 2

En mi opinión, la similitud entre los gráficos1 y los gráficos2 es sólo superficial. Ambos tipos de grafos pueden considerarse subconjuntos particulares de ciertos tipos de productos cartesianos ( $\mathbb R \times \mathbb R$ y $V \times V$ ), pero hasta ahí llega.

Considera:

1. Un gráfico1 se generaliza a funciones de mayor dimensión $\mathbb R^m \to \mathbb R^n$ que no se puede considerar como un gráfico2 cuando $m \neq n$ . Un grafo2 se generaliza a los grafos con aristas etiquetadas, a los multigrafos, etc., que no se pueden considerar como un grafo1.

2. Reordenando el orden de los elementos de la matriz de adyacencia se obtiene el mismo gráfico2, pero no el mismo gráfico1.

3. Dado un grafo1, nos preocupamos por cosas como la inyectividad, la continuidad, la convexidad, etc., que no se corresponden con propiedades útiles del correspondiente grafo2. Dado un grafo2, nos preocupamos por cosas como la conectividad, los caminos más cortos, la planaridad, etc., que no se corresponden con propiedades útiles del grafo1 correspondiente.

Un ejemplo sencillo: El gráfico de $f(x) = x$ es una línea continua, pero un gráfico en el que cada vértice sólo está conectado a sí mismo está completamente desconectado.

Answer 3

Desde el punto de vista de la teoría de conjuntos, ambos son más o menos lo mismo: una colección de pares ordenados que definen una relación que es un gráfico en un caso y una función en otro.

La razón, sin embargo, de que la idea de una matriz continua sea ligeramente problemática es que se necesita saber cuál es la "siguiente" coordenada. Así que la matriz tiene que estar bien ordenada, es más, si requerimos que haya una permutación de las filas que dejan la matriz con el mismo orden (por ejemplo, cambiar dos filas) tenemos que requerir ordinales iniciales, es decir, cardinales, y no cualquier ordinal.

En caso contrario, la matriz con $\omega + 1$ filas puede ser isomorfo al que tiene $\omega$ filas (tomar el $\omega$ -de la primera fila, lo cambias por el de la segunda fila, y así sucesivamente...).

Ahora, las matrices son muy útiles cuando hay alguna correspondencia entre los índices de la matriz y el elemento con el que se está tratando. Así que un gráfico finito y una matriz de adyacencia son similares en ese sentido.

Aunque los números reales pueden estar bien ordenados, esta ordenación no nos dice nada sobre el orden habitual de los mismos, y es más difícil "navegar" dentro de la matriz, y mucho menos mantener la idea de continuidad, ya que estar cerca de otro punto de los números reales no implica estar cerca de él en la matriz.

En ese sentido, ambos gráficos son similares como los perros y los gatos. Ambos son mamíferos (parientes) y tienen pelo, y seguramente se puede encontrar alguna conexión y características comunes, pero en última instancia son animales diferentes, cuando se ven como perros y gatos, y no como mamíferos.