A continuación tengo algunas pruebas que me gustaría que me revisaran. Gracias.
a. Demuestra cada árbol con vértices tiene exactamente bordes
Solución:
queremos mostrar que Usamos el proceso de poda de árboles (eliminación de un vértice de grado del árbol junto con la arista que se produce en ese vértice). Este proceso está bien definido porque eliminar un vértice y una arista aún nos deja con un árbol, ya que los árboles no contienen ciclos y eliminar el par arista/vértice no agrega ningún ciclo al árbol.
Todo árbol con más de un vértice se puede podar porque todo árbol con dos o más vértices tiene al menos dos vértices de grado (Considere un camino simple más largo en el árbol cuya longitud es El grado de sus extremos es como máximo De lo contrario ya no es el camino simple más largo).
La diferencia permanece constante durante todo el proceso de poda. En algún momento, el árbol se reducirá a un solo vértice para que es Desde la diferencia permanece constante durante toda la poda, podemos decir que por un árbol
b. en un bosque con vértices y componentes, el número de aristas es
Solución:
Por (a) arriba, para cada componente árbol significado es constante en cada componente. Puesto que hay componentes y entonces el número de aristas es
C. Supongamos que un gráfico tiene vértices, bordes, y no contiene ciclos. Entonces, ¿cuántas componentes contiene el gráfico?
Solución:
Este gráfico no tiene ciclos, por lo que debe ser un árbol, pero un árbol debe contener exactamente bordes si es el número de vértices. Por lo tanto, estamos tratando con un bosque. Por (b) arriba, el número de componentes es
d. Supongamos que un gráfico contiene un número igual de vértices y aristas. Demostrar que la gráfica debe contener al menos un ciclo.
Solución:
Un grafo con igual número de vértices y aristas no es un árbol por (a) arriba, sino quizás un bosque. Entonces este bosque tiene componentes, lo que significa que este gráfico tampoco es un bosque. Por lo tanto, este gráfico debe contener al menos un ciclo.
Si no me equivoco, sus ideas son correctas, aunque su redacción a veces se siente un poco torpe. Señalaré solo las fallas en su lógica; Te animo a que revises tu redacción tú mismo.
a. [...] (Considere un camino simple más largo en el árbol cuya longitud es . El grado de sus extremos es como máximo . De lo contrario ya no es el camino simple más largo). [...]
No entiendo cómo esto prueba el hecho de que cualquier árbol con más de un vértice tiene al menos dos vértices de grado 1. ¿Estás diciendo que el camino simple más largo tiene una longitud de 1?
C. Este gráfico no tiene ciclos por lo que debe ser un árbol [...]
Esto no es correcto. No digas cosas que no son correctas.
d. [...] Entonces este bosque tiene 0 componentes, lo que significa que este gráfico tampoco es un bosque. [...]
No estoy seguro de qué definición aprendiste, pero me parece que el gráfico vacío ( ) es un grafo con el mismo número de vértices y aristas. Es el único gráfico con componentes, y es trivialmente un bosque. Al contrario de lo que la pregunta le haría creer, no contiene un ciclo.
Supongo que se supone que el vértice establecido en su definición de gráficos no está vacío. En ese caso, la frase "este gráfico no es un bosque" es inadecuada. Una mejor manera de decirlo: "esto no es un gráfico en absoluto". (Después de todo, una vez que reconocemos que es un gráfico, definitivamente es un bosque). Es cierto que estoy siendo quisquilloso aquí, ¡pero es mi opinión que los casos de esquina sí importan!