Definición de gráfico bipartito del libro de Murty-Bondy

Estaba leyendo la definición de gráfico bipartito y un momento me confunde. Debido a esta definición podemos considerar cualquier gráfico GRAMO = ( V , mi ) como bipartito, si tomamos X = ∅ y Y = V . Sin embargo, estoy seguro de que mi razonamiento es falso.

¿Me estoy perdiendo de algo?

ingrese la descripción de la imagen aquí

Respuestas (2)

Sí, te estás perdiendo la parte de que "cada borde tiene un extremo en X y un extremo en Y ." A menos que GRAMO no tiene bordes, no puedes tener X = ∅ o Y = ∅ .

¡Gracias por su respuesta! Pero no entendí por qué no podemos aceptar que estén vacíos.
Para cada borde, un extremo debe aparecer en X y un extremo debe aparecer en Y , Así que si mi no está vacío, entonces ambos X y Y contienen al menos un elemento.
¿Por qué? el libro no dice eso X y Y deben ser subconjuntos no vacíos de V .
OK, te daré un gráfico arbitrario y exhibirás X y Y que satisfacen la definición de bipartito. Llevar GRAMO = k 3 , el gráfico completo en 3 vértices, con V = { 1 , 2 , 3 } y mi = { { 1 , 2 } , { 1 , 3 } , { 2 , 3 } } .
En este caso no es posible. Pero suena probablemente estúpido, pero no puedo entender la lógica aquí. ¿Qué pasa si añadimos en la definición que X , Y ≠ ∅ ?
si especificas X y Y no vacío en la definición, la única diferencia es que no permitiría los gráficos vacíos con mi = ∅ de ser llamado bipartito.
Déjame pensar en ello. Pero, ¿por qué en la definición de gráfico conexo consideramos una partición no vacía?
Una pequeña corrección: si especificamos X y Y no vacío en la definición, entonces todos los gráficos con | V | ≥ 2 , mi = ∅ siguen siendo bipartitos. Luego, debido a esta "definición modificada" gráficos con | V | ∈ { 0 , 1 } y mi = ∅ NO son bipartitos.
Sí, estoy de acuerdo con tu corrección.
¿Puedo hacerle una pregunta más, por favor: por qué en la definición de gráficos conectados requerimos que las particiones no estén vacías?
Por favor abra una nueva pregunta para eso.
Abrí la nueva pregunta. Por favor echa un vistazo.
@PlayGame Puse una respuesta separada para algo más largo que un comentario, pero en realidad si necesita particiones no vacías, incluso un gráfico de 1 vértice sin bordes aún no sería bipartito, ya que para particionar un gráfico de 1 vértice necesitaría 1 de los dos conjuntos estar vacios
@Alan Él explicó eso con | V | ∈ { 0 , 1 } .
@RobPratt 1 no funciona, no puede particionar un conjunto de 1 elemento sin que uno de los dos conjuntos de particiones esté vacío
@Alan, correcto, y eso es lo que dijo PlayGame. Si | V | = 1 y mi = ∅ y tu requieres X y Y ambos no vacíos, entonces GRAMO no sería bipartito bajo esa definición modificada.

Como faceta adicional a la otra respuesta, un grafo es bipartito si hay una forma de separar los vértices de modo que cada borde conecte una parte con la otra. Dado que en la lógica moderna, cualquier declaración universal sobre un conjunto vacío es verdadera, si no hay bordes, entonces es bipartito sin importar la partición que use.

Entonces, obtenemos si el conjunto de bordes está vacío, es bipartito ya sea que permitamos o no que la partición sea la trivial. Si el conjunto de bordes no está vacío, la partición trivial no funcionará para demostrar si es bipartito o no. Entonces, la única "ventaja" que obtenemos de permitir la partición trivial (un conjunto vacío, el otro todo el espacio) es que podemos considerar el gráfico completamente vacío: sin vértices, sin bordes para ser bipartito (como la única partición de la gráfico vacío está en dos conjuntos vacíos de vértices).

Como nos gustaría incluir el conjunto vacío como bipartito (vacuamente), debemos permitir que el conjunto vacío sea una partición en este caso.

¿Qué pasa con el gráfico con un solo vértice y sin bordes? Eso es bipartito, ¿no? En ese caso, una de las dos partes debe ser el conjunto vacío.
Definición de gráfico bipartito del libro de Murty-Bondy
RespuestasAquíPolítica de privacidad1y, 0v