Add Papers Marked0
Paper checked off!

Marked works

Viewed0

Viewed works

Shopping Cart0
Paper added to shopping cart!

Shopping Cart

Register Now

internet library
Atlants.lv library
FAQ
4,99 € Add to cart
Add to Wish List
Want cheaper?
ID number:897916
 
Evaluation:
Published: 15.04.2003.
Language: Latvian
Level: College/University
Literature: n/a
References: Not used
Table of contents
Nr. Chapter  Page.
  IEVADS    1
1.  GRAFU ATTĒLOŠANA    2
2.  PĀRMEKLĒŠANA PLAŠUMĀ    4
2.1.  Procedūra BFS    4
2.2.  Procedūras BFS darbības analīze    6
2.3.  Īsākais ceļš    7
2.4.  Teorēma 1    7
2.5.  Teorēma 2    7
2.6.  Teorēma 3    8
2.7.  Teorēma 4    8
2.8.  Pārmeklēšanas plašumā koks    9
2.9.  Teorēma 5    10
3.  PĀRMEKLĒŠANA DZIĻUMĀ    11
3.1.  Procedūra DFS un DFS-Visit    12
3.2.  Pārmeklēšanas dziļumā algoritma īpašības    13
3.3.  Teorēma 6 ( Intervālu teorēma )    14
3.4.  Secinājums 7    14
3.5.  Teorēma 8    16
3.6.  Loku klasifikācija    16
3.7.  Teorēma 9    17
4.  TOPOLOĢISKĀ KĀRTOŠANA    18
4.1.  Procedūra Topological-Sort    19
4.2.  Teorēma 10    19
4.3.  Teorēma 11    19
5.  STINGRI SAVIENOTĀS KOMPONENTES    20
5.1.  ProcedūraStrongly-Connected-Components    21
5.2.  Teorēma 12    21
5.3.  Teorēma 13    22
5.4.  Teorēma 14    22
5.5.  Secinājums 15    23
5.6.  Teorēma 16    23
5.7.  Teorēma 17    24
6.  NOBEIGUMS    26
Extract

Šis darbs dot pārskatu par dažām grafu aprakstīšanas, parmeklēšanas un kārtošanas metodēm. Pārmeklēt grafu nozīmē sistemātiski izsekot grafa lokus, tātad iziet grafa virsotnes. Ir vairāki grafu pārmeklēšanas algoritmi. Daudzi no tiem balstās uz to, ka no sākuma tiek iegūta informāciju par grafa struktūru, un tikai tad notiek grafa pārmeklēšana. Citi algoritmi strādā vienkārši izvēršot virsotni pēc virsotnes. Paši pa sevīm grafu parmeklēšanas algoritmi dot iespeju arī atklāt grafa struktūru un tie aizņem svarīgu daļu grafu algoritmos.
Darba pirmā nodaļā būs apskatīti divi vissizplatītākie grafa aprakstīšanas veidi: blakus virsotņu saraksts un blakus virsotņu matrica. Otrā nodaļā aprakstīts vienkārš grafa pārmeklēšanas algoritms - pārmeklēšana plašumā, un arī tiek parādīts kā tiek konstruēts pārmeklēšanas plašumā koks. Trešā nodaļā apskatīsim dziļumā pārmeklēšanas algoritmu, un piemēru kurā var redzēt kādā kartībā dziļumā pārmeklēšanas algoritms apskata virsotnes. Ceturtā nodaļa būs veltīta topoloģiskai grafa kārtošanai. Un beidzot piektajā nodaļā ir aprakstīts tāds jēdziens kā stingri savienotās komponentes un arī tiek apskatīta procedūra kura sameklē tās virzītā grafā.
Ir divi standarta veidi kā aprakstīt grafu G = (V, E) (V – virsotņu kopa, E – loku kopa): proti ar blakus virsotņu saraksta vai ar blakus virsotņu matricas palīdzību. Blakus virsotņu sarakstu lieto parasti biežāk, tapēc, ka tas nodrošina iespeju 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ā strarpā savienotas ar loku.
2. att. Divi veidi kā aprakstīt virzītu grafu. (a) Grafs G sastāv no sešām virsotnēm un astoņiem lokiem. (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 nevirzītam grafam no attēla 1(a). Respektīvi attēlā 2(b) arī redzams blakus virsotņu saraksts virzītam grafam no attēla 2(a).
Ja grafs G ir virzīts grafs, tad loku garumu summa blakus virsotņu sarakstā ir vienāda ar |E|, bet ja G ir nevirzīts grafs tad loku garumu summa blakus virsotņu sarakstā ir vienāda ar 2|E|, tas ir tapēc kā aprakstot nevirzītu grafu viens un tas pats loks sarakstā parādās divas reizes.
Neatkarīgi no tā vai grafs ir virzīts vai nav, blakus virsotņu sarakstam piemīt tāda īpašība: nepieciešamā atmiņa lai aprakstīt grafu ir O(max(V,E)) = O(V+E)…

Author's comment
Load more similar papers

Atlants

Choose Authorization Method

Email & Password

Email & Password

Wrong e-mail adress or password!
Log In

Forgot your password?

Draugiem.pase
Facebook

Not registered yet?

Register and redeem free papers!

To receive free papers from Atlants.com it is necessary to register. It's quick and will only take a few seconds.

If you have already registered, simply to access the free content.

Cancel Register