Exercici 2.b - Condicions d'arbre · Matemática Discreta UAB 2025
Tema: Relacions, conceptes bàsics de grafs i seqüències de graus (grafs i arbres) · Del examen Examen Parcial 1 – Matemàtica Discreta (Curs 2025-2026) (2025)
Enunciado
Considerem la seqüència de nombres enters amb la restricció .
b.
Identifiqueu per a quins valors de la seqüència correspon als graus dels vèrtexs d'un arbre.
Existeix algun graf que no sigui un arbre i que tingui exactament aquesta mateixa seqüència de graus? Justifiqueu la resposta.
Sí
No
Solución
Según los criterios oficiales de corrección
Valor de perquè la seqüència correspongui als graus dels vèrtexs d'un arbre
Solución: 3
Valor de perquè la seqüència correspongui als graus dels vèrtexs d'un arbre
Solución: 1
Existeix algun graf que no sigui un arbre i que tingui exactament aquesta mateixa seqüència de graus?
Solución: Sí
Justifiqueu si existeix algun graf que no sigui un arbre i que tingui exactament aquesta mateixa seqüència de graus
Solución: Sí que existeix. Perquè no sigui un arbre havent de tenir 7 arestes i 8 vèrtexs, el graf ha de ser desconnectat i contenir algun cicle. Per exemple, podem construir un graf amb dues components connexes: una component formada per un cicle de 3 vèrtexs cadascun connectat a una fulla (6 vèrtexs: tres de grau 3 i tres de grau 1, que conté un cicle de longitud 3) i una altra component formada per una aresta aïllada entre els dos vèrtexs restants (2 vèrtexs de grau 1). Aquest graf té la seqüència (3, 3, 3, 1, 1, 1, 1, 1) i no és un arbre.
La explicación paso a paso, hecha con IA, es Premium. Premium
Resuélvelo aquí mismo: corrección automática, pistas y solución paso a paso.
‹ Exercici 2.a - Seqüències gràfiques · 2025 · Exercici 3 · 2025 ›