Glosario

Seleccione una de las palabras clave de la izquierda ...

Gráficos y RedesApretones de manos y citas

Tiempo de leer: ~15 min
Esta página ha sido traducida automáticamente y puede contener errores. ¡Póngase en contacto si desea ayudarnos a revisar las traducciones!

Has sido invitado a una maravillosa fiesta de cumpleaños con tus amigos. Incluyéndote a ti y al anfitrión, hay ${hnd} personas presentes

Por la noche, cuando los invitados se preparan para partir, todos se dan la mano con todos los demás. ¿Cuántos apretones de manos hay en total?

Podemos representar los apretones de manos usando un gráfico: cada persona es , y cada apretón de manos es

Ahora es fácil contar el número de aristas en el gráfico. Encontramos que allí con ${hnd} gente, hay ${hnd*(hnd-1)/2} apretones de manos

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 .

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 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×n12 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?

En este caso, el gráfico correspondiente consta de dos conjuntos separados de vértices. Cada vértice está conectado a todos los vértices en conjunto, pero ninguno de los vértices en conjunto . Los gráficos que tienen este diseño se denominan gráficos bipartitos .

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