Examen de Matemática Discreta UAB 2023 · Primer Parcial 2023-2024

Exercici 1. Repartiment d'estudiants en habitacions

A la vila universitària cal allotjar 9 estudiants distribuint-los entre tres habitacions retolades com a 1, 2 i 3:

a.

De quantes maneres diferents es poden allotjar els 9 estudiants si no s'imposa cap mena de condició o restricció?

b.

De quantes formes es poden repartir si s'estableix que a l'habitació 1 hi vagin exactament 4 estudiants, a l'habitació 2 n'hi vagin 2 i a l'habitació 3 n'hi vagin 3?

Exercici 2. Arbres no isomorfs d'ordre 16

Determineu el nombre d'arbres no isomorfs d'ordre 16 que compleixen que tots els seus vèrtexs tenen grau $g_1 > 3$ o bé grau $g_2 = 1$. Per a cadascun dels casos que es puguin donar, indiqueu quants vèrtexs hi ha de grau $g_1$.

Casos possibles (ordenats de menor a major grau $g_1$):

Exercici 3. Seqüències gràfiques d'un graf connex

Quantes seqüències no ordenades de xifres del tipus $x, x, x, y, y, y, 3$ (amb $x > 3$, $x > y$ i $y$ parell) hi ha que siguin la seqüència de graus d'un graf connex?

1a parella: $x =$ $y =$

2a parella: $x =$ $y =$

Exercici 4. Algorisme de Floyd

A partir de la matriu de pesos o d'adjacència d'un graf dirigit ponderat $G = (V, E)$:

a.

Expliqueu el funcionament bàsic de l'algorisme de Floyd-Warshall per trobar els camins mínims entre tots els parells de vèrtexs.

b.

Descriviu com s'actualitza la matriu de distàncies $D^{(k)}$ en cada iteració $k$ i com es pot detectar l'existència de cicles de pes negatiu.

Exercici 5. Algorismes sobre grafs

En relació amb els algorismes clàssics d'optimització sobre grafs (com ara Dijkstra, Kruskal o Prim):

a.

Diferencieu el problema del camí mínim d'origen únic (resoluble mitjançant Dijkstra) del problema de l'arbre d'extensió mínim (resoluble mitjançant Kruskal o Prim).

b.

Expliqueu breument per què l'algorisme de Dijkstra pot fallar si el graf conté arestes amb pesos estrictament negatius.