Ejercicios de Relacions, conceptes bàsics de grafs i seqüències de graus (grafs i arbres)

5 ejercicios de Relacions, conceptes bàsics de grafs i seqüències de graus (grafs i arbres) que han salido en los exámenes de Matemática Discreta de la UAB…

Exercici 2.a - Seqüències gràfiques · 2025

Exercici 2.a: Per a la seqüència x, x, x, y, y, y, y, y amb 0 < y < x <= 5, determinar per a quins valors de x i y la seqüència és gràfica.

Exercici 2.b - Condicions d'arbre · 2025

Exercici 2.b: Identificar per a quins valors de x i y la seqüència (x, x, x, y, y, y, y, y) correspon als graus dels vèrtexs d'un arbre, i determinar si existeix algun graf que no sigui un arbre amb aquesta mateixa seqüència de graus, justificant la resposta.

Exercici 3 · 2025

Sigui A={1,2,3,4,5} i la relació d'ordre estricte R={(a,b) | a < b}. Es demana dibuixar el graf dirigit G(A, R), dibuixar el seu complementari i justificar quina relació binària genera el graf complementari.

Exercici 2 · 2023

Determineu el nombre d'arbres no isomorfs d'ordre 16 que compleixen que tots els seus vèrtexs tenen grau g1 > 3 o bé g2 = 1. Indiqueu quants vèrtexs hi ha de grau g1 en cada cas.

Exercici 3 · 2023

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?

Otros temas de Matemática Discreta

Combinatòria i relacions

• Combinatòria i recompte · 2 problemas · 35 % de que salga

Grafs, arbres i recorreguts

• 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
• Coloració de grafs i polinomi cromàtic · 4 problemas · 45 % de que salga