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
ABCDE

Lygiai viena grafo viršūnė turi laipsnį 1. Spustelėkite ją.

deg = 1
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
2.Lengvas

Kiek briaunų |E| turi pilnasis grafas K8?

K8
|E| =
3.Vidutinis

Jungus grafas turi 11 viršūnių ir 12 briaunų. Kiek briaunų k reikia pašalinti, kad liktų karkasinis medis?

|V| = 11|E| = 12
k =
4.Vidutinis

Medis turi 3 viršūnių, kurių laipsnis 3, 4 viršūnių, kurių laipsnis 4, o visos kitos jo viršūnės yra lapai (laipsnis 1). Kiek lapų L jis turi?

3 × deg 34 × deg 4
L =
5.Sunkus
712111128121157ABCDEFG

Dijkstros algoritmas vykdomas nuo A. Spustelėkite viršūnę, užfiksuojamą (padaromą galutine) 3 etape; pats A yra 1 etapas.

pradžia: Aetapas 3
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F
  7. 7G
6.Sunkus
17916561511191317ABCDEFG

Kruskalio algoritmas sudaro minimalų karkasinį medį. Spustelėkite briauną, kurią jis prideda kaip briauną numeris 2; praleistos briaunos neskaičiuojamos.

k = 2
  1. 1briauna AB
  2. 2briauna AC
  3. 3briauna BC
  4. 4briauna BD
  5. 5briauna CE
  6. 6briauna DE
  7. 7briauna DF
  8. 8briauna EF
  9. 9briauna GB
  10. 10briauna GC
  11. 11briauna GE

Atsakymai

  1. 1. D
  2. 2. |E| = 28
  3. 3. k = 2
  4. 4. L = 13
  5. 5. G
  6. 6. briauna CE

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