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
Kuris rikiavimo algoritmas yra stabilus?
ARikiavimas išrinkimu (įprasta versija)
BGreitasis rikiavimas (įprasta versija vietoje)
CRikiavimas suliejimu
DRikiavimas krūva
2.Algoritmai ir sudėtingumasSunkus
Kodėl bet kuriai palyginimais pagrįstai paieškai surikiuotame masyve blogiausiu atveju reikia Ω(log n) palyginimų?
AKiekvienas palyginimas trunka logaritminį laiką
BKiekvieną elementą reikia palyginti bent kartą
CDvejetainė paieška yra vienintelis galimas algoritmas, ir jam reikia log₂ n palyginimų
DSprendimų medžio su n galimų baigčių gylis turi būti bent log₂ n
3.Duomenų struktūrosVidutinis
Kiek laiko užtrunka patikrinti, ar briauna (u, v) egzistuoja, naudojant gretimumo matricą?
AO(log V)
BO(V)
CO(1)
DO(E)
4.Duomenų struktūrosSunkus
DPM, kurio šaknis 50, kairysis pomedis 30 (vaikai 20, 40) ir dešinysis pomedis 70 (vaikai 60, 80), šaknis pašalinama naudojant in-order įpėdinį. Kuris raktas tampa nauja šaknimi?
A40
B80
C70
D60
5.Grafų teorijaVidutinis
Ar jungus grafas turi Oilerio ciklą, Oilerio kelią, kuris nėra ciklas, ar nei vieno? Spustelėkite savo atsakymą.
|V| = 7|E| = 7
1Oilerio ciklas
2Oilerio kelias, ne ciklas
3nei viena
6.Grafų teorijaSunkus
Kiek yra 3 ilgio maršrutų iš E į B? Maršrutas gali kartoti viršūnes ir briaunas. Pažymėkite skaičių N.
M = gretimumo matricaL = 3
N =
3Tirpalai
1.Algoritmai ir sudėtingumas
Atsakymas: C · Rikiavimas suliejimu
Kodėl tai yra atsakymas
Rikiavimas suliejimu yra stabilus, jei esant lygiems raktams suliejant pirmiausia imamas elementas iš kairiosios pusės. Greitasis rikiavimas vietoje, rikiavimas krūva ir rikiavimas išrinkimu paprastai nėra stabilūs.
Atsakymas
C · Rikiavimas suliejimu
2.Algoritmai ir sudėtingumas
Atsakymas: D · Sprendimų medžio su n galimų baigčių gylis turi būti bent log₂ n
Kodėl tai yra atsakymas
Kiekvienas palyginimas likusių galimybių aibę sumažina daugiausia perpus, todėl norint atskirti n pozicijų reikia bent log₂ n palyginimų.
Atsakymas
D · Sprendimų medžio su n galimų baigčių gylis turi būti bent log₂ n
3.Duomenų struktūros
Atsakymas: C · O(1)
Kodėl tai yra atsakymas
Matricos įrašas u eilutėje ir v stulpelyje iš karto parodo, ar briauna egzistuoja; gretimumo sąraše gali tekti peržiūrėti u kaimynus.
Atsakymas
C · O(1)
4.Duomenų struktūros
Atsakymas: D · 60
Kodėl tai yra atsakymas
Kairiausias dešiniojo pomedžio mazgas yra 60, todėl 60 pakeičia 50, o jo senoji vieta pašalinama; naudojant pirmtaką būtų gauta 40.
Atsakymas
D · 60
5.Grafų teorija
Atsakymas: nei viena
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ų.
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ą.