График чокулардан жана четтерден турат. Чокулар белгилүү бир касиетке ылайык кырлар менен туташтырылган - четтердин жыйындысын аныктоочу инциденттик байланыш. Бул учурда циклдер жана обочолонгон чокулар пайда болушу мүмкүн.
Нускамалар
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-кадам
Эми график тарт. Кандайдыр бир жол менен кагазга чокуларды жайгаштырып, курулган таблицалардын жардамы менен аларды четтери менен байланыштырыңыз. Четтери менен туташпаган вертикалдар обочолонгон деп аталат.
