Grafiką sudaro viršūnės ir briaunos. Viršūnės yra sujungtos briaunomis pagal tam tikrą savybę - nuolydžio santykį, kuris nusako kraštų rinkinį. Tokiu atveju gali susidaryti kilpos ir atskirtos viršūnės.
Naudojimo instrukcija
1
Tegul pateikiamas grafiko briaunų rinkinys ir duotas santykis, pagal kurį galima nubrėžti kraštą nuo vienos viršūnės prie kitos. Pavyzdžiui, viršūnių {1, 2, 3, 4, 5, 6, 7, 8} viršūnių aibė, dviejų viršūnių x ir y santykis x + y <8.
2
Sukurkite viršūnės gretimybių matricą. Norėdami tai padaryti, pastatykite kvadratinę lentelę, eilučių ir stulpelių skaičius lentelėje sutampa su viršūnių skaičiumi. Tada i-osios eilutės ir j-ojo stulpelio sankirtoje uždėkite 1, jei viršūnės i ir j atitinka nurodytą santykį. Įrašykite 0 i-osios eilutės ir j-tosios stulpelio sankirtoje, jei nėra patenkintų atitinkamų elementų santykio.
Mūsų pavyzdyje pirmoji eilutė užpildyta taip:
1 + 1 <8, taigi 1 eilutės ir 1 stulpelio sankirtoje yra 1
1 + 2 <8, vėl 1
1 + 3 <8, vėl 1
…
1 + 7 <8, neteisinga nelygybė, tada šis lentelės elementas bus 0
1 + 8 <8, vėl 0
3
Norėdami sužinoti briaunų skaičių, suskaičiuokite vienetų skaičių gretimybių matricoje, neišardydami kraštų.
Pavyzdyje buvo gauta simetrinė matrica, todėl pirmiausia vienetai buvo apskaičiuojami virš pagrindinės matricos įstrižainės (pažymėtos mėlyna spalva), o po to vienetai pagrindinėje įstrižainėje (pažymėti raudona spalva). Bendras šonkaulių skaičius yra 12.
4
Sudarykite įvykių (kraštų) matricą. Norėdami tai padaryti, nubrėžkite lentelę, eilučių skaičius joje yra lygus grafiko viršūnių skaičiui, o stulpelių skaičius yra lygus kraštų skaičiui. Įdėkite vienetus į linijas, kurios bus sujungtos kraštu. Kraštai, vedantys iš viršaus į jį, vadinami kilpomis ir pridedami prie matricos galo. Stulpeliuose, atitinkančiuose kilpas, yra tik vienas vienetas, skirtingai nuo kitų kraštų.
5
Dabar nubrėžkite grafiką. Savavališkai išdėstykite viršūnes ant popieriaus ir, naudodamiesi sudarytomis lentelėmis, prijunkite juos su kraštais. Viršūnės, nesujungtos briaunomis, vadinamos izoliuotomis.
Atkreipkite dėmesį
Paveikslėlyje aiškumo sumontuoti šonkauliai. Paprastai šonkaulio svoris užrašomas virš šonkaulio.
