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
AABBCCDDEE0110010111110000100101010

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

deg(A) =
2.Lengvas
AABBCCDDEEFF010000101110010010010011011100000100

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

deg(E) =
3.Vidutinis

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

|V| = 6|E| = 10
k =
4.Vidutinis

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

|V| = 12|E| = 23
k =
5.Sunkus
11158199627416ABCDEFG

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

k = 6
  1. 1briauna AB
  2. 2briauna AC
  3. 3briauna BC
  4. 4briauna BD
  5. 5briauna DF
  6. 6briauna EF
  7. 7briauna GB
  8. 8briauna GC
  9. 9briauna GD
  10. 10briauna GE
6.Sunkus
3154987176ABCDEF

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

|V| = 6|E| = 8
W =

Atsakymai

  1. 1. deg(A) = 2
  2. 2. deg(E) = 3
  3. 3. k = 5
  4. 4. k = 12
  5. 5. briauna AB
  6. 6. W = 29

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