Spausdinimo lange pasirinkite „Išsaugoti kaip PDF“, kad nuosavą kopiją išsaugotumėte savo įrenginyje.
1Formulės ir metodai
Grafų teorija
Rankų paspaudimo lema
Σ deg(v) = 2|E|
Pilnieji grafai
|E(Kn)| = n(n − 1)/2, |E(Km,n)| = m·n
Reguliarusis grafas
|E| = n·k/2
Medis ir miškas
|E| = n − 1, |E| = n − c
Medžio lapai
L = 2 + Σ (deg(v) − 2) over deg(v) ≥ 3
Oileris
ciklas: visų viršūnių laipsniai lyginiai; kelias: lygiai 2 nelyginio laipsnio viršūnės
Hamiltono ciklai grafe Kn
(n − 1)!/2
Dijkstros atnaujinimas
d(v) = min(d(v), d(u) + w(u, v))
L ilgio maršrutai
(Mᴸ)ij
Metodas
Užrašykite kiekvienos viršūnės laipsnį; laipsnių suma lygi dvigubam briaunų skaičiui.
Oilerio uždaviniuose patikrinkite, ar grafas jungus, ir suskaičiuokite nelyginio laipsnio viršūnes.
Medžiams naudokite n − 1 briaunų ir rankų paspaudimo lemą.
Dijkstros algoritme laikykite preliminarių atstumų lentelę ir kiekviename etape užfiksuokite mažiausio atstumo dar neužfiksuotą viršūnę.
Minimaliam karkasiniam medžiui surikiuokite briaunas pagal svorį ir praleiskite kiekvieną briauną, uždarančią ciklą (Kruskalis), arba auginkite vieną medį iš pradinės viršūnės (Primas).
2Uždaviniai
1.Algoritmai ir sudėtingumasVidutinis
Kuri godžioji taisyklė veiklų atrankos uždavinyje visada duoda didžiausią nepersidengiančių veiklų skaičių?
APirmiausia pasirinkti trumpiausią veiklą
BPasirinkti anksčiausiai prasidedančią veiklą
CPirmiausia pasirinkti veiklą, turinčią mažiausiai persidengimų, tada kartoti su suderinamomis
DPasirinkti anksčiausiai pasibaigiančią veiklą, tada kartoti su suderinamomis
2.Algoritmai ir sudėtingumasSunkus
Kaip Bellmano–Fordo algoritmas aptinka iš šaltinio pasiekiamą neigiamo svorio ciklą?
AJis patikrina, ar kuri nors briauna turi neigiamą svorį
BPo V − 1 etapų jis patikrina, ar kurią nors briauną dar galima relaksuoti
CJis suskaičiuoja ciklus paieška gilyn
DJis du kartus paleidžia Dijkstros algoritmą ir palygina abu atstumų rezultatus
3.Duomenų struktūrosVidutinis
AVL medžiai ir raudonai juodi medžiai garantuoja:
AO(log n) aukštį perbalansavimo dėka
BKad nė vienas mazgas neturi dviejų vaikų
CKad raktai saugomi įterpimo tvarka
DPastovaus laiko paiešką bet kokiu atveju
4.Duomenų struktūrosSunkus
Objektas saugomas kaip raktas maišos atvaizdyje, o paskui pakeičiamas laukas, kurį naudoja jo maišos funkcija. Koks tikėtinas rezultatas?
AAtvaizdis automatiškai perkelia raktą į naują kibirą
BNiekas nepasikeičia, nes rakto maišos reikšmė skaičiuojama tik vieną kartą programai pasileidus
CObjekto paieška gali nepavykti, nes jis yra senosios maišos reikšmės kibire
DAtvaizdis išmeta klaidą tą akimirką, kai laukas pasikeičia
5.Grafų teorijaVidutinis
Medis turi 3 viršūnių, kurių laipsnis 3, 2 viršūnių, kurių laipsnis 4, 2 viršūnių, kurių laipsnis 5, 2 viršūnių, kurių laipsnis 2, o visos kitos jo viršūnės yra lapai (laipsnis 1). Kiek lapų L jis turi?
3 × deg 32 × deg 42 × deg 52 × deg 2
L =
6.Grafų teorijaSunkus
Kiek yra 2 ilgio uždarų maršrutų, prasidedančių ir pasibaigiančių ties B? Maršrutas gali kartoti viršūnes ir briaunas. Pažymėkite skaičių N.
M = gretimumo matricaL = 2
N =
3Tirpalai
1.Algoritmai ir sudėtingumas
Atsakymas: D · Pasirinkti anksčiausiai pasibaigiančią veiklą, tada kartoti su suderinamomis
Kodėl tai yra atsakymas
Anksčiausios pabaigos pasirinkimo optimalumą galima įrodyti mainų argumentu; kitoms taisyklėms yra kontrpavyzdžių.
Atsakymas
D · Pasirinkti anksčiausiai pasibaigiančią veiklą, tada kartoti su suderinamomis
2.Algoritmai ir sudėtingumas
Atsakymas: B · Po V − 1 etapų jis patikrina, ar kurią nors briauną dar galima relaksuoti
Kodėl tai yra atsakymas
Visi tikrieji trumpiausi atstumai randami per V − 1 etapą; jei kurią nors briauną vis dar galima pagerinti, turi egzistuoti neigiamas ciklas.
Atsakymas
B · Po V − 1 etapų jis patikrina, ar kurią nors briauną dar galima relaksuoti
3.Duomenų struktūros
Atsakymas: A · O(log n) aukštį perbalansavimo dėka
Kodėl tai yra atsakymas
Savaime balansuojantys medžiai išlaiko logaritminį aukštį, todėl paieška, įterpimas ir šalinimas blogiausiu atveju yra O(log n).
Atsakymas
A · O(log n) aukštį perbalansavimo dėka
4.Duomenų struktūros
Atsakymas: C · Objekto paieška gali nepavykti, nes jis yra senosios maišos reikšmės kibire
Kodėl tai yra atsakymas
Rakto vieta buvo parinkta pagal senąją maišos reikšmę; su nauja maišos reikšme paieška ieško netinkamame kibire, todėl raktai turėtų būti nekeičiami.
Atsakymas
C · Objekto paieška gali nepavykti, nes jis yra senosios maišos reikšmės kibire
5.Grafų teorija
Atsakymas: L = 15
Oileris, Hamiltonas ir medžiai: jungus grafas turi Oilerio ciklą (kiekviena briauna vieną kartą, grįžtama į pradžią), kai kiekvienos viršūnės laipsnis lyginis, ir Oilerio kelią, kuris nėra ciklas, kai lygiai dvi viršūnės turi nelyginį laipsnį; tada kelias eina iš vienos nelyginės viršūnės į kitą. Hamiltono ciklas aplanko kiekvieną viršūnę vieną kartą; Kn jų turi (n − 1)!/2. Medis su n viršūnių turi n − 1 briauną, o jungus grafas su m briaunų turi karkasinį medį, pašalinus m − n + 1 briaunų.
Rankų paspaudimo lema medžiui
L + 31 = 2(L + 9) − 2
L = 15
Atsakymas
L = 15
Trumpesnis kelias: L = 2 + Σ (d − 2) pagal viršūnes, kurių laipsnis d ≥ 3.
6.Grafų teorija
Atsakymas: N = 3
Laipsniai: viršūnės laipsnis yra joje susitinkančių briaunų skaičius. Kiekviena briauna turi du galus, todėl laipsnių suma lygi dvigubam briaunų skaičiui: Σ deg(v) = 2|E| (rankų paspaudimo lema). Todėl nelyginio laipsnio viršūnių skaičius lyginis. Kn turi n(n − 1)/2 briaunų, k-reguliarusis grafas su n viršūnių – nk/2, o medis su n viršūnių – n − 1 briauną.