3.1 Негізгі ұғымдар
Анықтама
N доғаға төбелердің
реттелген қосағын сәйкестікке қояды, бұл төбелердің
біріншісі – доғаның басы, ал екіншісі доғаның
соңы деп аталады.
и доғаның басы мен соңын сәйкесінше
beg и және end и деп белгілейміз. Бұл төбелер
мен доға бір біріне түйісті деп айтады.
Мысал. Төмендегі
суретте көрсетілген графтың төбелер жиыны M = {A,B,C,D}, доғалар жиыны N = {1, 2,
3, 4, 5, 6}, ал T түйістілік
бейнелеуі кестемен берілген (сурет 1).

Сурет 1.
Анықтама
2 х – {M, N, T} графтың төбесі
болсын. Бұл төбеге келесі үш санды сәйкестікке қоямыз:
– х төбеге кіретін доғалар
саны,
– х төбеден шығатын доғалар саны,
.
саны – х төбеге кіру жартылай дәрежесі,
саны – х төбеден шығу
жартылай дәрежесі, ал
саны х төбенің дәрежесі деп
аталады. Егер
болса, онда
х оңаша төбе деп аталады. Егер
beg и= end и= х болса, и доға х төбедегі ілмек деп аталады.
Егер beg и= end w және beg w=
end u болса, онда u және w доғалар қарама-қарсы
доғалар деп аталады. Егер beg и= beg w және end w=
end u болса, онда u мен w параллель (еселі) доғалар деп
аталады.
n төбесі бар граф берілсін
. Егер графтың
ілмектері, еселі, қарама-қарсы доғалары болмаса және
кез келген екі төбесі арасында доға бар болса, онда бұл граф толық деп аталады да
арқылы белгіленеді (сурет 2):

Сурет 2.
(M, N', T) жиыны, мұндағы N' – N-ның ішкі жиыны, (M,N, T) графтың дербес
графы деп аталады.
M' –M жиынының қандай
да бір ішкі жиыны болсын. N(M') арқылы үштары M' жиынына
тиісті болған доғалар жиынын белгілейік.
(M',N(M'), T) графы (M,N, T) графтың
ішграфы деп аталады. {M', N', T} графы, мұндағы N'Ì N{M'), (M,N,T) графтың дербес ішграфы
деп аталады..