Graaf koosneb tippudest ja servadest. Tipud on ühendatud servadega vastavalt teatud omadusele - esinemissuhtele, mis määrab servade hulga. Sel juhul võivad tekkida silmused ja eraldatud tipud.
Juhised
Samm 1
Olgu antud graafi servade kogum ja antud suhe, mida mööda on võimalik ühest tipust teise serva tõmmata. Näiteks on tippude hulk {1, 2, 3, 4, 5, 6, 7, 8}, kaks tippu x ja y suhe x + y <8.
2. samm
Ehitage tipu külgnemismaatriks. Selleks koostage ruuduline tabel, tabeli ridade ja veergude arv langeb kokku tippude arvuga. Seejärel pange 1 i-nda ja j-nda veeru ristumiskohta, kui tipud i ja j vastavad antud suhtele. Pange 0 i-nda ja j-nda veeru ristumiskohta, kui vastavate elementide suhe pole täidetud.
Meie näites täidetakse esimene rida järgmiselt:
1 + 1 <8, seega on 1. rea ja 1. veeru ristumiskohas 1
1 + 2 <8, jälle 1
1 + 3 <8, jälle 1
1 + 7 <8, vale ebavõrdsus, seega on see tabeli element 0
1 + 8 <8, jälle 0
3. samm
Servade arvu väljaselgitamiseks lugege külgmaatriksis olevate servade arv servi dubleerimata.
Näites saadi sümmeetriline maatriks, nii et loendasime kõigepealt maatriksi peamise diagonaali kohal olevad (tähistatud sinisega) ja seejärel põhidiagonaali (punasega tähistatud). Ribide koguarv on 12.
4. samm
Koostage juhtumite (servade) maatriks. Selleks joonistage tabel, selles olevate ridade arv on võrdne graafi tippude arvuga ja veergude arv võrdub servade arvuga. Pange üksused nendele joontele, mis on ühendatud servaga. Tipust selleni viivaid servi nimetatakse silmusteks ja lisatakse maatriksi lõppu. Silmustele vastavas veerus on vastupidiselt ülejäänud servadele ainult üks üksus.
5. samm
Nüüd joonista graafik. Asetage tipud paberile mis tahes viisil ja ühendage need koostatud tabelite abil servadega. Tippusid, mida servad ei ühenda, nimetatakse isoleerituteks.
