Ejercicio práctico | Árboles | Teoría de grafos

Question

Sea $ G $ sea un árbol con 14 vértices de grado 1, y el grado de cada vértice no terminal sea 4 ó 5. Hallar el número de vértices de grado 4 y grado 5.

Mi intento, resumido, es el siguiente: Sea $ x $ es el número de vértices de grado 4, y $ y $ sea el número de vértices de grado 5. Obsérvese que hay $ x + y + 14 $ vértices ( $ x + y + 13 $ bordes, ya que $ G $ es un árbol), entonces $ 4x + 5y + 1 (14) = 2x + 2y + 26 $ aplicando el lema del apretón de manos (la suma sobre todos los vértices de los grados es dos veces el número de aristas). Pero la solución a esto es $x = - \frac{3}{2} y + 6$ . No sé si está bien o qué estoy haciendo mal.

Answer 1

Ibas por buen camino.

En $$4x + 5y + 14 = 2x + 2y + 26$$ obtenemos $$ 2x+3y=12 $$ De ello se deduce que $y$ es par y como máximo $4$ Por lo tanto $$ (x,y)\in\bigl\{(0,4),\;(3,2),\;(6,0)\bigr\} $$ Como mostraremos, todos $3$ de estos pares potenciales $(x,y)$ son, en fsct, posibles.

La siguiente imagen muestra un ejemplo con $(x,y)=(0,4)$ .

Y la imagen de abajo muestra un ejemplo con $(x,y)=(3,2)$ .

Por último, la siguiente imagen muestra un ejemplo con $(x,y)=(6,0)$ .

De este modo, según la reivindicación, cada uno de los pares $$ (x,y)=(0,4),\qquad(x,y)=(3,2),\qquad(x,y)=(6,0) $$ puede hacerse realidad.

Answer 2

Lo que ha hecho hasta ahora es correcto. Ahora bien, como $x\geq0$ tenemos $$6-\frac32y\geq0\implies y\leq4$$ También, $x$ es un número entero, por lo que $y$ debe ser par. Esto da las soluciones $$y=4,\ x=0\\y=2,\ x=3\\y=0,\ x=6$$

Estas son las únicas posibilidades. Debemos investigar si realmente existe algún árbol de este tipo. Obsérvese que el subgrafo inducido por los nodos no terminales debe ser un árbol, ya que en el grafo original, si todos los vecinos de un nodo no terminal tuvieran grado $1$ el gráfico no estaría conectado. Una vez que tenemos este árbol inducido, y los grados de los vértices en el grafo original, el grafo original está determinado, porque sólo tenemos que añadir suficientes nodos terminales para que los grados de los vértices alcancen el valor requerido.

Eso no está muy dicho, lo sé, pero con ejemplos quedará claro, espero. Utilizaré $F$ un vértice de grado cuatro, y $V$ (Romano $5$ ) para un vértice de grado $5$ . Utilizaré un guión (-) para indicar una arista en el subárbol inducido.

En el caso $y=4,\ x=0$ tenemos el subgrafo inducido $V-V-V-V$ . Dos de los vértices tienen grado $1$ en el subárbol, así que añadiremos $4$ vértices terminales a cada uno de ellos. Los otros dos vértices tienen grado $2$ en el subárbol, y añadiremos $3$ vértices terminales a cada uno. Esto da $14$ vértices terminales, según sea necesario.

En el caso $y=2,\ x=3$ podemos utilizar $F-V-F-V-F$ como subárbol. Añadiremos $3$ vértices terminales a cada nodo excepto al $f$ en el centro, donde añadimos $2$ .

En el caso $y=0,\ x=6$ el subárbol $F-F-F-F-F-F$ obras. Añadimos $3$ vértices terminales a los nodos de los extremos, y $2$ al otro $4$ nodos.

En realidad, un poco de reflexión muestra que, siempre que el subgrafo inducido de $F$ y $V$ los nodos forman un árbol $T$ y no hay $F$ nodo de grado superior a $4$ en $T$ ni un $V$ nodo de grado superior a $%$ y, a continuación, rellenando los nodos terminales como se ha indicado anteriormente, se obtendrá un árbol adecuado. Por tanto, si queremos, podemos enumerar todas las soluciones.

Answer 3

El grafo más pequeño tiene dos vértices de grado 5 y uno de grado 4.
Los grafos más grandes con 14 vértices terminales son numéricos.