Назарияи графҳо

Назарияи графҳо як фасли математикаро гӯянд, ки объектҳояшро ба тариқи геометрӣ меомӯзад. Мафҳуми асосии ин назария граф мебошад. Граф тавассути маҷмуи қуллаҳо (нуқтаҳо) ва маҷмӯи теӯаҳо (бандҳо)-е, ки баъзе аз ҷуфтҳои (ё ҳаман) қуллаҳоро мепайванданд, муайян карда мешавад. Ҷуфтҳои қуллаҳо ба ҳамдигар бо якчанд теғахо пайваст шуда метавонанд. Масалан, маҷмӯи шаҳрҳои Тоҷикистон (қуллаҳои граф) ва роҳҳое, ки ин шаҳр- ҳоро мепайванданд (теғаҳои граф); элементҳои схемаи электрӣ (қулла) ва симҳои онҳоро пайвасткунанда (теғаҳо). Вазифаи асосии Назарияи графҳоро интихоб намуданн теғаҳои оптималӣ (масалан, роҳҳои кӯтоҳтарин) ташкил медиҳад. Агар дар теғаҳо самт ва ё тартиби аз қуллаҳо гузаштан муай­ян шуда бошад, граф самтдор номи­да мешавад.

Яке аз корҳои аввалин дар соҳаи Назарияи графҳо тадқиқоти Л. Эйлер доир ба ҳалли масъала ва мисолҳои математикаи шавқовар аст. Аввалин натиҷаҳои дақиқ доир ба Назарияи графҳо дар нимаи якуми асри 20 дар зимни тартиб додани занҷирҳои алектрӣ, ҳисоб кардани моддаҳои химиявви навъи пайвастҳои молекулавиашон гуно- гун ба вуҷуд омаданд. Солҳои 50 асри 20 вобаста ба инкишофи кибернетика ва техникаи ҳисоббарорӣ Назарияи графҳо бо суръат тараққӣ намуд ва бо матери­алу усулҳои нав бой гардид. Назарияи графҳо дар назарияи программасозӣ, дар бунёди компютерҳо, омӯзиши про­сессҳои физики, химиявӣ ва техно­логӣ, ҳалли масъалаҳои баплангирй, дар забоншиносӣ ва тадқиқоти сотси­ологӣ истифода бурда мешавад. Назарияи графҳо бо гопология, алгебра, таҳлили ком- бинаторӣ, назарияи ададҳо ва дигар соҳаҳои математика робитаи мустаҳкам дорад.

Ад.: Б е р ж К., Теория графов её при­менения. пер. с франтс.. М., 1962; Оре О., Графы и их применение, пер. с англ., М„ 1965; Басакер Р., С а а т и Т., Конечные графы и сети, пер. с англ., М.,