Estaba revisando el tema sobre la conectividad de los gráficos. Allí se hablaba de los términos " corte de borde mínimo " y " corte mínimo de los bordes ". Sé que ambos son los conjuntos de aristas si se eliminan del gráfico $G$ , hace que $G$ desconectado. Pero no consigo captar la diferencia básica entre estos dos términos. ¿Es lo mínimo siempre lo mínimo o viceversa? gracias.
Véase, por ejemplo, este enlace que enumera de forma concisa las definiciones y la distinción, y donde encontrará ilustraciones que representan las distinciones.
Un corte del borde es un conjunto de aristas que, si se eliminan de un gráfico conectado desconectará el gráfico.
A corte mínimo de los bordes es un corte de arista tal que si se vuelve a poner cualquier arista en el gráfico, el gráfico se reconecta.
A corte de borde mínimo es un corte de arista tal que no hay otro corte de arista que contenga menos aristas.
Un corte de borde mínimo es siempre mínimo, pero un corte de borde mínimo no es siempre mínimo [la negrita es mía].
Un corte de arista mínimo (y por tanto mínimo) siempre dará lugar a dos componentes conectados.
$\qquad\qquad$ 
$\qquad\qquad$ 
Figura $1$ muestra el gráfico original.
Figura $2$ muestra el corte máximo de los bordes - simplemente elimina todos los bordes.
Figura $3$ muestra un corte de borde mínimo (y por tanto mínimo).
Figura $4$ muestra un corte de borde mínimo (que no es mínimo).
Sí, las ilustraciones y/o los ejemplos siempre facilitan la comprensión de las definiciones.
Normalmente la distinción es que un ejemplo mínimo sería aquel que no puede hacerse más pequeño tomando un subconjunto de los cortes del ejemplo, mientras que un mínimo es aquel que es lo más pequeño posible en tamaño absoluto.
Por ejemplo, si hablamos de subconjuntos no vacíos de $\{1,2,\dots,n\}$ que suman un número par, entonces $\{2\}$ es un ejemplo mínimo y un ejemplo mínimo, pero $\{1,3\}$ es mínima pero no es un mínimo. Hay ejemplos que son más pequeños que $\{1,3\}$ pero esos ejemplos no están contenidos en $\{1,3\}$ .
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
2 votos
Es la misma diferencia entre la noción de elementos mínimos y la de mínimo en un conjunto proporcionado por una relación de orden, en su caso el conjunto es el conjunto de cortes de aristas y la relación en la inclusión insiemística. En general, mínimo implica mínimo, la viveversa es falsa. Además el mínimo está determinado unívocamente, mientras que en general se pueden tener muchos elementos mínimos
0 votos
@FedericaMaggioni.... gracias por la respuesta oportuna..