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 20 viršūnių. Kiek briaunų |E| jis turi?

|V| = 20
|E| =
2.Lengvas
AABBCCDD0110100010010010

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

deg(D) =
3.Vidutinis

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

|V| = 12|E| = 17
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
3121791810519862ABCDEFG

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

pradžia: Ak = 5
  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 GC
  10. 10briauna GD
  11. 11briauna GE
6.Sunkus
ABCDEF

Kiek yra 2 ilgio maršrutų iš A į E? Maršrutas gali kartoti viršūnes ir briaunas. Pažymėkite skaičių N.

M = gretimumo matricaL = 2
N =

Atsakymai

  1. 1. |E| = 19
  2. 2. deg(D) = 1
  3. 3. k = 6
  4. 4. Oilerio ciklas
  5. 5. briauna GE
  6. 6. N = 2

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