ej. 3 2do parcial 6/18

ej. 3 2do parcial 6/18

de Marcela Pintos Nogues -
Número de respuestas: 2

Hola buenas tardes, tengo una duda del ejercicio 3 del 2do parcial de junio del 2018. Piden hallar la cantidad de arboles no isomorfos con 7 vértices y que además tengan máximo grado 3.  En la solución plantean según la cantidad de vértices de grado 3, pero no tomaron en cuenta la posibilidad de que no exista ninguno, no estaría faltando contar el árbol p7?  adjunto foto con la solución y los grafos que pusieron como respuesta

En respuesta a Marcela Pintos Nogues

Re: ej. 3 2do parcial 6/18

de Luis Stábile -
Hola Marcela,

En el ejercicio se dice que el grado máximo es 3 por lo que por lo menos debe haber un vértice en esas condiciones. Por esa razón P_7 no fue considerado.

Que el grado máximo sea 3 significa que existe al menos un vértice de grado 3. Distinto sería que pidan los árboles de 7 vértices con a lo sumo grado 3. Ese "a lo sumo" implica que gr(v) \leq 3 \forall v \in V, con T=(V,E), árbol. En este caso, P_7 debería tenerse en cuenta.

Saludos,
Luis.