Gráficos y RedesApretones de manos y citas

En lugar de contar todos los bordes en gráficos grandes, también podríamos tratar de encontrar una fórmula simple que nos diga el resultado para cualquier número de invitados.

Cada una de las ${n} la gente en la fiesta se da la mano con ${n-1} otros. Lo que hace ${n} × ${n-1} = ${n×(n-1)} apretones de manos en total. Para n personas, la cantidad de apretones de manos sería n×n−1n×n+1n2 .

Lamentablemente, esta respuesta no es del todo correcta. Date cuenta cómo las dos primeras entradas en la fila superior en realidad son lo mismo, solo volteado.

De hecho, hemos contado cada apretón de manos dos veces una vez tres veces una vez para cada una de las dos personas involucradas. Esto significa que la cantidad correcta de apretones de manos para ${n} invitados es ${n}×${n-1}2=${n*(n-1)/2} .

Los gráficos de apretón de manos son especiales porque cada vértice está conectado a cualquier otro vértice. Los gráficos con esta propiedad se llaman gráficos completos . El gráfico completo con 4 vértices a menudo se abrevia como K4 , el gráfico completo con 5 vértices se conoce como K5 , y así.

Acabamos de mostrar que un gráfico completo con n vértices Kn , tiene n×n−12 bordes

En un día diferente, estás invitado a un evento de citas rápidas para ${m} chicos y ${f} muchachas. Hay muchas mesas pequeñas y cada niño pasa 5 minutos con cada una de las niñas. ¿Cuántas "fechas" individuales hay en total?

El gráfico bipartito con dos conjuntos de tamaño x e y a menudo se escribe como Kx,y . Tiene x×yx+y2x−y bordes, lo que significa que en el ejemplo anterior hay ${m} × ${f} = ${m×f} fechas.