I боб. Дастлабки тушунчалар

I БОБ. ДАСТЛАБКИ ТУШУНЧАЛАР
1.1. Метрик графлар бўйича асосий тушунчалар

Сўнгги йилларда тармоқланган сохаларда дифферециал тенгламалар учун чегаравий масала ўрганишга катта қизиқиш бўлмокда. Бунга асосий сабаб, бундай масалалар замонавий физика ва теxниканинг кўплаб актуал муаммоларини ўрганишда, тармокланган мезоскопик сохалар тўлкин жараёнларини ўрганишда бундай чегаравий масалалар математик мадел вазифасини бажаради. Бу ишни ўрганишдан бизнинг асосий максадимиз, метрик графларда тўлкин тенгламалари, xусусан каср тартибли тенгламалар учун чегаравий масалаларни қўйиш ва бу масалаларнинг ечимини тадқиқ килиш, олинган натижаларнинг баъзи тадбикларини таҳлил килишдан иборат.

1736- йилда Л. Эйлер томонидан қизиқарли амалий масалалардан бири ҳисобланган Кёнигсберг кўприклари хакидаги масаланинг қўйилиши ва ечилиши графлар назариясининг пайдо бўлишига асос бўлди. Кёнигсберг шахридаги Прегел дарёси устида курилган етти кўприкнинг жойлашувидир.
XIX асрнинг ўрталарида графлар назарияси билан боғлик тадкикотлар Г. Кирxгоф ва А. Кели ишларида пайдо бўлди. “Граф” ибораси Д. Кёниг томонидан 1936-йилда графлар назариясига бағишланган дастлабки дарсликларда учрайди.
Графлар назарияси бўйича тадкикотлар натижалари инсон фаолиятининг турли сохаларида кўлланилади. Масалан, бошкотирмаларни ҳал қилишда, қизиқарли ўйинлар, йўллар, электр занжирлари, интеграл сxемалар, бошқариш сxемаларини лойиҳалаштириш, компьютерлар учун программаларни тадқиқ қилиш ва бошқа сохаларда кенг қўлланилади.
Аввало, графнинг абстракт математик тушунча сифатидаги таърифини келтирамиз. Бизга бўш бўлмаган тўплам берилган бўлсин. Унинг ва элементларидан тузилган кўринишдаги барча жуфтликлар (кортежлар) тўпламини ( тўпламнинг ўз-ўзига Декарт кўпайтмасини) билан белгилаймиз.
Граф деб шундай жуфтликка айтиладики, бу ерда ва эса ( , ) кўринишдаги жуфтликлар кортежи булиб, тўпламнинг элементларидан тузилган тўплам.
Графларнинг турлича берилиш усуллари мавжуд. Графнинг абстракт математик таърифи унинг берилиш усулларидан биридир. Графнинг абстракт математик таърифи уни тасаввур килиш, англаш, унинг xоссаларини ўрганиш ва бу xоссаларни амалда қўллаш жараёнида баъзи қийинчиликлар туғдириши табиийдир. Шунинг учун графнинг бошқа берилиш усулларидан хам фойдаланиш мақсадга мувофиқ.
Графнинг учларини текисликда ёки фазода нуқталар билан, қирраларини эса мос учларини туташтирувчи узлуксиз чизиқлар билан ифодалаб, қандайдир диаграммага-графнинг кўргазмали тасвирига эга бўламиз.
Агар бирор диаграммада графнинг учларига мос келувчи нуқталар устма-уст тушмаса, қирраларга мос келувчи чизиқлар, четки нуқталарни ҳисобга олмаганда, умумий нуқталарга эга бўлмаса, бундай диаграмма графнинг геометрик ифодаланиши дейилади. Шуни таъкидлаш керакки, битта граф турлича геометрик ифодаланиши мумкин.
Агар графнинг учларига кандайдир белгилар, масалан, сонлари мос қўйилган бўлса, у белгиланган граф дейилади.
- учлари сони га тенг бўлган белгиланган, сиртмоксиз ва каррали кирраларсиз граф бўлсин.
Елементлари

Кўринишда аниқланган ( ) матритсани графнинг учлари қўшнилиги матритсаси деб аталади.