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
AABBCCDD0111101011011010

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

|E| =
2.Lengvas

Paprastasis grafas turi 7 viršūnių, kurių laipsniai yra 4, 3, 2, 2, 2, 2, 1. Kiek briaunų |E| jis turi?

deg: 4, 3, 2, 2, 2, 2, 1
|E| =
3.Vidutinis

Medis turi 2 viršūnių, kurių laipsnis 3, 2 viršūnių, kurių laipsnis 2, o visos kitos jo viršūnės yra lapai (laipsnis 1). Kiek lapų L jis turi?

2 × deg 32 × deg 2
L =
4.Vidutinis

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

K8
H =
5.Sunkus
71611134123811029ABCDEFG

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

pradžia: Gk = 2
  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 GB
  10. 10briauna GC
  11. 11briauna GD
  12. 12briauna GE
6.Sunkus
ABCDEF

Kiek yra 2 ilgio uždarų maršrutų, prasidedančių ir pasibaigiančių ties A? Maršrutas gali kartoti viršūnes ir briaunas. Pažymėkite skaičių N.

M = gretimumo matricaL = 2
N =

Atsakymai

  1. 1. |E| = 5
  2. 2. |E| = 8
  3. 3. L = 4
  4. 4. H = 2520
  5. 5. briauna GD
  6. 6. N = 2

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