Бағдарланған графтар

Орграф (Бағдарланған графтар) - бұл граф, оның барлық қабырғаларының бағыты бар. Осындай бағытталған қабырғалар доға деп аталады. Суретте доға көрсеткішпен бейнеленеді (3.6 сурет).

3.6.сурет. Орграф

Қабырғалардан айырмашылығы, доғалар екі теңқұқықты емес төбелерді біріктіреді: олардың біреуі доғаның басы, екіншісі – доғаның соңы деп аталады. Кезкелген қабырғаны – бір-біріне қарсы бағытталған, қос доға деп айтуға болады.

Егер графта қабырғада және доғада болатын болса, онда оны аралас деп айтады.

Бағдарланбаған графтар үшін анықталған негізгі түсініктердің барлығы (инциденттілік, шектестік, қол жеткізушілік, жол ұзындығы және т. б.), орграфтар үшінде күшінде қалады – тек "қабырға" сөзін "доға" сөзіне ауыстырса болғаны. Қабырға және доға арасындағы айырмашылықтармен байланысты аздағанды қоспағанда.

Орграфтағы төбелер дәрежесі – бұл бір емес, қос сан: біріншісі төбеден шығатын доғалар санын, ал екіншісі – кіретін доғалар санын сипаттайды.

Орграфтағы жол – бұл төбелер тізбегі (қайталанбайтын), онда кезкелген екі көршілес төбе шектес, сонымен қатар әрбір төбе біруақытта бір доғаның соңы және келесі доғаның басы болып табылады. Мысалы, 3.6 суреттегі орграфта 2 төбеден 5 төбеге апаратын жол жоқ. Тек көрсеткіштермен берілген бағыттарда ғана орграф бойынша "жылжуға" болады.