Vienkārši grafu algoritmi / Реферат / ID: 423371

4,99 € В корзину

Добавить в список желаний

В списке желаний

Хочешь дешевле?

Идентификатор:423371

Автор: Valentīns Livdāns (2)

Оценка:

Опубликованно: 24.11.2000.

Язык: Латышский

Уровень: Университет

Литературный список: Нет

Ссылки: Не использованы

Рассмотреный период: 20-й век (1900–1999 гг.)
2000–2010 гг.

Увеличить просмотр

Содержание

Nr.	Название главы	Стр.
	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

Фрагмент работы

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

Коментарий автора

Комплект работ:

ВЫГОДНО купить комплект ➞ экономия −2,48 €