Grafs
- Šis raksts ir par matemātikas un datorzinātnes jēdzienu. Par citām jēdziena grafs nozīmēm skatīt nozīmju atdalīšanas lapu.
Grafs matemātikā ir punktu (kurus sauc par virsotnēm) kopa kopā ar šķautnēm, kas tos savieno. Datorzinātnē grafs ir nelineāra datu struktūra. Tādējādi grafs ir svarīgs diskrētās matemātikas un datorzinātnes jēdziens. Grafus un to īpašības pēta grafu teorija.
Matemātiskais apraksts
Par grafu sauc sistēmu (V; E), kur V ir netukša kopa, bet E - divu argumentu funkcija kopā V. E katram pārim (x; y) no VxV piekārto kādu kopu E(x; y) tā, ka:
- neviena no kopām E(x; y) nešķeļas ar V,
- dažādiem pāriem (x; y); (x1; y1) piekārtotas kopas var šķelties vienīgi tad,
ja šie pāri ir viens otram apgriezti: (x; y) = (y1; x1).
Kopas V elementi ir grafa virsotnes, kopā (x; y) atrodas šķautnes.
Grafu uzdošana
Grafu var uzdot ar incidences matricu, incidences sarakstu vai arī kā zīmējumu.
Grafu veidi
Matemātikā, grafu teorijā un citur ir svarīgi šādi grafu veidi:
- Sakarīgs grafs. Tas ir tāds grafs, kuram no jebkuras virsotnes var aiziet uz jebkuru citu virsotni, pārvietojoties tikai pa grafa šķautnēm.
- Planārs grafs. Tas ir grafs, ko iespējams attēlot plaknē tā, ka tā šķautnes nekrustojas.
- Orientēts grafs. Tas ir grafs, kura katrai šķautnei ir piekārtots virziens.
- Multigrafs. Tas ir grafs, kuram ir divas virsotnes, kas savienotas ar vairāk nekā vienu šķautni.
Algoritmi darbam ar grafiem
Pazīstami vairāki grafa apstaigāšanas algoritmi: apstaigāšana dziļumā (DFS), apstaigāšana plašumā (BFS).
Skatīt arī
Ārējās saites
- Eric W. Weisstein, Graph, MathWorld.
- Graph Arhivēts 2010. gada 20. jūnijā, Wayback Machine vietnē., PlanetMath.
- Paulis Ķikusts, Grafu teorija Arhivēts 2008. gada 26. februārī, Wayback Machine vietnē..
- Jānis Dambītis, Modernā grafu teorija Arhivēts 2009. gada 9. aprīlī, Wayback Machine vietnē..
- Jānis Cīrulis, Grafu teorija Arhivēts 2016. gada 5. martā, Wayback Machine vietnē..
- Grafu teorija[novecojusi saite], lekciju materiāli LU kursam DatZ5031 (lai piekļūtu, jāklikšķina uz "Login as a guest").
- Pēteris Daugulis, Grafu teorija[novecojusi saite].
Content Disclaimer
Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.
- The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
- There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
- It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
- Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
- Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.