Ejercicios de Coloració de grafs i polinomi cromàtic
4 ejercicios de Coloració de grafs i polinomi cromàtic que han salido en los exámenes de Matemática Discreta de la UAB (Grado en Ingeniería Informática)…
Exercici 2 · Juny 2026
Exercici 2. a. Sigui G = T ∪ K_5 ∪ {v_1, v_2} on T té 6 vèrtexs. 1) Polinomi cromàtic de T i de K_5. 2) Polinomi cromàtic de G. 3) Nombre cromàtic de G. 4) Maneres d'acolorir G amb χ(G) colors. b. Donat f(D, t) = t^13 - 11t^12 + at^11 - 131t^10 + 205t^9 - 201t^8 + 121t^7 - 41t^6 + 6t^5. 1) Vèrtexs, arestes i…
Pregunta 2 · 2024
Determineu el polinomi cromàtic P(G, t) per a: a) un graf de 4 vèrtexs (triangle K_3 amb aresta penjant); b) un graf de 5 vèrtexs (K_4 amb aresta penjant); c) el graf que s'obté en afegir un nou vèrtex connectat mitjançant una aresta a K_n; d) Per al graf de l'apartat a: 1. De quantes maneres es pot pintar amb 5…
Pregunta 2 · 2023
a) Donat el polinomi cromàtic f(G,t) = t^9 - 6t^8 + 14t^7 - 16t^6 + at^5 - bt^4: 1. Determineu |V|, |E| i components connexos. 2. Trobeu a i b si χ(G) > 2. b) Calculeu el polinomi cromàtic i deduïu el nombre cromàtic del graf de la figura.
Ejercicio 2 · Juny 2022
Dado f(G,t) = t^5 - 3t^4 - at^3 + t^2, determina el número de vértices, componentes conexas, la constante a y el número cromático de G. Además, deduce el polinomio cromático de un bosque de orden n con k componentes en función de n y k.
Otros temas de Matemática Discreta
Combinatòria i relacions
- Combinatòria i recompte · 2 problemas · 35 % de que salga
Grafs, arbres i recorreguts
- Relacions, conceptes bàsics de grafs i seqüències de graus (grafs i arbres) · 5 problemas · 35 % de que salga
- Recorreguts BFS i DFS · 3 problemas · 50 % de que salga
Camins, circuits i rutes
- Grafs ponderats: arbre generador mínim i camins mínims (Kruskal, Prim, Dijkstra) · 5 problemas · 45 % de que salga
- Grafs eulerians i hamiltonians · 4 problemas · 45 % de que salga
- Optimització de rutes: carter xinès, viatjant de comerç i complexitat · 8 problemas · 45 % de que salga
Planaritat i coloració
- Grafs planars i fórmula d'Euler · 4 problemas · 45 % de que salga