Grafiks sastāv no virsotnēm un malām. Virsotnes ir savienotas ar malām saskaņā ar noteiktu īpašību - sastopamības attiecību, kas nosaka malu kopu. Šajā gadījumā var veidoties cilpas un izolētas virsotnes.
Lietošanas instrukcija
1
Ļauj dot grafika malu kopu un attiecību, ar kuru var novilkt malu no vienas virsotnes uz otru. Piemēram, virsotņu kopa {1, 2, 3, 4, 5, 6, 7, 8}, divas virsotnes x un y ir attiecībās x + y <8.
2
Veidojiet virsotnes blakus esošu matricu. Lai to izdarītu, izveidojiet kvadrātveida tabulu, tabulas rindu un kolonnu skaits atbilst virsotņu skaitam. Tad ielieciet 1 i-tās rindas un j-tās kolonnas krustojumā, ja virsotnes i un j atbilst dotajai attiecībai. I-tās rindas un j-tās kolonnas krustojumā ielieciet 0, ja attiecīgo elementu attiecība nav apmierināta.
Mūsu piemērā pirmo rindu aizpilda šādi:
1 + 1 <8, tātad 1. rindas un 1. kolonnas krustojumā ir 1
1 + 2 <8, atkal 1
1 + 3 <8, atkal 1
…
1 + 7 <8, nepareiza nevienādība, tad šis tabulas elements būs 0
1 + 8 <8, atkal 0
3
Lai uzzinātu malu skaitu, saskaitiet vienību skaitu blakus esošajā matricā, vienlaikus neizvelkot malas.
Šajā piemērā tika iegūta simetriska matrica, tāpēc vispirms vienības tika aprēķinātas virs matricas galvenās diagonāles (apzīmētas ar zilu krāsu) un pēc tam vienības uz galvenās diagonāles (apzīmētas ar sarkanu krāsu). Kopējais ribu skaits ir 12.
4
Izveidojiet incidentu (malu) matricu. Lai to izdarītu, uzzīmējiet tabulu, tajā esošo rindu skaits ir vienāds ar diagrammas virsotņu skaitu, un kolonnu skaits ir vienāds ar malu skaitu. Ielieciet vienības līnijās, kuras savienos ar malu. Malas, kas ved no augšas uz to, sauc par cilpām un pievieno matricas beigām. Kolonnās, kas atbilst cilpām, atšķirībā no citām malām ir tikai viena vienība.
5
Tagad uzzīmējiet diagrammu. Patvaļīgi sakārtojiet virsotnes uz papīra un savienojiet tās ar malām, izmantojot konstruētās tabulas. Malas, kuras nav savienotas ar malām, sauc par izolētām.
Pievērsiet uzmanību
Attēlā skaidrības labad redzamas ribas. Parasti ribas svaru raksta virs ribas.
