Grafiks sastāv no virsotnēm un malām. Virsotnes ir savienotas ar malām atbilstoši noteiktai īpašībai - sastopamības attiecībai, kas nosaka malu kopu. Šajā gadījumā var veidoties cilpas un izolētas virsotnes.
Instrukcijas
1. solis
Ļaujiet dot grafika malu kopu un norādīt attiecību, pa kuru ir iespējams 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. solis
Veidojiet virsotnes blakus esošās matricas. Lai to izdarītu, izveidojiet kvadrātveida tabulu, tabulas rindu un kolonnu skaits sakrīt ar virsotņu skaitu. Tad i-tās rindas un j-tās kolonnas krustojumā ielieciet 1, ja virsotnes i un j atbilst norādītajai attiecībai. Ievietojiet 0 i-tās un j-s kolonnas krustojumā, ja attiecīgo elementu attiecība nav izpildīta.
Mūsu piemērā pirmā rinda tiek aizpildīta šā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 nevienlīdzība, tāpēc šis tabulas elements būs 0
1 + 8 <8, atkal 0
3. solis
Lai uzzinātu malu skaitu, saskaita to skaitu blakus esošajā matricā, nedublējot malas.
Šajā piemērā tika iegūta simetriska matrica, tāpēc vispirms mēs saskaitījām tos, kas atrodas virs matricas galvenās diagonāles (atzīmēti ar zilu krāsu), un pēc tam tos, kas atrodas uz galvenās diagonāles (atzīmēti ar sarkanu). Kopējais ribu skaits ir 12.
4. solis
Veidojiet incidentu (malu) matricu. Lai to izdarītu, uzzīmējiet tabulu, tajā esošo rindu skaits ir vienāds ar virsotņu skaitu diagrammā, un kolonnu skaits ir vienāds ar malu skaitu. Ievietojiet vienības tajās līnijās, kuras savienos mala. Malas, kas ved no virsotnes uz to, sauc par cilpām un tiek pievienotas matricas galā. Kolonnās, kas atbilst cilpām, atšķirībā no pārējām malām ir tikai viena vienība.
5. solis
Tagad uzzīmējiet grafiku. Jebkurā veidā novietojiet virsotnes uz papīra un savienojiet tās ar malām, izmantojot izveidotās tabulas. Virsotnes, kas nav savienotas ar malām, sauc par izolētām.
