Gráfico conectado infinito

Question

¿Significa un grafo infinitamente conectado que dados dos vértices cualesquiera hay un camino de longitud finita que los une o el camino puede ser de longitud infinita?

Answer 1

Diestel's Teoría de los gráficos trata de los gráficos infinitos en el capítulo 8. También considera ciertos caminos infinitos, a saber, el rayo (indexado por $\mathbb{N}$ ) y el rayo doble (indexado por $\mathbb{Z}$ ). A camino en un grafo infinito puede ser un camino finito, una semirrecta o una semirrecta doble. Sin embargo, de estas opciones, la trayectoria finita es la única que tiene dos puntos finales. Por lo tanto, cuando se trata de conectividad, se requiere que cualquier par de vértices pueda ser unido por un finito camino.

También se puede abordar la definición de componentes conectados desde otra perspectiva. Digamos que una componente conectada en un grafo $G = (V,E)$ es un conjunto de vértices mínimo y no vacío en función de la inclusión $C \subseteq V$ tal que cada arista $e\in E$ teniendo un punto final en $C$ tiene, de hecho, ambos extremos en $C$ . (En otras palabras, un conjunto de vértices mínimo no vacío que no tiene aristas que entren/salgan). Sea $C$ sea un componente y que $a\in C$ se arreglen. Ahora dejemos que $F_a \subseteq V$ sea el conjunto de vértices a los que se puede llegar desde $a$ a través de un camino de longitud finita. Ahora:

• Podemos demostrar por inducción que $F_a \subseteq C$ debe mantenerse: tenemos $a \in C$ Así que cada vecino de $a$ también debe pertenecer a $C$ y cada vecino de cada vecino de $a$ debe entonces pertenecer también a $C$ y así sucesivamente.
• Por otro lado, se demuestra fácilmente que $F_a$ satisface la propiedad descrita anteriormente, es decir, que toda arista que tenga un punto final en $F_a$ también tiene el otro punto final en $F_a$ . Así, por la minimidad de $C$ no podemos tener $F_a \subsetneq C$ Así que nos encontramos con que $F_a = C$ debe aguantar.

Así, efectivamente, vemos que los vértices que pertenecen a la misma componente pueden estar unidos por un camino finito. (Hay que tener un poco de cuidado con este planteamiento: no está claro a priori en la definición que deban existir componentes conectadas, o que dos componentes conectadas $C_1,C_2\subseteq V$ son iguales o disjuntos. Por suerte, se puede demostrar fácilmente que $F_a$ es efectivamente un componente conexo para cada $a\in V$ y el resto de propiedades se pueden deducir después).

Varios ejemplos estándar de grafos infinitos están conectados en este sentido: el rayo $\mathbb{N}$ el rayo doble $\mathbb{Z}$ El árbol binario completo (contablemente) infinito pero también el gráfico de distancia unitaria del plano donde el conjunto de vértices es $\mathbb{R}^2$ y dos vértices están conectados si y sólo si la distancia euclidiana entre ellos es exactamente $1$ . (Ejercicio divertido: encuentra una fórmula para la longitud del camino más corto entre dos puntos del gráfico de distancia unitaria).

---

Fuera de tema: Es bastante interesante considerar un tipo de camino más abstracto, que está indexado por otros tipos de conjuntos. Por ejemplo, el usuario GregRos da una lista de requisitos para el conjunto de índices $I$ : debe ser un limitado conjunto ordenado linealmente, y cada elemento debe tener un único sucesor (excepto el elemento mayor) y predecesor (excepto el elemento menor). Llamemos a los componentes conectados para esta noción generalizada de caminos los componentes generalizados .

Estoy un poco confundido por el ejemplo que proporciona, ya que no estoy familiarizado con los hipérreos, pero parece que sigue faltando un requisito fundamental: $I$ debe estar conectado en algún sentido. Por ejemplo, considere el siguiente ejemplo:

Ejemplo. Consideremos el conjunto de índices $I = \mathbb{Z}$ con el orden lineal $\prec$ definido de la siguiente manera: $$ 0 \prec 1 \prec 2 \prec 3 \prec \cdots \prec -4 \prec -3 \prec -2 \prec -1. $$ Es decir, los subconjuntos $\mathbb{Z}_{\geq 0}$ y $\mathbb{Z}_{<0}$ se ordenan de la forma habitual, pero declaramos que todo número negativo es mayor que todo número no negativo. El orden es efectivamente lineal y acotado: el elemento mayor es $-1$ y el menor elemento es $0$ . Además, cada elemento tiene un único sucesor (excepto el elemento mayor) y un único predecesor (excepto el elemento menor). Por tanto, este conjunto ordenado cumple todos los requisitos. Obsérvese que no hay ninguna arista que vaya de $\mathbb{Z}_{\geq 0}$ a $\mathbb{Z}_{<0}$ . Por lo tanto, cualquier par de rayos en un grafo infinito puede unirse mediante un camino indexado por $(\mathbb{Z},\prec)$ .

El camino del ejemplo anterior es esencialmente el único tipo nuevo de camino que obtenemos de esta generalización:

Propuesta. Dejemos que $P$ sea un camino infinito indexado por un conjunto de índices $I$ que cumple con los requisitos de GregRos. A continuación, $P$ contiene un subcamino indexado por el conjunto ordenado $(\mathbb{Z},\prec)$ del ejemplo anterior.

Prueba. Dejemos que $a$ y $b$ sean los puntos finales de $P$ y que $s : P \setminus\{b\} \to P$ y $p : P \setminus\{a\} \to P$ denotan las funciones sucesoras y predecesoras en $P$ . Definir $x_0,x_1,x_2,\ldots$ de forma recursiva estableciendo $$ x_n = \begin{cases} a,&\quad\text{if $n = 0$};\\[1ex] s(x_{n-1}),&\quad\text{if $n > 0$}. \end{cases} $$ Esto está bien definido ya que el camino $P$ se supone que es infinito (en cada paso tenemos $x_n \neq b$ para que $x_n$ tiene un sucesor). Del mismo modo, definimos $x_{-1},x_{-2},x_{-3},\ldots$ de forma recursiva estableciendo $$ x_n = \begin{cases} b,&\quad\text{if $n = -1$};\\[1ex] p(x_{n+1}),&\quad\text{if $n < -1$}. \end{cases} $$ Vemos que $\{x_n\}_{n\in\mathbb{Z}}$ es una ruta indexada por $(\mathbb{Z},\prec)$ . $\hspace{2mm}\blacksquare$

Así, si tenemos dos vértices $a$ y $b$ que pueden unirse por un camino infinito, también pueden unirse por un camino indexado por $(\mathbb{Z},\prec)$ . Ahora es fácil determinar las componentes conectadas según esta definición más amplia de caminos:

Propuesta. Dos vértices $a$ y $b$ se encuentran en el mismo componente generalizado si y sólo si se cumple al menos uno de los siguientes criterios:

• Hay un camino finito que une $a$ y $b$ .
• Ambos $a$ y $b$ se encuentran en un rayo.

Nota: para cada componente original tenemos que o bien todos los vértices o bien ningún vértice de la componente se encuentra en una semirrecta. Así, cuando consideramos esta generalización del concepto de caminos, obtenemos esencialmente una especie de compactación de un punto de nuestro gráfico original: tenemos las mismas componentes que antes, excepto que las componentes que contienen un rayo se unen en el infinito. (No obstante, hay que tener en cuenta que la unión disjunta de los infinitos contables gráfico de estrellas $S_{\omega}$ y un rayo sigue estando desconectado, ya que sólo uno de los componentes contiene un rayo. En particular, podría haber más de una componente generalizada con infinitos vértices. Así que quizás mi comparación con las compactificaciones de un punto sea un poco confusa: se podría argumentar que el grafo estelar contablemente infinito $S_{\omega}$ no es localmente compacto para empezar).

Todo esto es muy interesante, pero en la literatura se asume que los vértices de una misma componente están unidos por un camino finito.

Answer 2

Un gráfico infinito es conectado si para cualquier vértice $u, v$ hay un camino finito $x_0 x_1 x_2 \dots x_n$ con $u = x_0, v = x_n$ y no $x_i$ duplicado.