Dado un grafo $G(V,E)$, ¿cuál es el máximo número de triángulos que este gráfico puede tener en términos de $|E|$?
Sé que hay un triángulo listado de algoritmo , que enumera todos los triángulos en $O(|E|^{3/2})$, pero tengo que demostrar que el número de triángulos en realidad es $O(|E|^{3/2})$. Alguien me puede ayudar? Cualquier estrictos obligado también es apreciado, pero necesito que se basa en el $E$.
Hasta el momento, se me ocurrió una prueba a mí mismo, pero otros pueden ayudar a verificar esta prueba:
Lema. Dado un grafo $G(V,E)$, el número de triángulos es $O(|E|^{1.5})$.
Prueba. Para cada nodo $v$, nos vamos a denotar por $A(v)$ el conjunto $\{u \in N(v), d(u) \geq d(v)\}$; este conjunto contiene sólo los vecinos de $v$ cuyo grado no inferior al grado de $v$ sí.
Sin pérdida de generalidad, vamos a considerar cada triángulo $\Delta_{uvw}$ tal que $d(u) \leq d(v) \leq d(w)$ donde $d(v)$ es el grado del nodo $v$$G$. Entonces uno se puede descubrir $\Delta_{uvw}$ mediante la comprobación de que $w$$A(u) \cap A(v)$.
Por lo tanto, podemos afirmar que el conjunto de los triángulos es $T=\{\Delta_{uvw} | (u,v) \in E, w \in A(u) \cap A(v)\}$. Por lo tanto, sólo tenemos que probar que para cada borde de la $(u,v) \in E$, $|A(u)|$ $|A(v)|$ ambos $O(\sqrt{|E|})$.
Supongamos $u$ $\omega(\sqrt{|E|})$ estos vecinos en $A(u)$. Dado que el grado de todos ellos es igual, al menos, el grado de $u$, el número total de aristas convertido $\omega(|E|)$ lo cual es una contradicción.
Así que podemos afirmar que $|T| \in O(|E|^{1.5})$.
Estoy bastante seguro de que la prueba pueda funcionar, pero aquí hay una alternativa.
Deje $t(e)$ ser el máximo número de triángulos en un gráfico con $e$ bordes.
He estado tratando de conseguir exacta de los límites en $t(e)$, pero fracasó miserablemente. Así que me fui en términos de los Grandes-O la notación (tuve que salir de mi vieja libros de texto para obtener algo que se relaciona con las funciones lisas - si nunca te has encontrado con estos sugiero Brassard Y Bratley).
Queremos $t(e) \in O(e^{1.5})$.
Como usted puede saber, si $e = {n \choose 2}$ algunos $n$, el gráfico con la mayoría de los triángulos es el grafo completo en $n$ vértices, los cuales ha $O(e^{1.5})$ triángulos. Así que podemos decir que hay un $c$ tal que $t(e) \leq ce^{1.5}$ siempre $e = {n \choose 2}$ algunos $n$.
La problemática de los valores de $e$ son los en-entre el binomio valores, es decir,${ n - 1 \choose 2} < e < {n \choose 2}$. Quiero mostrar estos valores de $e$ "encajar" $O(e^{1.5})$. Deje $\delta$ ser tal que $e + \delta = {n \choose 2}$. Podemos suponer $\delta \leq e$. Eso es debido a que $e + e > 2{n-1 \choose 2} > {n \choose 2}$ siempre $n > 4$, por lo que un $\delta > e$ nunca serán requeridos para alcanzar el siguiente binomio (por lo suficientemente grande como $e$). He aquí un perezoso de verificación.
Una última cosa a tener en cuenta : $t$ es no decreciente. Es decir, $t(e) \leq t(e + 1)$, debido a que el máximo número de triángulos se puede hacer no se puede disminuir mediante la adición de un borde.
Así que aquí es lo que sucede :
$$t(e) \leq t(e + \delta) \leq c(e + \delta)^{1.5} \leq c(2e)^{1.5} = 2^{1.5}ce^{1.5}$$
La primera desigualdad debido a $t$ es no decreciente, la segunda porque de $e + \delta = {n \choose 2}$, y el tercero porque el $\delta \leq e$ y el "no-decreasingness".
Por lo $t(e) \leq de^{1.5}$ con la constante $d = 2^{1.5}c$, y por lo tanto $t(e) \in O(e^{1.5})$.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
