Vienkārši grafu algoritmi / Referāts / ID: 423371

Autors: Valentīns Livdāns (2)

Vērtējums:

Publicēts: 24.11.2000.

Valoda: Latviešu

Līmenis: Augstskolas

Literatūras saraksts: Nav

Atsauces: Nav

Laikposms: 20. gs. (1900. - 1999. g.)
2000. - 2010. g.

Izvērst priekšskatu

SatursAizvērt

Nr.	Sadaļas nosaukums	Lpp.
	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

Darba fragmentsAizvērt

IEVADS

Š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ā.…

Autora komentārsAtvērt

Darbu komplekts:

IZDEVĪGI pirkt komplektā ➞ ietaupīsi −2,48 €