Graafik koosneb tippudest ja servadest. Tippe ühendavad servad vastavalt teatud omadusele - esinemissagedusele, mis määratleb servade komplekti. Sel juhul võivad moodustuda silmused ja isoleeritud tipud.
Kasutusjuhend
1
Olgu antud graafi servade komplekt ja antud seos, mille abil saab serva tõmmata ühest tipust teise. Näiteks tippude kogum {1, 2, 3, 4, 5, 6, 7, 8}, kaks tippu x ja y on suhtega x + y <8.
2
Koostage tipu külgnevuse maatriks. Selleks ehitage ruudukujuline tabel, tabeli ridade ja veergude arv vastab tippude arvule. Seejärel pange 1 i-nda rea ja j-nda samba ristumiskohta, kui tipud i ja j vastavad antud suhtele. Pange 0 i-nda rea ja j-nda veeru ristumiskohale, kui vastavate elementide suhe pole rahul.
Meie näites on esimene rida täidetud järgmiselt:
1 + 1 <8, nii et 1. rea ja 1. veeru ristumiskohas on 1
1 + 2 <8, jälle 1
1 + 3 <8, jälle 1
…
1 + 7 <8, vale ebavõrdsus, siis on see tabeli element 0
1 + 8 <8, jälle 0
3
Servade arvu teadasaamiseks loendage külgnevusmaatriksis olevate ühikute arv, jätmata samal ajal servi lahti.
Näites saadi sümmeetriline maatriks, seetõttu arvutati kõigepealt ühikud maatriksi peamise diagonaali kohal (tähistatud sinisega) ja seejärel peamise diagonaali ühikud (tähistatud punasega). Ribide koguarv on 12.
4
Koostage juhtumite (servade) maatriks. Selleks joonistage tabel, ridade arv selles võrdub graafi tippude arvuga ja veergude arv on võrdne servade arvuga. Pange üksused servaga ühendatavatesse ridadesse. Ülevalt selle poole viivad servad nimetatakse silmusteks ja lisatakse maatriksi lõppu. Silmustele vastavates veergudes on erinevalt teistest servadest ainult üks üksus.
5
Nüüd joonistage graafik. Korraldage tipud paberil meelevaldselt ja ühendage need servadega, kasutades konstrueeritud tabeleid. Tippe, mida servad ei ühenda, nimetatakse isoleerituks.
Pöörake tähelepanu
Joonis näitab selguse saamiseks ribisid. Tavaliselt kirjutatakse ribi kaal üle ribi.
