miércoles, 14 de junio de 2017

Martes de combi (en miércoles otra vez)

Hola chicos.

Una disculpa nuevamente por el desfase en la publicación.

Determina el mínimo y máximo número de triángulos orientados (triángulos en los que las aristas forman un ciclo siguiendo el orden de las flechas) que pueden encontrarse en una gráfica completa dirigida con n vértices.

1 comentario:

Ariel dijo...

El mínimo es siempre $0$. Numeramos los vértices $1, 2, \dots, n$ y definimos que si $a$ es menor que $b$ entonces la arista entre $a$ y $b$ va en dirección $a \rightarrow b$. Esto claramente no tiene triángulos.

Ahora, para encontrar el máximo, acotamos el número de tripletas de vértices $(a, b, c)$ tales que las aristas $a \rightarrow b$ y $b \rightarrow c$ existen. Para $\{a, b, c\}$ dados hay tres tripletas si estos tres vértices forman un triángulo dirigido y una de lo contrario. Por otro lado para cada vértice $v$ el número de tripletas $(a, b, c)$ descritas anteriormente que tienen $b = v$ es igual a

$$d^{+}(v)d^{-}(v) \leq \left\lfloor \frac{n - 1}{2} \right\rfloor \left\lceil \frac{n - 1}{2} \right\rceil$$

Donde $d^{+}(v)$ y $d^{-}(v)$ denotan el exgrado y el ingrado de $v$. De aquí tenemos la desigualdad:

$$3T + \left(\binom{n}{3} - T\right) \leq n\left\lfloor \frac{n - 1}{2} \right\rfloor \left\lceil \frac{n - 1}{2} \right\rceil$$

$$\implies$$

$$T \leq \frac{n\left\lfloor \frac{n - 1}{2} \right\rfloor \left\lceil \frac{n - 1}{2} \right\rceil - \binom{n}{3}}{2} $$

Para ver que este número es alcanzable basta encontrar un acomodo en el que

$$d^{+}(v)d^{-}(v) = \left\lfloor \frac{n - 1}{2} \right\rfloor \left\lceil \frac{n - 1}{2} \right\rceil$$

Para todo vértice $v$. Numeramos los vértices $1, 2, \dots, n$. Si $n = 2k + 1$ entonces del vértice $i$ saldrán aristas a los vértices $i + 1, i + 2, \dots, i + k$ módulo $n$ para cada $i$. Si $n = 2k$ entonces de $i$ salen aristas a $i + 1, i + 2, \dots + i + k$ si $1 \leq i \leq k$ y únicamente salen a $i + 1, i + 2, \dots, i + k - 1$ si $k + 1 \leq i \leq 2k$. En ambos casos es fácil verificar que se cumple la igualdad deseada y que la construcción es consistente (es decir que no existen tanto $u \rightarrow v$ como $v \rightarrow u$).

Publicar un comentario