Grafų teorija: uždaviniai su sprendimais žingsnis po žingsnio

Nemokami uždaviniai tema Grafų teorija su brėžiniais, užuominomis ir išsamiais sprendimais. Kiekvieną kartą naujos reikšmės, trijų lygių: laipsniai ir briaunos, Oilerio keliai ir medžiai, trumpiausi keliai ir karkasiniai medžiai.

Nemokamas pratybų uždavinysLengvas

Medis turi 12 viršūnių. Kiek briaunų |E| jis turi?

|V| = 12

Tikslus atsakymas: sveikasis skaičius, be apvalinimo.

Kitas uždavinys →
Praktikuokitės nemokamai: Grafų teorijaPraktikuokitės dabar: Grafų teorijaKasdien nemokamų uždavinių: 5. Kortelės nereikia.

Ką praktikuositės

  1. Lengvaslaipsniai ir briaunos
  2. VidutinisOilerio keliai ir medžiai
  3. Sunkustrumpiausi keliai ir karkasiniai medžiai

Kaip spręsti uždavinius tema Grafų teorija

  1. Užrašykite kiekvienos viršūnės laipsnį; laipsnių suma lygi dvigubam briaunų skaičiui.
  2. Oilerio uždaviniuose patikrinkite, ar grafas jungus, ir suskaičiuokite nelyginio laipsnio viršūnes.
  3. Medžiams naudokite n − 1 briaunų ir rankų paspaudimo lemą.
  4. Dijkstros algoritme laikykite preliminarių atstumų lentelę ir kiekviename etape užfiksuokite mažiausio atstumo dar neužfiksuotą viršūnę.
  5. 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).

Dažnos klaidos

  • Pamiršti laipsnių sumą padalyti iš 2.
  • Grafą vadinti Oilerio nepatikrinus jungumo.
  • Dijkstros algoritme užfiksuoti viršūnę, kol jos atstumas dar nėra mažiausias.
  • Imti lengviausias briaunas netikrinant, ar nesusidaro ciklų.
  • Skaičiuoti Hamiltono ciklus grafe Kn kaip n!, o ne (n − 1)!/2.

Pagrindinės formulės

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

Išmokite Grafų teorija nuo nulio

Prieš tai: Aibės, sąryšiai ir funkcijos

1Viršūnės, briaunos ir laipsniai

Grafą sudaro viršūnės (taškai) ir briaunos (linijos tarp dviejų viršūnių). Paprastajame grafe nėra kilpų ir dvigubų briaunų.

Viršūnės laipsnis yra joje susitinkančių briaunų skaičius. Kiekviena briauna turi du galus, todėl prideda 1 prie kiekvieno galo laipsnio. Iš to išplaukia rankų paspaudimo lema:

Σ deg(v) = 2·|E|

Dvi išvados: laipsnių suma visada lyginė, ir nelyginio laipsnio viršūnių skaičius taip pat lyginis.

  • Pilnasis grafas Kn jungia kiekvieną porą: n(n − 1)/2 briaunų.
  • Pilnasis dvidalis grafas Km,n jungia kiekvieną vienos pusės viršūnę su kiekviena kitos pusės viršūne: m·n briaunų.
  • k-reguliarusis grafas su n viršūnių turi n·k/2 briaunų.

Gretimumo matrica turi 1 ties (i, j), kai i ir j sujungtos. Neorientuotam grafui ji simetrinė, eilutės suma yra laipsnis, o Mᴸ elementas (i, j) parodo L ilgio maršrutų iš i į j skaičių.

Savikontrolė Grafo laipsniai yra 3, 3, 2, 2, 2. Kiek jis turi briaunų?
  1. 10
  2. 12
  3. 5
  4. 6

Atsakymas: 6. Laipsnių suma lygi 12, o kiekviena briauna suskaičiuota du kartus, todėl briaunų yra 12/2 = 6. Skaičius 5 yra viršūnių skaičius.

2Oilerio ir Hamiltono keliai

Oilerio ciklas panaudoja kiekvieną briauną lygiai vieną kartą ir grįžta į pradžią. Oilerio kelias panaudoja kiekvieną briauną vieną kartą, bet gali baigtis kitur. Jungiam grafui:

  • visi laipsniai lyginiai: Oilerio ciklas egzistuoja;
  • lygiai du nelyginiai laipsniai: Oilerio kelias egzistuoja, iš vienos nelyginės viršūnės į kitą;
  • daugiau nei du nelyginiai laipsniai: nėra nei vieno, nei kito.

Hamiltono ciklas aplanko kiekvieną viršūnę lygiai vieną kartą. Paprasto laipsnių testo jam nėra. Grafe Kn yra (n − 1)!/2 skirtingų Hamiltono ciklų: pasirinkite pradžią, išdėstykite kitas n − 1 viršūnių ir padalykite iš 2 dėl dviejų krypčių.

Savikontrolė Jungus grafas turi laipsnius 2, 3, 4, 3, 2. Ką jis turi?
  1. Ir Oilerio ciklą, ir Oilerio kelią, kuris nėra ciklas
  2. Nei vieno, nei kito
  3. Oilerio ciklą
  4. Oilerio kelią, bet ne Oilerio ciklą

Atsakymas: Oilerio kelią, bet ne Oilerio ciklą. Lygiai dvi viršūnės turi nelyginį laipsnį (dvi trijulės), todėl tarp jų yra Oilerio kelias, bet ne ciklas.

3Medžiai

Medis yra jungus grafas be ciklų. Kiekvienas medis su n viršūnių turi lygiai n − 1 briauną. Pridėjus bet kurią briauną, atsiranda ciklas; pašalinus bet kurią briauną, medis suskyla.

c medžių miškas su n viršūnių turi n − c briaunų. Jungus grafas su m briaunų turi karkasinį medį, pašalinus m − n + 1 briaunų.

Rankų paspaudimo lema padeda skaičiuoti lapus: Σ deg = 2(n − 1). Trumpa forma yra L = 2 + Σ (d − 2) pagal viršūnes, kurių laipsnis d ≥ 3. Medis su dviem trečiojo laipsnio viršūnėmis, o likusios – lapai, turi 2 + 1 + 1 = 4 lapus.

4Dijkstra ir minimalūs karkasiniai medžiai

Dijkstros algoritmas randa trumpiausius atstumus nuo pradinės viršūnės grafe su neneigiamais svoriais.

  1. Pradinės viršūnės atstumą padarykite 0, o visų kitų – ∞.
  2. Užfiksuokite neužfiksuotą viršūnę su mažiausiu atstumu; jos atstumas dabar galutinis.
  3. Kiekvienai kaimynei v atnaujinkite d(v) = min(d(v), d(u) + w(u, v)).
  4. Kartokite, kol tikslo viršūnė bus užfiksuota.

Minimalus karkasinis medis jungia visas viršūnes mažiausiu bendru svoriu. Kruskalis surikiuoja briaunas nuo lengvų iki sunkių ir paima kiekvieną, nebent ji uždarytų ciklą. Primas augina vieną medį iš pradinės viršūnės, visada pridėdamas lengviausią iš jo išeinančią briauną. Abu sustoja po n − 1 briaunų.

Išspręstas pavyzdys

Raskite trumpiausią atstumą nuo A iki E toliau pateiktame grafe.

1

Pradžia

412581ABCDE

d(A) = 0. Jos kaimynai gauna d(B) = 4 ir d(C) = 1.

2

Užfiksuokite C (1)

Per C: d(B) = min(4, 1 + 2) = 3 ir d(E) = 1 + 8 = 9.

3

Užfiksuokite B (3)

Per B: d(D) = 3 + 5 = 8.

4

Užfiksuokite D (8)

Per D: d(E) = min(9, 8 + 1) = 9. Pagerėjimo nėra, lygybė.

5

Užfiksuokite E (9)

E užfiksuota: jos atstumas galutinis.

Atsakymas

Trumpiausias atstumas yra d(E) = 9 keliu A → C → E. Maršrutas A → C → B → D → E to paties ilgio: 1 + 2 + 5 + 1 = 9.

Savikontrolė Kruskalio algoritmas paėmė 1, 2 ir 3 svorio briaunas. Kita lengviausia briauna, kurios svoris 4, jungia dvi jau sujungtas viršūnes. Kas atsitinka?
  1. Algoritmas sustoja
  2. Ji paimama, nes yra lengviausia likusi
  3. Ji praleidžiama, nes uždarytų ciklą
  4. Vietoj to pašalinama 3 svorio briauna

Atsakymas: Ji praleidžiama, nes uždarytų ciklą. Kruskalio algoritmas niekada neuždaro ciklo: briauna tarp dviejų to paties komponento viršūnių praleidžiama, ir algoritmas pereina prie kitos briaunos.

5Dažnos klaidos

  • Pamiršti laipsnių sumą padalyti iš 2, norint gauti briaunų skaičių.
  • Tikrinti Oilerio ciklą nepatikrinus, ar grafas jungus.
  • Dijkstros algoritme užfiksuoti viršūnę, kol ji dar neturi mažiausio preliminaraus atstumo.
  • Imti n − 1 lengviausių briaunų netikrinant, ar nesusidaro ciklų.
  • Skaičiuoti Hamiltono ciklus grafe Kn kaip n!, o ne (n − 1)!/2.

6Kaip atrodo egzamino uždaviniai

  • Lengvas: laipsniai ir briaunos. Naudojate rankų paspaudimo lemą, skaičiuojate Kn, Km,n, reguliarųjų grafų ir medžių briaunas, skaitote gretimumo matricą arba pasirenkate viršūnę su duotu laipsniu.
  • Vidutinis: Oilerio keliai ir medžiai. Nusprendžiate, ar grafas turi Oilerio ciklą ar kelią, skaičiuojate medžio lapus, briaunų, kurias reikia pašalinti karkasiniam medžiui gauti, skaičių arba Hamiltono ciklus grafe Kn.
  • Sunkus: trumpiausi keliai ir karkasiniai medžiai. Vykdote Dijkstros algoritmą, randate nurodytame etape užfiksuotą viršūnę, minimalaus karkasinio medžio svorį, pasirenkate briauną, kurią kitą prideda Kruskalis ar Primas, arba skaičiuojate maršrutus gretimumo matrica.

Mokykitės žingsnis po žingsnio programėlėjeMokykitės žingsnis po žingsnio programėlėje

Išspręsti pavyzdžiai

Pavyzdys 1Lengvas
AABBCCDDEE0010000001100010000101110

Parodyta paprastojo neorientuotojo grafo gretimumo matrica. Kiek briaunų |E| turi grafas?

Raskite |E|

Rodyti užuominas
  1. Elementas (i, j) lygus 1, kai viršūnes i ir j jungia briauna.
  2. Kiekviena briauna {i, j} duoda du vienetus: vieną ties (i, j) ir vieną ties (j, i).
  3. Matricoje yra 8 vienetų.
Rodyti atsakymą ir sprendimą žingsnis po žingsnio

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ą.

Suskaičiuokite vienetus

eilučių sumos: 1 + 1 + 2 + 1 + 3 = 8
|E| = 8/2 = 4

Atsakymas

|E| = 4
Pavyzdys 2Vidutinis
ABCDEFGOilerio ciklasOilerio kelias, ne ciklasnei viena

Ar jungus grafas turi Oilerio ciklą, Oilerio kelią, kuris nėra ciklas, ar nei vieno? Spustelėkite savo atsakymą.

|V| = 7|E| = 10
  1. 1Oilerio ciklas
  2. 2Oilerio kelias, ne ciklas
  3. 3nei viena
Rodyti užuominas
  1. Oilerio teoremai reikia tik viršūnių laipsnių (grafas jungus).
  2. Visi laipsniai lyginiai: Oilerio ciklas. Lygiai du nelyginiai laipsniai: Oilerio kelias tarp jų. Daugiau: nei vieno.
  3. Suskaičiuokite nelyginio laipsnio viršūnes.
Rodyti atsakymą ir paaiškinimą

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

deg(A) = 1, deg(B) = 4, deg(C) = 2, deg(D) = 4, deg(E) = 4, deg(F) = 2, deg(G) = 3

Nelyginės viršūnės

A, G → 2
Oilerio kelias, ne ciklas

Atsakymas

Oilerio kelias, ne ciklas

Oilerio kelias prasideda vienoje nelyginėje viršūnėje ir baigiasi kitoje.

Pavyzdys 3Sunkus
ABCDEF

Kiek yra 3 ilgio uždarų maršrutų, prasidedančių ir pasibaigiančių ties E? Maršrutas gali kartoti viršūnes ir briaunas. Pažymėkite skaičių N.

M = gretimumo matricaL = 3

Raskite N

Rodyti užuominas
  1. Su gretimumo matrica M, L ilgio maršrutų iš i į j skaičius yra Mᴸ elementas (i, j).
  2. Pirmiausia suskaičiuokite 2 ilgio maršrutus iš E į kiekvieną viršūnę, tada žengkite dar vieną žingsnį.
  3. 2 ilgio maršrutai iš E: A: 2, B: 1, C: 0, D: 2, E: 4, F: 1.
Rodyti atsakymą ir sprendimą žingsnis po žingsnio

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ą.

Gretimumo matrica

A: 0 1 1 0 0 0
B: 1 0 0 1 1 0
C: 1 0 0 0 1 0
D: 0 1 0 0 1 1
E: 0 1 1 1 0 1
F: 0 0 0 1 1 0

Dar vienas žingsnis

(M³)EE = 2·0 + 1·1 + 0·1 + 2·1 + 4·0 + 1·1 = 4

Atsakymas

N = 4

Klausimai ir atsakymai

Grafų teorija: kas tai?

Viršūnės laipsnis yra joje susitinkančių briaunų skaičius. Kiekviena briauna turi du galus, todėl prideda 1 prie kiekvieno galo laipsnio. Iš to išplaukia rankų paspaudimo lema:

Dvi išvados: laipsnių suma visada lyginė, ir nelyginio laipsnio viršūnių skaičius taip pat lyginis.

Grafų teorija: kaip spręsti uždavinius žingsnis po žingsnio?
  1. Užrašykite kiekvienos viršūnės laipsnį; laipsnių suma lygi dvigubam briaunų skaičiui.
  2. Oilerio uždaviniuose patikrinkite, ar grafas jungus, ir suskaičiuokite nelyginio laipsnio viršūnes.
  3. Medžiams naudokite n − 1 briaunų ir rankų paspaudimo lemą.
  4. Dijkstros algoritme laikykite preliminarių atstumų lentelę ir kiekviename etape užfiksuokite mažiausio atstumo dar neužfiksuotą viršūnę.
  5. 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).
Grafų teorija: kokios klaidos dažniausios?
  • Pamiršti laipsnių sumą padalyti iš 2.
  • Grafą vadinti Oilerio nepatikrinus jungumo.
  • Dijkstros algoritme užfiksuoti viršūnę, kol jos atstumas dar nėra mažiausias.
  • Imti lengviausias briaunas netikrinant, ar nesusidaro ciklų.
  • Skaičiuoti Hamiltono ciklus grafe Kn kaip n!, o ne (n − 1)!/2.
Grafų teorija: ką lavinsite?
  • Lengvas: laipsniai ir briaunos
  • Vidutinis: Oilerio keliai ir medžiai
  • Sunkus: trumpiausi keliai ir karkasiniai medžiai

Kiekviename uždavinyje naujos reikšmės, todėl išmokstate metodą, o ne atsakymą. Strigote? Pirmiausia atverkite nedidelę užuominą, o visą paaiškinimą – tik kai jo prireiks.

Kaip vyksta praktika

  • Kiekviename uždavinyje naujos reikšmės, todėl išmokstate metodą, o ne atsakymą.
  • Strigote? Pirmiausia atverkite nedidelę užuominą, o visą paaiškinimą – tik kai jo prireiks.
  • Jūsų pažanga, klaidos ir išsaugoti uždaviniai išlieka, todėl prieš egzaminą galite viską pakartoti.

Temos prieš šią ir po jos

Pirmiausia išmokite

Aibės, sąryšiai ir funkcijos

Kursai su šia tema

Duomenų struktūros ir algoritmaiInformatikos pagrindaiDiskrečioji matematika

Daugiau temų: Matematika ir statistika

RibosIšvestinėsOptimizavimasIntegralaiSekos ir eilutėsKelių kintamųjų diferencialinis skaičiavimasDiferencialinės lygtysKompleksiniai skaičiaiSkaitiniai metodaiMatricos ir determinantaiVektoriai: skaliarinė ir vektorinė sandaugaTeiginių logika ir įrodymaiAibės, sąryšiai ir funkcijosSkaičių teorija ir modulinė aritmetikaTikimybėAprašomoji statistikaNormalusis skirstinysPasikliautinieji intervalaiHipotezių tikrinimas ir pasikliautinieji intervalaiTiesinė regresija ir koreliacijaChi kvadrato testai

Spausdinamas užduočių lapas

Užduočių lapas tema Grafų teorija su atsakymais
Praktikuokitės nemokamai: Grafų teorijaPraktikuokitės dabar: Grafų teorijaKasdien nemokamų uždavinių: 5. Kortelės nereikia.