Užduočių lapas tema Grafų teorija su atsakymais

Nemokamas spausdinamas užduočių lapas tema Grafų teorija: 6 uždavinių nuo lengvų iki egzamino lygio, su atsakymais. Atsispausdinkite arba išsaugokite kaip PDF.

Naujas užduočių lapasPraktikuokitės internete su užuominomis

Mokytojams: galima nemokamai spausdinti, kopijuoti ir naudoti per pamokas. Kiekvienas naujas lapas turi naujas reikšmes ir savo atsakymų raktą. Būsime dėkingi už nuorodą į ExamProblems jūsų kurso puslapyje.

Vardas: ____________________   Data: ____________

1.Lengvas

Medis turi 28 briaunų. Kiek viršūnių |V| jis turi?

|E| = 28
|V| =
2.Lengvas

2-reguliarusis grafas turi 5 viršūnių (kiekvienos viršūnės laipsnis 2). Kiek briaunų |E| jis turi?

n = 5k = 2
|E| =
3.Vidutinis

Medis turi 3 viršūnių, kurių laipsnis 3, 2 viršūnių, kurių laipsnis 5, 4 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 54 × deg 2
L =
4.Vidutinis
ABCDEFOilerio 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| = 6|E| = 7
  1. 1Oilerio ciklas
  2. 2Oilerio kelias, ne ciklas
  3. 3nei viena
5.Sunkus
131911781051218ABCDEFG

Primo algoritmas sudaro minimalų karkasinį medį pradėdamas nuo viršūnės G. Spustelėkite briauną, kurią jis prideda kaip briauną numeris 4.

pradžia: Gk = 4
  1. 1briauna AC
  2. 2briauna BC
  3. 3briauna BD
  4. 4briauna CE
  5. 5briauna DE
  6. 6briauna EF
  7. 7briauna GB
  8. 8briauna GC
  9. 9briauna GD
6.Sunkus
611235151014136ABCDEFG

Dijkstros algoritmu raskite trumpiausio kelio nuo A iki G svertiniame grafe ilgį d(G).

pradžia: Apabaiga: G
d(G) =

Atsakymai

  1. 1. |V| = 29
  2. 2. |E| = 5
  3. 3. L = 11
  4. 4. Oilerio ciklas
  5. 5. briauna EF
  6. 6. d(G) = 19

Išsamūs sprendimai žingsnis po žingsnio: praktikuokite šią temą svetainėje examproblems.com.