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
ABCDEFG

Lygiai viena grafo viršūnė turi laipsnį 1. Spustelėkite ją.

deg = 1
  1. 1A
  2. 2B
  3. 3C
  4. 4D
  5. 5E
  6. 6F
  7. 7G
2.Lengvas

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

deg: 3, 3, 2, 2, 2
|E| =
3.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
4.Vidutinis

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

2 × deg 3
L =
5.Sunkus
41710792015ABCDE

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

pradžia: Bk = 3
  1. 1briauna AB
  2. 2briauna AC
  3. 3briauna BC
  4. 4briauna BD
  5. 5briauna CE
  6. 6briauna DE
  7. 7briauna BE
6.Sunkus
7188111412915ABCDEFG

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 BC
  3. 3briauna BD
  4. 4briauna CE
  5. 5briauna EF
  6. 6briauna GB
  7. 7briauna GC
  8. 8briauna GD
  9. 9briauna GE

Atsakymai

  1. 1. F
  2. 2. |E| = 6
  3. 3. Oilerio ciklas
  4. 4. L = 4
  5. 5. briauna BC
  6. 6. briauna BD

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