¿Está conectado el gráfico vacío?

Question

Es el vacío gráfico siempre conectado ? He mirado a través de algunas fuentes (por ejemplo Diestels "teoría de grafos") y en este caso especial, parece ser que no se incluye. ¿Cuál es la opinión general para este caso ?

Como he podido recopilar a partir de la lectura de Diestel la teoría de grafos, desconectado de los gráficos y el trivial gráfico (es decir, el uno con un solo vértice) 0-conectado. Pero el trivial gráfico está conectado, ya que siempre hay un camino a partir de ese nodo a sí mismo. Así que no es la terminología un poco engañoso ? Porque uno podría tomar "0-conectado" para significar "desconectado", pero en el caso de la trivial gráfico que este no es más, que me parece - en el nivel de la terminología - estéticos.

Answer 1

Mi opinión es que el vacío de la gráfica debe ser considerado como desconectado, de la misma manera que $1$ debe ser considerado como no prime. La razón es que cada gráfico debe tener un único "factorización prima" en un discontinuo de la unión de conectado gráficos, y de este teorema es falso si se permite que el vacío gráfico para estar conectado.

El hecho de que la definición estándar ("cualquiera de los dos vértices pueden ser conectados por un camino") es vacuously cierto para el vacío de la gráfica es engañosa. Este es un fenómeno conocido en la nLab como demasiado simple para ser simple y es causada por el uso de definiciones que no funcionan bien para vaciar los objetos. Aquí es una mejor definición:

Un gráfico está conectado si tiene exactamente un componente conectado.

Recordemos que un componente conectado es una clase de equivalencia en virtud de la relación de equivalencia generada por la relación de adyacencia; en particular, no es necesario definir la palabra "conectado" para definir lo que es un componente conectado. El vacío de la gráfica tiene cero, en lugar de uno, los componentes conectados.

Answer 2

Un grafo es conectado si para todas las $x, y \in V(G)$ existe un camino de $x$ $y$el uso de bordes en $E(G)$. La nula gráfico que cumpla con estos criterios por lo que está conectado. El término desconectado , es la negación de la conexión; es decir, existe un $x, y \in V(G)$ para las que no hay camino de $x$ $y$el uso de bordes en $E(G)$. Es imposible encontrar una $x$ $y$ debido a que el conjunto está vacío, por lo tanto, la nula gráfico no puede ser desconectado.

No podemos cambiar la definición estándar a la gráfica está conectado si tiene exactamente un componente conectado". Por otra parte, no tiene sentido definir "conectado", usando el término "componente conectado", porque para hablar de un componente conectado se había ya tiene que saber qué conectado significado (así como el término "componente").

En un nivel personal, la definición de gráfico que aprendí a no permitir la nula gráfico. Un gráfico que consistía en un conjunto no vacío V de vértices junto con una (posiblemente vacía) conjunto de aristas, E. sería prudente para definir "el gráfico" de esta manera mantener la nula la gráfica de la existente.

Answer 3

Para algunos autores, gráficos vacíos y nulos gráficos son conceptos diferentes. El gráfico nulo es el grafo sin nodos, mientras que un grafo vacío es un grafo sin aristas. Un grafo vacío de dos vértices no está conectado.

Sobre el gráfico nulo, por supuesto depende de la definición de conectividad. Si un gráfico está conectado si cualquier dos vértices pueden ser conectados por un camino, el gráfico nulo está conectado.