Grafikas susideda iš viršūnių ir kraštų. Viršūnės yra sujungtos briaunomis pagal tam tikrą savybę - kritimo santykį, kuris apibrėžia kraštų rinkinį. Tokiu atveju gali susidaryti kilpos ir izoliuotos viršūnės.
Nurodymai
1 žingsnis
Leiskite pateikti grafiko kraštų rinkinį ir pateikti santykį, kuriuo palei galima brėžti kraštą iš vienos viršūnės į kitą. Pavyzdžiui, viršūnių rinkinys {1, 2, 3, 4, 5, 6, 7, 8}, dvi viršūnės x ir y yra santykyje x + y <8.
2 žingsnis
Sukurkite viršūnės gretimumo matricą. Norėdami tai padaryti, pastatykite kvadratinę lentelę, lentelės eilučių ir stulpelių skaičius sutampa su viršūnių skaičiumi. Tada įdėkite 1 į i-osios ir j-osios kolonos sankirtą, jei viršūnės i ir j tenkina nurodytą santykį. Jei neatitinka atitinkamų elementų santykis, i-osios ir j-osios kolonų sankirtoje uždėkite 0.
Mūsų pavyzdyje pirmoji eilutė užpildoma 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ė, todėl šis lentelės elementas bus 0
1 + 8 <8, vėl 0
3 žingsnis
Norėdami sužinoti kraštų skaičių, suskaičiuokite jų skaičių gretimumo matricoje, nedubliuodami kraštų.
Pavyzdyje buvo gauta simetriška matrica, todėl pirmiausia suskaičiavome virš pagrindinės matricos įstrižainės (pažymėtos mėlyna spalva), o paskui - ant pagrindinės įstrižainės (pažymėtos raudonai). Bendras šonkaulių skaičius yra 12.
4 žingsnis
Sukurkite įvykių (kraštų) matricą. Norėdami tai padaryti, nubrėžkite lentelę, joje esančių eilučių skaičius yra lygus grafo viršūnių skaičiui, o stulpelių skaičius yra lygus kraštų skaičiui. Įdėkite vienetus tose linijose, kurios bus sujungtos kraštu. Kraštai, vedantys iš viršūnės į ją, vadinami kilpomis ir pridedami prie matricos galo. Stulpeliuose, atitinkančiuose kilpas, yra tik vienas vienetas, priešingai nei likusiuose kraštuose.
5 žingsnis
Dabar pieškite grafiką. Bet kokiu būdu uždėkite viršūnes ant popieriaus ir sujunkite jas su kraštais, naudodamiesi sukurtomis lentelėmis. Viršūnės, kurios nėra sujungtos kraštais, vadinamos izoliuotomis.
