Phenquestions
Mezglu grafikā sauc par virsotni (daudzskaitlī - virsotnes). Dažreiz to joprojām sauc par mezglu; to var saukt arī par punktu. Saiti grafikā sauc par malu. Dažreiz to joprojām sauc par saiti; to var saukt arī par līniju.
Diagramma ar daudzām funkcijām
Šis attēls parāda diagrammu ar daudzām funkcijām:
Apļi (diski) ir virsotnes. Jebkura taisna līnija vai izliekta līnija vai cilpa ir mala.
Grafika iezīmes
Virsotne
Virsotne ir objekts. Tā var būt māja; tā var būt persona; tas var būt abstrakts lietvārds; tas var būt jebkurš objekts, par kuru var iedomāties.
Mala
Mala ir savienojums (attiecība) starp divām virsotnēm; saikne var būt abstrakta.
Loop
Cilpa ir mala, kas savieno virsotni ar sevi.
Bultu mala
Apsveriet divus cilvēkus: Jāni un Pēteri. Ja Jānis aizdod Pēterim 100 ASV dolārus un ja Jānis un Pēteris ir virsotnes, tad aizdevēja mala būs vērsta uz Pēteri. Ja abi partneri aizmirst, ka Pēteris ir parādā Jānim, un Pēteris aizdod Jānim 100 USD, tad tās pašas malas otrā galā bultiņa būs vērsta uz Džona pusi. Ja Pēteris aizdotu Jānim 75 USD, nevis 100 USD, tad Pēteri ar Jāni savienotu cita mala. Šīs otrās malas bultu uzgalis būs vērsts uz Džonu. Otrajā gadījumā ir divas malas, katra ar vienu bultu uzgali, kas vērsta pretējos virzienos.
Virsotne, uz kuru norāda mala, ir šīs malas galvas virsotne. Virsotne, no kuras atstāj malu, ir astes virsotne.
Incidents
Mala savieno divas virsotnes. Tiek teikts, ka mala ir notikusi uz jebkuru virsotni. Malai nav jābūt bultu galam. Abas virsotnes ir pazīstamas kā malas galapunkti. Ir iespējams izveidot grafiku, kurā virsotne nepieder nevienai malai, taču tas netiks ņemts vērā šajā apmācībā.
Nevirzīts grafiks
Mala var būt bulta, vai arī tā nevar būt. Grafiks, kurā neviena mala nav bulta, ir nenovirzīts grafiks. Malu var attēlot ar taisnu līniju vai līkni vai cilpu.
Virzīts grafiks
Grafiks, kur katra mala ir bulta (virziens), ir virzīts grafiks. Bultiņas malu var attēlot ar taisnu līniju ar bultiņu galu vai līkni ar bultiņas galu vai cilpu ar bultiņas galu.
Virziena neesamība nenovirzīta grafa malā nozīmē, ka katra nenovirzītā grafa mala ir divvirzienu.
Virsotnes pakāpe
Virsotnēs sastopamo malu skaits ir virsotnes pakāpe. Cilpai virsotnē ir divi gadījumi, tāpēc cilpa tiek skaitīta divas reizes.
Grafika secība
Grafika secība ir virsotņu skaits diagrammā.
Multigrafs
Multigrafs ir grafiks, kur dažiem virsotņu pāriem ir vairāk nekā viena mala. Nenovirzīts multigrafs ir tāds grafiks, kurā malām nav virzienu (nav bultiņas). Vērsts multigrafs ir tāds, kur katra mala ir bulta, un virsotņu pāriem, kuriem ir vairāk nekā viena bultiņa, viena virsotne ir šo bultiņu aste, bet otra virsotne ir to pašu bultiņu galva. Šī diagramma parāda nenovirzītu multigrafu:
Vairāk nekā viena mala (t.i.e. vairākas malas) virsotņu pārim sauc arī par paralēlām malām.
Drebuļi
Drebuļi ir multigrafi, kas ļauj veikt cilpas (vienu vai vairākas cilpas). Daži multigrafi nepieļauj cilpas.
Vienkāršs grafiks
Vienkāršs grafiks ir grafiks, kurā diviem virsotņu pāriem nav vairākas malas. Cilpas nav atļautas vienkāršā diagrammā.
Tukša diagramma
Tukša diagramma ir diagramma bez virsotnēm un bez malām.
Jaukts grafiks
Jauktais grafiks ir grafiks, kurā dažas malas ir bultiņas, bet citas nav; citiem vārdiem sakot: dažām malām ir virzieni, bet citām nav vērsta.
Svērtais grafiks
Ir iespējams izveidot grafiku, kurā katrai malai tiek piešķirts skaitlis, kas pazīstams kā svars. Dažām malām ir vienāds skaitlis, bet skaitļi parasti atšķiras. Šādu grafiku sauc par svērto grafiku. Konkrēta grafika skaitļi var norādīt garumu vai izmaksas (cenas) vai kaut kādu lielumu atkarībā no problēmas.
Nepiedienīgs un nepārsniedzams
Vārdnīca, bez pakāpes un ārpus pakāpes ir piemērojama tikai virzītam grafikam. Grafiks var būt multigrāfs vai nebūt. Grafikā var būt vai nav cilpu.
Virsotnei pievienoto bultu galu skaits ir šīs virsotnes pakāpiens. Bultiņai ar vienu bultiņas galu ir astes gals. Astes skaits, kas savienots ar virsotni, ir šīs virsotnes ārējais pakāpe.
Piezīme: Šajā apmācībā netiek apskatīts virsotņu pāra diagramma ar vairākām malām, ja vairākas malas atrodas pretējos virzienos.
Grafika programmatūras attēlojums
Grafiku programmatūrā var attēlot tā, kā tas ir uzzīmēts diagrammā. Grafiku programmatūrā var attēlot arī ar matemātisko matricu (divdimensiju masīvs). Viena no šādām matricām tiek dēvēta par blakusmatriksu.
Adjacency Matrix
Blakus matrica ir kvadrātveida matrica. Rindu virsraksti ir visas virsotnes, kas rakstītas augošā secībā. Kolonnu virsraksti joprojām ir tās pašas virsotnes, kas rakstītas augošā secībā. Matricas rindu vai kolonnu skaitīšana sākas no 1, nevis no nulles kā ar masīviem. Identificējot elementu matricā, rindas numurs vispirms tiek ierakstīts pirms kolonnas numura.
Nenovirzītam grafikam katrs blakus esošās matricas ieraksts (elements) ir malu skaits, kas savieno abas atbilstošās virsotnes. Cilpa jāuzskaita divreiz. Virzītam grafikam katrs ieraksts blakus esošajā matricā ir vai nu to malu skaits, kas atstāj rindas virsotni un ievada atbilstošo kolonnas virsotni, vai ir malu skaits, kas atstāj kolonnas virsotni un ievada atbilstošo rindas virsotni. Izvēli izvēlas programmētājs. Šajā situācijā (abos gadījumos) cilpa joprojām būtu jāuzskaita vienreiz.
Piezīme: Grafiks ir diagramma, kas pati par sevi ir datu struktūra. Blakus matrica ir arī pati sava datu struktūra.
Nenovirzīts grafiks un nepietiekamības matrica
Šīs diagrammas parāda nenovirzītu diagrammu un atbilstošo blakus esošās matricas:
Matricas vadošā diagonāle ir diagonāle no augšas pa kreisi līdz apakšai pa labi. Nenovirzīta matrica ir simetriska attiecībā pret vadošo diagonāli. Matricas ieraksts A rindai un kolonnai C ir 1, kas nozīmē, ka ir viena mala, kas savieno virsotni A un virsotni C. C rindas un kolonnas B matricas ieraksts ir 3, kas nozīmē, ka ir 3 malas, kas savieno virsotni C un virsotni B. Pārējie ieraksti ir līdzīgi izskaidroti.
Rindas ierakstu summa dod atbilstošās virsotnes malu skaitu (grādu). A rindas ierakstu summa ir 2, kas nozīmē, ka 2 malas ir savienotas ar virsotni A. B rindas ierakstu summa ir 6, kas nozīmē, ka 6 malas ir savienotas ar virsotni B. Pārējie ieraksti ir līdzīgi izskaidroti.
Directed Graph un Adjacency Matrix
Šīs diagrammas parāda virzītu grafiku un atbilstošo blakuses matricu:
Virzītā grafika blakusesības matrica ne vienmēr ir simetriska attiecībā pret vadošo diagonāli. Matricas ieraksts A rindai un kolonnai C ir 1, tas nozīmē, ka viena mala atstāj no A virsotnes līdz C virsotnei. C rindas un kolonnas B matricas ieraksts ir 3, kas nozīmē, ka no C virsotnes līdz B virsotnei atstāj 3 malas. Pārējie ieraksti ir līdzīgi izskaidroti.
Kolonnu ierakstu summa dod (kolonnas) virsotnes pakāpienu. Rindas ierakstu summa dod (rindas) virsotnes pakāpi. Ailes A ierakstu summa ir 1, tas nozīmē, ka viena mala ir novirzīta uz A virsotni. B rindas ierakstu summa ir 2, kas nozīmē, ka no B virsotnes atstāj 2 malas. Pārējie ieraksti ir līdzīgi izskaidroti.
Grafika darbības
Datu struktūra, piemēram, diagramma, sastāv no datu vērtību vai objektu kopas, kā arī attiecību starp objektiem, kā arī operācijām (funkcijām) starp objektiem. Attiecības diagrammā norāda malas. Pēc tam diagrammā jāveic vismaz šādas darbības:
blakus (G, x, y)
G nozīmē grafiku. Šī darbība pārbauda, vai mala savieno virsotni x un virsotni y. Ieraksta vērtība un pozīcija matricā norāda malas savienojumu (un tā tipu).
kaimiņi (G, x)
Šī darbība atgriež visu virsotņu sarakstu, kas ir tieši saistītas ar virsotni x. Ieraksta vērtība un pozīcija matricā norāda malas savienojumu.
remove_vertex (G, x)
Šī darbība noņem grafika virsotni x. Ja virsotnei nebija malas, problēmu nav. Tomēr, ja virsotnei bija saites, tad arī saites (malas) būtu jānoņem. Ieraksta vērtība un pozīcija matricā norāda uz konkrētas virsotnes klātbūtni. Ja virsotne tiek noņemta, matrica ir jāpielāgo.
add_vertex (G, x)
Tas pievieno virsotni x, nepievienojot malas, vai aizstāj virsotni, kurai bija malas, bet kas tika noņemta. Ieraksta vērtība un pozīcija matricā norāda uz konkrētas virsotnes klātbūtni. Ja tiek pievienota virsotne, matrica ir jāpielāgo.
add_edge (G, x, y)
Šī darbība pievieno jaunu malu starp virsotni x un virsotni y, ja malas tur nebija. Ieraksta vērtība un pozīcija matricā norāda uz konkrētas malas klātbūtni. Ja tiek pievienota mala, matrica ir jāpielāgo.
noņemt malu (G, x, y)
Šī darbība noņemtu malu starp virsotni x un virsotni y, ja mala būtu. Ieraksta vērtība un pozīcija matricā norāda uz konkrētas malas klātbūtni. Ja mala tiek noņemta, matrica ir jāpielāgo.
get_vertex_value (G, x)
Šī darbība atgriež vērtību, v, kas saistīta ar virsotni, x. Lai to panāktu, virsotņu etiķetēm un to vērtībām ir nepieciešams jaudas apakškopa.
set_vertex_value (G, x, v)
Šī darbība piešķir jaunu vērtību v vērtībai, kas saistīta ar virsotni, x. Lai to panāktu, virsotņu etiķetēm un to vērtībām ir nepieciešams jaudas apakškopa.
Daži diagrammas vērtības saista arī ar to malām. Šādiem grafikiem nepieciešamas šādas papildu darbības:
get_edge_value (G, x, y)
Šī darbība atgriež vērtību, v, kas saistīta ar malu, (x, y). Lai to panāktu, jums ir nepieciešams jaudas apakškopu kopums malām un to vērtībām.
set_edge_value (G, x, y, v)
Šī darbība piešķir jaunu vērtību v vērtībai, kas saistīta ar malu, (x, y). Lai to panāktu, jums ir nepieciešams jaudas apakškopu kopums malām un to vērtībām.
Secinājums
Grafiks ir virsotņu kopums, kas savienots ar malām. Grafiku var novirzīt vai novirzīt. Malas var būt vienvirziena vai virziena. Diagrammā var būt vai nav cilpu. Tas, kas jums jāapgūst pēc tam, ir iestatīts, iestatīts spēks un multiset, kas saistīti ar diagrammām. Pēc tam jums jāapgūst dažāda veida grafiki, piemēram, orientēts grafiks, parasts grafiks, pilnīgs grafiks, divpusējs grafiks, turnīra grafiks, plūsmas tīkla grafiks utt.
Chrys
Par autoru
Chrysanthus Forcha
Matemātikas integrācijas atklājējs no pirmajiem principiem un saistītajām sērijām. Maģistra grāds tehniskajā izglītībā, kas specializējas elektronikā un datoru programmatūrā. BSc Elektronika. Man ir arī zināšanas un pieredze maģistra līmenī skaitļošanas un telekomunikāciju jomā. No 20 000 rakstnieku es biju 37. labākais rakstnieks devarticles.com. Es strādāju šajās jomās vairāk nekā 10 gadus.
Skatīt visas ziņas
