¿Cuál es el más grande transitoriamente reducen gráfico acíclico conectado en $n$ vértices, cada $n$?
¿Cuántos bordes $e$ tiene? ¿Cómo crece en función de $e$ $n$? ¿Más rápido que $n^2/4$?
Respuestas
¿Demasiados anuncios?
Desde el transitivamente reducción de grafos $G$ es acíclico, hay una correspondiente grafo simple gráfico de $G'$, que puede estar formado por ignorar la dirección de la orilla. El número de aristas en $G$ es el mismo que el número de aristas en $G'$.
Para $G$ a ser transitivamente reducido, una condición necesaria es que la $G'$ no debe contener ningún triángulos.
Es bien sabido (Turan/Repisa de la chimenea del teorema) que cualquier simple grafo no dirigido en $n$ vértices y más de $n^2/4$ bordes con un triángulo.
También es conocido que el grafo no dirigido en $n$ vértices con el máximo de los bordes y no triángulos es la completa bipartito gráfico de $K_{[n/2],[n/2]}$ (por ejemplo, echa un vistazo: http://books.google.com/books?id=SbZKSZ-1qrwC&pg=PA28, ejercicio 4)
A partir de sus comentarios, parece que has encontrado un $G$ cuyo correspondiente $G'$$K_{[n/2],[n/2]}$, por lo que lo demuestra.
Manuel Ferreria
Puntos
176
Bipartita de gráfico es el más grande.
Prueba: Supongamos que G es un grafo, v es el vértice. Deje $L(v)$ es igual a la máxima longitud de una trayectoria que se inicia en $v$. Deje $L(G)=max_{v\in G} L(v)$. Si $L(G)=1$, el grafo es bipartito. A fin de demostrar, que el bipartito gráfico es el más grande, voy a probar, que para cualquier gráfico de $G$ tal que $L(G)>1$ no existe gráfico del $H$ con el mismo número de vértices y aristas, de tal manera que $L(G)>L(H)$.
Tenga en cuenta, que cualquier vértice con $L(v)=0$ sólo tiene conexiones entrantes. Estas conexiones son de vértices w con $L(w)=1$. Vamos a hacer gráfico de $H$ en dos pasos.
Paso 1. Quitar todos los vértices con $L(v)=0$, y los bordes. Tenga en cuenta que $L(G)$ ha disminuido.
Paso 2. Agregar todos los vértices, eliminado en el paso 1. Agregar bordes, eliminado en el paso 1, pero a la inversa de su dirección. Llame a la nueva gráfica de $H$. Nota, que tiene el mismo número de vértices y aristas y $L(H) < L(G)$.
