Qué es la intuición detrás de esta cuestión (teoría de gráfico con aplicaciones, Bondy y Murty Q1.2.9)

Question

Esta es la pregunta 1.2.9 a partir de la teoría de grafos con aplicaciones por Bondy y Murty que estoy trabajando a través de la diversión (este libro está disponible gratuitamente en internet, y se los recomiendo).

Pregunta, estoy trabajando en la parte (a).

Se nos pide a mostrar que $T_{m,n}$, el $m$-partita gráfico en $n$ vértices donde cada parte ha $[n/m]$ o $\{n/m\}$ vértices satisface $$\varepsilon(T_{m,n}) = {n-k \choose 2} + (m-1){k+1 \choose 2} ,$$ donde $\varepsilon(G)$ cuenta el número de bordes de $G$$k = [n/m]$.

Mi planteamiento es el siguiente. Para una completa $m$-partita gráfico de $G$ $n$ vértices tener piezas $V_1, \ldots, V_m$, tenemos que cada vértice $v$$i$$\deg{v} = n - |V_i|$, y $|V_i|$ tales vértices en $V_i$. Entonces $$\varepsilon (G) = \sum\limits_{v\in G} \frac{\deg(v)}{2} = \sum\limits_{i=1}^m |V_i| \frac{n-|V_i|}{2} =\frac{n^2}{2} - \sum\limits_{i=1}^m \frac{|V_i|^2}{2}. $$ Tan lejos y tan bien, creo.

Ahora, si dejamos $n = mk + d$ donde $d \in[0,m)$, y establecer$|V_i| = k+1$$i = 1,\ldots, d$$|V_i| = k $$i = d+1,\ldots, m$, obtenemos $T_{m,n}$. Entonces tenemos $$\varepsilon(T_{m,n}) = \frac{n^2}{2} - \sum\limits_{i=1}^d\frac{(k+1)^2}{2} - \sum\limits_{i=d+1}^m \frac{k^2}{2}= \frac{n^2}{2} -\frac{mk^2}{2} - d\frac{2k+1}{2}. $$

He tratado de hacer álgebra a esta expresión, y también los resultados requeridos pero no me parecen demostrar su igualdad. Así que mi pregunta ahora es la siguiente:

Es mi trabajo hasta ahora de hecho correcta, y si es así, ¿hay una manera fácil de demostrar la igualdad de dos expresiones. Más aún, el resultado se ve como un simple combinatoria de contar el argumento de que debe ser intuitivamente claro, pero yo no lo veo, ¿alguien puede explicar? Muchas gracias!

Answer 1

En primer lugar, para el beneficio de aquellos que no tienen una copia de Bondy Y Murty, me explico que las notaciones $[x]$ $\{x\}$ el valor del entero de piso y de techo de $x,$ hoy en día, generalmente escrita como $\lfloor x\rfloor$ $\lceil x\rceil.$

Deje $V_0,V_1,\dots,V_{m-1}$ ser las partes de la $m$-partita gráfico de $T=T_{m,n}.$ Cada parte ha $k$ o $k+1$ vértices; ya que al menos una parte tiene exactamente $k$ vértices, podemos suponer que la $|V_0|=k.$

Definir una función $f:V\to\{1,2,\dots,k+1\}$, de modo que, para cada una de las $i\in\{0,1,\dots,m-1\},$ la restricción de $f$ $V_i$es un bijection de $V_i$ $\{1,2,\dots,|V_i|\}.$

Para $1\le i\le m-1,$ el número de aristas $xy\in E(T)$ con $x\in V_0$, $y\in V_i,$ y $f(y)\le f(x)$ es igual a $\binom{k+1}2,$ el número de enteros pares de $(r,s)$ $1\le s\le r\le k.$ por lo Tanto, si definimos $E_0=\{xy\in E(T):x\in V_0,\ f(y)\le f(x)\}$ $E_1=\{xy\in E(T):x\in V_0,\ f(x)\lt f(y)\},$ $$|E_0|=(m-1)\binom{k+1}2.\tag1$$

Deje $K$ ser el grafo completo sobre el conjunto de vértices $V\setminus V_0.$ Observar que no hay una correspondencia uno a uno entre el $E_1$ $E(K)\setminus E(T);$ es decir, una arista $xy\in E_1$ con $x\in V_0$, $y\in V_i$, y $f(x)\lt f(y)$ corresponde a la orilla $zy\in E(K)\setminus E(T)$ donde $z\in V_i$ $f(z)=f(x).$ Se sigue que $|E(K)\setminus E(T)|=|E_1|$ y así $$|E(T)\setminus E_0|=|E_1|+|E(K)|-|E(K)\setminus E(T)|=|E(K)|=\binom{n-k}2.\tag2$$ La adición de $(1)$ $(2)$ tenemos $$|E(T)|=\binom{n-k}2+(m-1)\binom{k+1}2.\tag3$$

Answer 2

Aquí es más "talkies" camino a la presente bof la respuesta.

Dentro de cada partita parte (de los vértices), número (etiqueta) de los vértices de $1$ $k$(o $k+1$). Elija uno de los partita partes con $k$ vértices y llamar a $L$ ("más a la izquierda.") Los bordes de $T_{m,n}$ están en exactamente uno de los siguientes tres grupos:

$E$: el conjunto de aristas que no impliquen un vértice de $L$.

$U$ ("up"): el conjunto de aristas de un vértice $v_i$ $L$ a un vértice con la etiqueta inferior o igual a $i$. ("Up" es en realidad "o directamente a través de".)

$D$ ("abajo"): es el conjunto de aristas de un vértice $v_i$ $L$ a un vértice con el sello mayor de $i$.

El número de aristas en $T_{m,n}$$|E|+|U|+|D|$.

El número de aristas en $U$ es más fácil de contar. Hay $k$ opciones para el vértice en $L$, y si el vértice en $L$$v_i$, $(m-1)i$ opciones para el otro vértice, ya que puede ser en cualquiera de las $m-1$ otros partita partes y debe tener la etiqueta inferior o igual a $i$. Así que hay $(m-1)\sum_{i=1}^{k} i=\color{red}{(m-1){k+1\choose2}}$ bordes en $U$.

Ahora considere los bordes en $D$. Cada uno de ellos se conecta un vértice $v_i$ $L$ a un número más alto de vértice en otros lugares. "Reposicionar" la $v_i$ final de cada uno de estos fuera de la $L$ y a los vértices etiquetados $i$ en el mismo partita conjunto como el final de la arista no en $L$ (es decir, en la partita parte en la "mano derecha" de finales de los bordes). Siempre hay un vértice, porque cada partita tiene al menos tantos vértices como $L$, y el resultado se conecta distintos vértices debido a que las etiquetas en los vértices de un borde en $D$ nunca son los mismos; $D$ significa "estrictamente". Llame a la resultante conjunto de aristas $D'$. El reposicionamiento de los bordes es uno-a-uno, por lo $|D'|=|D|$.

Es fácil ver que $D'$ es disjunta de a $E$ y $D'\cup E$ es el conjunto de aristas para el grafo completo sobre el conjunto de vértices de $T_{m,n}\setminus L$. Luego hay $\color\red{{n-k}\choose2}$ bordes en $D'\cup E$, por lo tanto, en $D$ $E$ juntos.