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

Miškas (grafas be ciklų) turi 28 viršūnių ir 6 jungumo komponenčių. Kiek briaunų |E| jis turi?

|V| = 28c = 6
|E| =
2.Lengvas
AABBCCDDEE0110010111110010100101110

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

|E| =
3.Vidutinis

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

|V| = 14|E| = 25
k =
4.Vidutinis

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

K4
H =
5.Sunkus
39161712571415ABCDEF

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

pradžia: Ek = 3
  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 BE
6.Sunkus
515201761118119102ABCDEFG

Raskite svertinio grafo minimalaus karkasinio medžio bendrą svorį W.

|V| = 7|E| = 11
W =

Atsakymai

  1. 1. |E| = 22
  2. 2. |E| = 7
  3. 3. k = 12
  4. 4. H = 3
  5. 5. briauna CE
  6. 6. W = 40

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