Ekvivalences attieksme, Deikstras algoritms

1. UZDEVUMA NOSTĀDNE

38. variants
Variants ietver 2 uzdevumus. Katra uzdevuma atrisināšanai jāizstrādā programma, kas veic datu ievadi prasītajā formā, atrisina uzdevumu un izvada rezultātu.
Uzdevumi:
1) Galīgā kopā A = {a,#,2,y,3} tiek uzdota attieksme R; to uzdot ar matricu. Pēc matricas ievades parādīt atbilstošo kortežu sarakstu.Noteikt vai dotā attieksme ir ekvivalence,( dot atbildi par visām 3.attieksmēm).
2) Deikstras algoritma realizācija – atrast īsāko ceļu grafā. Jābūt iespējai izvēlēties ceļu sākuma un beigu virsotnes. Grafu ievada ar blakus virsotņu matricu( 1 vietā ievada loka svarus), grafa virsotņu skaits n:9
2. TEORĒTISKAIS PAMATOJUMS

2.1. DEIKSTRAS ALGORITMS

2.1.1. Grafi

Grafs ir matemātisks objekts. Tā apzīmēšanai izmanto burtu G. Tas sastāv no divām kopām – V un Q. Kopa V ir grafa virsotņu kopa. Tajā iekļautas visas apskatāmā grafa virsotnes. Kopa Q ir grafa virsotņu pāru kopa jeb loku vai šķautņu kopa. Tātad grafa pilns apzīmējums ir G(V,Q).

Zīmējot grafu, virsotnes zīmē kā apļus, bet lokus zīmē kā līnijas vai bultas starp virsotņu, kuras tas savieno, apļiem.
Pastāv divi galvenie grafu veidi – neorientēts un orientēts.
Neorientētā grafā nav svarīgi, kura virsotne katram lokam ir pirmā un kura otrā – loku zīmē kā līniju un kopas Q elementi ir nesakārtoti virsotņu pāri.
Orientētā grafā ir svarīgi, kura virsotne katram lokam ir pirmā un kura otrā – loku zīmē kā bultu no pirmās virsotnes uz otro un kopas Q elementi ir sakārtoti virsotņu pāri.



…