Багытталган жана Багытсыз График
График – бул чокулардын жана четтердин жыйындысынан турган математикалык түзүлүш. График кээ бир шилтемелер (четтери менен көрсөтүлгөн) аркылуу туташкан объекттердин жыйындысын (чокулары менен көрсөтүлгөн) билдирет. Математикалык белгилерди колдонуу менен графикти G менен көрсөтсө болот, мында G=(V, E) жана V – чокулардын жыйындысы, E – четтердин жыйындысы. Багытталбаган графикте чокуларды бириктирген четтери менен байланышкан багыт жок. Багытталган графикте чокуларды бириктирген четтери менен байланышкан багыт бар.
Багытсыз график
Мурда айтылгандай, багытталбаган график – бул графиктин чокуларын бириктирген четтеринде багыт жок график.1-сүрөттө V={V1, V2, V3} чокуларынын жыйындысы менен багытталбаган график көрсөтүлгөн. Жогорудагы графиктин четтеринин жыйындысы V={(V1, V2), (V2, V3), (V1, V3)} түрүндө жазылышы мүмкүн. Ошондой эле, четтердин бир багыты жок болгондуктан, четтердин жыйындысын V={(V2, V1), (V3, V2), (V3, V1)} деп жазууга эч кандай тоскоолдук жок экенин белгилей кетүү керек. Демек, багытталбаган графиктин четтери иреттелген жуптар эмес. Бул багытталбаган графиктин негизги мүнөздөмөсү. Багытталбаган графиктер чокулары менен берилген объекттердин ортосундагы симметриялык мамилелерди көрсөтүү үчүн колдонулушу мүмкүн. Мисалы, шаарлардын жыйындысын бириктирген эки тараптуу жол тармагы багытталбаган графиктин жардамы менен көрсөтүлүшү мүмкүн. Шаарлар графиктин чокулары менен, ал эми четтери шаарларды бириктирген эки тараптуу жолдор менен көрсөтүлүшү мүмкүн.
Багытталган график
Багытталган график – бул графиктин чокуларды байланыштырган четтери бир багытка ээ болгон график. 2-сүрөттө V={V1, V2, V3} чокуларынын жыйындысы менен багытталган график көрсөтүлгөн. Жогорудагы графиктин четтеринин жыйындысы V={(V1, V2), (V2, V3), (V1, V3)} түрүндө жазылышы мүмкүн. Багытталбаган графиктин четтери иреттелген жуптар. Формалдуу түрдө багытталган графиктеги e чети иреттелген e=(x, y) түгөйү менен көрсөтүлүшү мүмкүн, мында х - чоку, ал четинин башталышы, булагы же баштапкы чекити деп аталат, ал эми y чокусу - чекит деп аталат., аяктоочу чоку же терминалдык чекит. Мисалы, бир жактуу жолдорду колдонуу менен шаарларды бириктирген жол тармагы багытталбаган графиктин жардамы менен көрсөтүлүшү мүмкүн. Шаарлар графикте чокулары менен көрсөтүлүшү мүмкүн, ал эми багытталган четтери жолдогу кыймылдын багытын эске алуу менен шаарларды бириктирген жолдорду көрсөтөт.
Багытталган график менен багытсыз графиктин ортосунда кандай айырма бар?
Багытталган графикте жээк иреттелген жуп болуп саналат, мында иреттелген жуп эки чокуну бириктирген кырдын багытын билдирет. Башка жагынан алганда, багытталбаган графикте чети ирээтсиз жуп болуп саналат, анткени чек менен байланышкан багыт жок. Багытталбаган графиктер объекттердин ортосундагы симметриялык мамилелерди көрсөтүү үчүн колдонулушу мүмкүн. Багытталбаган графиктеги ар бир түйүндүн даражасы жана сырткы даражасы бирдей, бирок бул багытталган график үчүн туура эмес. Багытталбаган графикти көрсөтүү үчүн матрицаны колдонгондо, матрица дайыма симметриялык графикке айланат, бирок бул багытталган графиктер үчүн туура эмес. Багытталбаган графикти ар бир четин карама-каршы багытта бараткан эки багытталган четтери менен алмаштыруу аркылуу багытталган графикке айландырууга болот. Бирок, багытталган графикти багытталбаган графикке айландыруу мүмкүн эмес.
