Autor Tema: Partición de grafo con al menos la mitad de aristas de corte

0 Usuarios y 1 Visitante están viendo este tema.

21 Noviembre, 2019, 03:51 am
Leído 857 veces

Julio_fmat

  • $$\Large \color{red}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 2,398
  • País: cl
  • Karma: +0/-0
  • Sexo: Masculino
    • Fmat
Demuestre que todo grafo tiene un corte que contiene al menos la mitad de las aristas del grafo. En otras palabras, demuestre que todo grafo \( G \) tiene un subconjunto de vertices \( X \) tal que \( d(X)\ge \dfrac{m(G)}{2}. \)
"Haz de las Matemáticas tu pasión".

21 Noviembre, 2019, 01:14 pm
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,123
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Demuestre que todo grafo tiene un corte que contiene al menos la mitad de las aristas del grafo. En otras palabras, demuestre que todo grafo \( G \) tiene un subconjunto de vertices \( X \) tal que \( d(X)\ge \dfrac{m(G)}{2}. \)

Tenemos que probar que hay una partición de los vértices del grafo \( A=X \) y   de manera que el número de aristas que unen vértices de \( A \) con vértices de \( B \) es al menos el número de aristas totales del grado.

Considera el siguiente algoritmo. Comenzamos tomando los conjuntos \( A \) y \( B \) vacíos.

Supongamos que numeramos los vértices \( v_1,v_2,\ldots,v_n \). Comenzando con el primero y hasta llegar al último realizamos este proceso:

Si el vértice \( v_i \) tiene más aristas que lo unen con \( A \) que aristas que lo unen con \( B \), se lo añadimos a \( B \). En otro caso se lo añadimos a \( A \).


Veamos que al completar el proceso hemos obtenido una partición cumpliendo lo pedido.

Para cada vértice \( v_i \) sean \( d_i \) el número de vértices \( v_j \) con \( j<i \) unidos por \( v_i \) con una arista. Se cumple que:

\( \displaystyle\sum_{i=1}^n{}d_i=m(G) \)

Ahora para cada vértice \( v_i \) en el momento de decidir según el algoritmo indicado si va al conjunto \( A \) o al \( B \) hay en total \( d_i \) aristas unidas a vértices que ya están en alguno de los dos conjuntos. Dado que decidimos unirlo al conjunto \( A \) o \( B \) de manera que halla el mayor número posible de aristas que lo unen al otro conjunto, al menos hay \( d_i/2 \) aristas que unen a \( v \) con un vértice del otro conjunto.

Por tanto el número total de aristas que unen vértices de \( A \) con vértices de \( B \) cumple:

\( d(X)\geq \displaystyle\sum_{i=1}^n{}d_i/2=m(G)/2 \)

Saludos.