Neorientēti grafi

Last modified by superadmin on 2018-01-12 20:38

Neorientēti grafi

Datorprogrammās izmanto un maina ne vien pašus datus (skaitļus, vārdus, utml.), bet arī datu vienību savstarpējās attiecības un struktūru. Tās bieži var aprakstīt ar grafiem. Grafos virsotnes attēlo atsevišķos objektus, ko savieno ar šķautnēm, kuras izsaka šo objektu attiecības. Īpaši svarīgs grafu paveids ir koki, kuri apraksta pakārtotas struktūras (piemēram, kurš objekts kuram pakļauts, vai kurš objekts kuru satur).

Neorientēts Grafs sastāv no virsotnēm V = {v1, v2, ..., vn} un šķautnēmE = {e1, e2, ..., em}. Katra šķautne ir divu grafa virsotņu pāris. Piemēram, pieraksts e5 = (v3,v17) nozīmē, ka piektā šķautne savieno trešo virsotni ar septiņpadsmito virsotni. Parastos jeb neorientētos grafos šķautnes virziens nav svarīgs, t.i. (v3,v17) = (v17,v3). (Orientētos grafos katrai šķautnei ir sākuma un beigu punkts un to secība tātad ir svarīga - tos aplūkosim nākamajā nodaļā.)

Grafa piemērs: V = {v1, v2, v3, v4}; E = {(v1,v2), (v2,v3), (v3,v4), (v4,v1)}. To var attēlot zīmējumā, katru virsotni apzīmējot ar aplīti un šķautnes attēlojot kā līnijas, kuras savieno aplīšus. Virsotņu izvietojums un šķautņu forma (tās var būt taisnas vai līkumainas) nav svarīga; šķautnes ārpus grafa virsotnēm var arī krustoties, bet šie krustpunkti parasti nevienu neinteresē, jo tie var izmainīties grafu pārzīmējot savādāk. Attēlosim piemēram grafu no mūsu piemēra ar šķautņu krustošanos un bez tās:

#pic("App_Graphs_EqualGraphs.gif", "250") Attēls: Viena grafa 2 dažādi attēlojumi

Grafu sauc par sakarīgu, ja no katras virsotnes uz katru citu var aiziet, izmantojot grafa šķautnes. Sakarīgā grafā ar n virsotnēm jābūt vismaz n-1 šķautnēm. Zīmējumā attēloti sakarīgi grafi ar piecām virsotnēm un četrām šķautnēm:

#pic("App_Graphs_Connected.gif", "300") Attēls: Sakarīgi grafi

Katrām divām virsotnēm grafā ir attālums - mazākas šķautņu skaits, kas jāšķērso, lai no vienas virsotnes nonāktu otrā. Lielāko no visiem attālumiem grafā sauc par grafa diametru. Grafiem iepriekšējā rindkopā ir vienāds virsotņu un šķautņu skaits, bet pirmajam grafam diametrs ir 4, otrajam grafam tas ir 2.

Datoru tīklu varam uzskatīt par grafu - virsotnes tam ir datori, bet šķautnes tiek vilktas starp tādiem diviem datoriem, kuri atrodas vienā lokālajā tīklā. Datoru tīklus svarīgi saslēgt tā, lai attālumi starp virsotnēm (tātad arī diametrs) nebūtu lieli. Vismazākais diametrs ir pilnam grafam, kur katras divas virsotnes savienotas ar šķautni (sk. pilna grafa diagrammu ar 5 virsotnēm):

#pic("App_Graphs_FullGraph.gif", "120") Attēls: Pilns grafs ar 5 virsotnēm

Ja pilnā grafā ir n virsotnes, tad vajadzīgas n(n-1)/2 šķautnes. Piemēram, 1000 virsotņu savienošanai tad vajadzīgs gandrīz pusmiljons šķautņu.

Tags:
Created by Kalvis Apsītis on 2008-05-04 12:26
    
This wiki is licensed under a Creative Commons 2.0 license
XWiki Enterprise 6.4 - Documentation