-
Vienkārši grafu algoritmi
2000. - 2010. g.
| 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 |
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ā.…
Grafu attēlošana. Pārmeklēšana plašumā. Pārmeklēšana dziļumā. Topoloģiskā kārtošana. Stingri savienotas komponentes.
