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

Kiek briaunų |E| turi pilnasis grafas K5?

K5
|E| =
2.Lengvas

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

|V| = 35c = 2
|E| =
3.Vidutinis

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

|V| = 16|E| = 23
k =
4.Vidutinis
ABCDEOilerio 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| = 5|E| = 6
  1. 1Oilerio ciklas
  2. 2Oilerio kelias, ne ciklas
  3. 3nei viena
5.Sunkus
20112811710652ABCDEFG

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

k = 4
  1. 1briauna AB
  2. 2briauna AC
  3. 3briauna BD
  4. 4briauna CE
  5. 5briauna DE
  6. 6briauna DF
  7. 7briauna EF
  8. 8briauna GC
  9. 9briauna GD
  10. 10briauna GE
6.Sunkus
121618111511013517ABCDEFG

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

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

Atsakymai

  1. 1. |E| = 10
  2. 2. |E| = 33
  3. 3. k = 8
  4. 4. Oilerio ciklas
  5. 5. briauna GC
  6. 6. briauna DE

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