Pievienot darbus Atzīmētie0
Darbs ir veiksmīgi atzīmēts!

Atzīmētie darbi

Skatītie0

Skatītie darbi

Grozs0
Darbs ir sekmīgi pievienots grozam!

Grozs

Reģistrēties

interneta bibliotēka
Atlants.lv bibliotēka

Izdevīgi: šodien akcijas cena!

Parastā cena:
3,99
Ietaupījums:
0,44 (11%)
Cena ar atlaidi*:
3,55
Pirkt
Identifikators:806869
Autors:
Vērtējums:
Publicēts: 14.12.2007.
Valoda: Latviešu
Līmenis: Augstskolas
Literatūras saraksts: Nav
Atsauces: Nav
SatursAizvērt
Nr. Sadaļas nosaukums  Lpp.
1.  Grafu attēlošana    3
2.  Meklēšana plašumā    5
  Procedūra BFS (Breadth-First search)    5
  Grafa apstrādes laiks    7
  Īsākais ceļš    7
  Teorēma 1    8
  Teorēma 2    8
  Teorēma 3    8
3.  Meklēšana dziļumā    9
  Procedūras DFS (Depth-First search) un DFS-Visit    10
  Meklēšanas dziļumā algoritma īpašības    11
  Teorēma 1 ( Intervālu teorēma )    12
  Teorēma 2 ( Baltā ceļa teorēma )    12
Darba fragmentsAizvērt

Grafu attēlošana
Grafs sastāv no divām netukšām kopām – viena satur virsotnes, bet otra šķautnes - grafs G = (V, E) (V – virsotņu kopa, E – šķautņu kopa). Pastāv divi standarta veidi kā aprakstīt grafu: ar blakus virsotņu saraksta vai ar blakus virsotņu matricas palīdzību. Blakus virsotņu sarakstu parasti lieto biežāk tāpēc, ka tas nodrošina iespēju kompakti aprakstīt izretinātu grafu – tas ir tāds grafs kur |E| ir daudz mazāks par |V²|. Blakus virsotņu matricas izmantošana grafa aprakstīšanai var būt piemērota tad, kad grafs ir blīvs, proti |E| skaits ir tuvs |V²| skaitam, vai arī tad, kad ir vajadzība ātri noskaidrot vai divas virsotnes ir savā starpā savienotas ar šķautni.
1. att. Divi veidi kā aprakstīt neorientētu grafu. (a) Grafs G sastāv no piecām virsotnēm un septiņām šķautnēm. (b) Grafs G aprakstīts ar blakus virsotņu saraksta palīdzību. (c) Grafs G ir aprakstīts ar blakus virsotņu matricu. 2. att. Divi veidi kā orientētu grafu. (a) Grafs G sastāv no sešām virsotnēm un astoņām šķautnēm. (b) Grafs G aprakstīts ar blakus virsotņu saraksta palīdzību. (c) Grafs G ir aprakstīts ar blakus virsotņu matricu.
Saistīto virsotņu saraksts kas apraksta kādu grafu G = (V,E) sastāv no kopas Adj, kas satur |V| virsotņu sarakstu. Sarakstā ir tik rindas cik ir virsotņu grafā. Priekš katras virsotnes u ∈ V saistīto virsotņu saraksts Adj[u] satur visas virsotnes ar kurām virsotne ir saistīta ar lokiem. Virsotnes blakus virsotņu sarakstā parasti izvieto patvaļīgā kartībā. Attēlā 1(b) ir redzams blakus virsotņu saraksts neorientētam grafam no attēla 1(a). Respektīvi attēlā 2(b) arī redzams blakus virsotņu saraksts orientētam grafam no attēla 2(a).…

Autora komentārsAtvērt
Parādīt vairāk līdzīgos ...

Nosūtīt darbu e-pastā

Tavs vārds:

E-pasta adrese, uz kuru nosūtīt darba saiti:

Sveiks!
{Tavs vārds} iesaka Tev apskatīties interneta bibliotēkas Atlants.lv darbu par tēmu „Algoritmu meklēšana grafos”.

Saite uz darbu:
https://www.atlants.lv/w/806869

Sūtīt

E-pasts ir nosūtīts.

Izvēlies autorizēšanās veidu

E-pasts + parole

E-pasts + parole

Norādīta nepareiza e-pasta adrese vai parole!
Ienākt

Aizmirsi paroli?

Draugiem.pase
Facebook
Twitter

Neesi reģistrējies?

Reģistrējies un saņem bez maksas!

Lai saņemtu bezmaksas darbus no Atlants.lv, ir nepieciešams reģistrēties. Tas ir vienkārši un aizņems vien dažas sekundes.

Ja Tu jau esi reģistrējies, vari vienkārši un varēsi saņemt bezmaksas darbus.

Atcelt Reģistrēties