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

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

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

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