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
AABBCCDDEEFF011000100100100010010000001001000010

Parodyta paprastojo neorientuotojo grafo gretimumo matrica. Raskite viršūnės A laipsnį deg(A).

deg(A) =
2.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
3.Vidutinis

Kiek skirtingų Hamiltono ciklų H turi pilnasis grafas K7? Ciklai, besiskiriantys tik pradine viršūne ar kryptimi, laikomi tuo pačiu.

K7
H =
4.Vidutinis

Medis turi 3 viršūnių, kurių laipsnis 3, 3 viršūnių, kurių laipsnis 4, 3 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 33 × deg 43 × deg 54 × deg 2
L =
5.Sunkus
29514111199ABCDEF

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

pradžia: Apabaiga: F
d(F) =
6.Sunkus
1613721781110203ABCDEFG

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

pradžia: Ck = 3
  1. 1briauna AB
  2. 2briauna AC
  3. 3briauna BD
  4. 4briauna CE
  5. 5briauna DE
  6. 6briauna DF
  7. 7briauna EF
  8. 8briauna GB
  9. 9briauna GC
  10. 10briauna GE

Atsakymai

  1. 1. deg(A) = 2
  2. 2. A
  3. 3. H = 360
  4. 4. L = 20
  5. 5. d(F) = 20
  6. 6. briauna GB

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