¿por qué un grafo completo ha $\frac{n(n-1)}{2}$ bordes?

Question

estoy estudiando los gráficos en el algoritmo de complejidad y, (pero yo no soy muy buena en matemáticas) como en el título, ¿por qué un grafo completo ha $\frac{n(n-1)}{2}$ bordes? y cómo esto está relacionado con la combinatoria?

Answer 1

Una simple respuesta sin binomios: Un grafo completo significa que cada vértice está conectado con todos los otros vértices. Si usted toma un vértice de la gráfica, por lo tanto, tenemos $n-1$ bordes salientes de ese particular vértice.

Ahora, usted tiene $n$ vértices en total, así que usted puede estar tentado a decir que hay $n(n-1)$ bordes en total, $n-1$ por cada vértice en el gráfico. Pero este método cuenta cada borde dos veces, porque cada borde que va de un vértice es un borde que va en otro vértice. Por lo tanto, usted tiene que dividir el resultado por 2. Esto te deja con $n(n-1)/2$.

Answer 2

Un grafo completo tiene una arista entre dos vértices. Usted puede obtener una ventaja mediante la selección de cualquiera de los dos vértices.

Así que si hay $n$ vértices, hay $n$ elegir $2$ = ${n \choose 2} = n(n-1)/2$ los bordes.

¿Eso ayuda?

Answer 3

$\frac{n(n-1)}{2} = \binom{n}{2}$ es el número de formas de elegir los 2 desordenada de elementos de n artículos distintos.

En su caso, usted realmente desea contar cuántos desordenada par de vértices que tienen, ya que cada pareja puede ser exactamente uno de los bordes (en un simple gráfico completo).

supongamos $(v,u)$ es un borde, luego v puede ser cualquiera de los vértices en la gráfica - usted tiene n opciones para esto. u puede ser cualquier vértice que no es v, entonces tiene (n-1) opciones para esto. el problema es que contaba cada borde dos veces - una vez en $(u,v)$ y un tiempo como $(v,u)$, por lo que es necesario dividir por dos, y luego de obtener que ha $\frac {n(n-1)}{2}$ bordes en un simple gráfico.