График шыңдар мен шеттерден тұрады. Төбелер шеттермен белгілі бір қасиетке сәйкес біріктіріледі - жиектер жиынын анықтайтын түсу қатынасы. Бұл жағдайда ілмектер мен оқшауланған шыңдар пайда болуы мүмкін.
Нұсқаулық
1-қадам
Графиктің жиектер жиыны берілсін және оның бойымен бір шыңнан екінші шыңға жиек жүргізуге болатын қатынас берілсін. Мысал ретінде, {1, 2, 3, 4, 5, 6, 7, 8} шыңдарының жиыны, екі x және y шыңдары x + y <8 қатынасында болады.
2-қадам
Төбеге көршілес матрица құрыңыз. Ол үшін квадрат кесте тұрғызыңыз, кестедегі жолдар мен бағандардың саны төбелер санымен сәйкес келеді. Содан кейін i және j шыңдары берілген қатынасты қанағаттандырса, i-ші қатар мен j-ші бағанның қиылысына 1 қойыңыз. Егер тиісті элементтер үшін қатынас орындалмаса, i-ші қатар мен j-ші бағанның қиылысында 0 қойыңыз.
Біздің мысалда бірінші жол келесідей толтырылады:
1 + 1 <8, сондықтан 1-жол мен 1-бағанның қиылысында 1 болады
1 + 2 <8, тағы 1
1 + 3 <8, тағы 1
1 + 7 <8, дұрыс емес теңсіздік, сондықтан кестенің бұл элементі 0 болады
1 + 8 <8, тағы 0
3-қадам
Шеттер санын білу үшін, шеттерін қайталамай, көршілестік матрицасында олардың санын санаңыз.
Мысалда симметриялы матрица алынды, сондықтан біз алдымен матрицаның негізгі диагоналінен жоғары (көкпен белгіленген), содан кейін басты диагональдағы (қызылмен белгіленген) санадық. Жалпы қабырға саны - 12.
4-қадам
Оқиғалар матрицасын құрыңыз (шеттері). Ол үшін кесте салыңыз, ондағы жолдар саны графиктегі төбелер санына, ал бағандар саны жиектерге тең. Шеттермен біріктірілетін бірліктерге қойыңыз. Төбеден оған апаратын шеттер цикл деп аталады және матрицаның соңына қосылады. Ілмектерге сәйкес бағандарда қалған шеттерден айырмашылығы тек бір бірлік бар.
5-қадам
Енді график сыз. Төбелерді қағазға кез-келген жолмен орналастырыңыз және оларды құрастырылған кестелер көмегімен шеттермен байланыстырыңыз. Шеттермен байланыспаған тігінен оқшауланған деп аталады.
