Графтар теориясы соңғы уақытта ғылым мен техниканың түрлі салаларында кеңінен қолданылады. Графтар теориясы алгоритмдеудің түрлі есептерін шешуге мүмкіндік беретін элект ронды есептеуіш машинаның пайда болуымен қарқынды дамыды.
Граф – бұл екі жиынның жиынтығы: нүктелер жиыны мен сол нүк телердің кейбірін жұптап қосатын сызықтар жиыны. Нүктелер жи ыны графтың төбелері (түйіндері) деп аталады. Граф төбелерін қо сатын сызықтар жиыны графтың қабырғалары (доғалар) деп аталады.
Бағытталмаған граф – барлық қабырғаларының бағыты жоқ граф, яғни қабырғаларына бағыт берілмеген.
Аралас граф – бағытталған қабырғадан да, бағытталмаған қабырғадан да тұратын граф.
Ілмек деп графтың өзіне өзін қосатын қабырғаны айтамыз. Егер екі төбені қосатын қабырға бар болса, онда ол төбелер көршілес деп аталады.
Бірдей төбелер жұбын қосатын қабырғаларды еселі деп атайды. Қарапайым граф – ілмегі де, еселі қабырғалары да жоқ граф. Мультиграф – кез келген екі төбесі бір қабырғадан артық қабырға мен қосылған граф.
Граф маршруты дегеніміз – көршілес төбелерді қосатын сол төбе лер мен қабырғалардың соңғы кезектелген тізбегі.
Граф маршруты дегеніміз – көршілес төбелерді қосатын сол төбе лер мен қабырғалардың соңғы кезектелген тізбегі.
Егер бастап қы және соңғы төбелер әр түрлі болатын болса, онда маршрут ашық деп аталады, ал кері жағдай да маршрут тұйық талған деп аталады.
Егер маршрут төбелері әр түрлі болса, онда ол маршрут тізбек деп аталады.
Егер ашық тізбекке кіретін төбелер әр түрлі болатын болса, онда ол тізбек жол деп аталады.
Егер тұйықталған тізбекке кіретін төбелер (ақырғы төбе ден басқа) әр түрлі болса, онда ол тізбек цикл деп аталады.
Егер графта деп кез келген екі төбе үшін оларды қосатын жол бар бол са, онда ол байланысқан граф деп аталады.
Төбе салмағы – сол төбеге сәйкес (құн, өткізу қабілеті және т.б.) қойыл ған сан (нақты, бүтін немесе бөлшек). Қабырға салмағы (ұзындығы) – қабырғаға ұзындық, өткізу қабілеті және т.б. қатынаста берілетін сан немесе бірнеше сан.
Өлшенген граф – әрбір қабырғаға қандай да бір мән (қабырға салмағы) қой ылған граф.
