Diskrétní matematika Vypracovali Věta o skóre grafu • Nechť D = (d^ d2,dn) je posloupnost přirozených čísel. • Předpokládejme, že d1 < d2 < ... < dn a označme symbolem D' (d/, d2', ... d^'), kde dj'= dj proi n — dn • Potom D je skóre grafu, právě když D' je skóre grafu. Zadání a řešení příkladu • Nakreslete graf se skórem (8, 8, 5, 5, 5, 5, 2, 2, 1, 1, 1, 1) • 1) Po přerovnání: (1,1,1,1, 2, 2, 5, 5, 5, 5, 8, 8) • 2) (n-dn-l) = (12-8-1) = 3 => (1, 1, 1, 0, 1, 1, 4, 4, 4, 4, 7) • Po přerovnání: (0,1,1,1,1,1, 4, 4, 4, 4, 7) • 3) (n-dn-l) = (11-7-1) = 3 => (0, 1, 1, 0, 0, 0, 3, 3, 3, 3) • Po přerovnání: (0, 0, 0, 0,1,1, 3, 3, 3, 3) • 4) (O, O, O, O, 1, 1, 3, 3, 3, 3) • (n-dn-l) = (10-3-1) = 6 • (0, 0, 0, 0,1,1, 2, 2, 2) • 5) (n-dn-l) = (9-2-1) = 6 • (0, 0, 0, 0,1,1,1,1) Graf č. 1 • (O, O, O, 0,1,1,1,1) O o-o o o Graf č. 2 • (O, O, O, 0,1,1, 2, 2, 2) Graf č. 3 • (O, O, O, 0,1,1, 3, 3, 3, 3) Graf č. 4 • (0,1,1,1,1,1, 4, 4, 4, 4, 7) o-o Graf č. 5 - výsledný graf • (1,1,1,1, 2, 2, 5, 5, 5, 5, 8, 8)