Secuencia inductivamente definida de vecindarios de grafos.

Question

Estoy tratando de resolver el siguiente problema:

Deje $v_0$ ser un vértice en un grafo $G$, e $D_0 := \{v_0\}$.

1. Para $n = 1, 2 \dots$ inductivamente definir $D_n := N(D_0 \cup D_1 \cup \dots \cup D_{n-1})$.

2. Mostrar que $D_n = \{v | d(v_0, v) = n\}$y $D_{n+1} \subseteq N(D_n) \subseteq D_{n-1} \cup D_{n+1}$ para todos los $n \in \mathbb{N}$.

Aquí, $N_G(V') = N(V')$ es el barrio de $V' \subseteq V(G)$, y $d_G(u, v) = d(u, v)$ es la distancia en $G$ de dos vértices $u$, $v$.

Yo soy incapaz de resolver la tarea porque no estoy seguro de si está correctamente definido. Cada tipo de gráfico que parece ser una contradicción con las declaraciones anteriores. Considerar para simplificar el ejemplo siguiente:

Deje $P$ ser un camino, y $v_0$ ser el vértice central en $P$. Entonces

$D_0 = \{v_0\}$,

$D_1 = N(D_0) = \{v | d(v_0, v) = 1\}$,

$D_2 = N(D_0 \copa D_1) = N(\{v_0\} \cup N(\{v_0\})) = \{v | d(v_0, v) \leq 2\}$,

y para todos los $n \geq 2$ obtenemos $D_n = \{v | d(v_0, v) \leq n\}$. En particular, se deduce que el $V(P) = D_r$, donde $r$ es el radio de la $P$.

En este ejemplo se contradice en ambas declaraciones en la segunda parte de la tarea. Puede usted, por favor, ayudarme a encontrar, hay algo que me falta o interpretar incorrectamente?

Answer 1

Se mezcla lo abierto y lo cerrado de la vecindad. Creo que cuando se está declarando $D_n=N(D_0\cup\ldots\cup D_{n-1})$, que implica el abrir barrio

El abierto de vecindad $N(S)$ de un conjunto de vértices $S$ no se incluyen los $S$. Por lo tanto, el uso de su exampla de la ruta de $P$:

$D_0=\{v_0\}$

$D_1=N(D_0)=\{v \mid d(v_0,v)=1\}$

$D_2=N(D_0\cup D_1)=\{v \mid d(v_0,v)=2\}$ y así sucesivamente.

Más precisamente, si se definen $P$como: $$ \ldots \ v_{-n} \ldots \ v_{-2} \ v_1 \ v_0 \ v_1 \ v_2 \ldots \ v_n \ldots$$ A continuación, $D_0=\{v_0\}$, $D_1=N(D_0)=\{v_1,v_{-1}\}$, y $$D_2=N(D_0\cup D_1)= N(\{v_1,v_0,v_{-1}\})=\{v_2,v_{-2}\}$$

Por lo tanto, las declaraciones que tiene como \begin{align*} D_{n+1}=\{v_{n+1},v_{-(n+1)}\} &\subset N(D_n)=N(\{v_{n},v_{-n}\})=\{v_{n+1},v_{n-1},v_{-(n-1)},v_{-(n+1)}\}\\ &\subset D_{n-1} \cup D_{n+1} \end{align*} con una igualdad que en su caso específico de $P$

Answer 2

Depende de cómo defina la vecindad, pero parece que aquí se define de manera que $N(V')$ comprende los vértices adyacentes a algún vértice en $V'$ , excluyendo los vértices en $V'$ .

Entonces en ese caso, $N(D_0\cup D_1)\neq \{v|d(v_0,v)\leq 2\}$ .