Графтар және ағаштар

Графтар теориясының негізгі ұғымдарымен танысайық. «Граф» ұғымы «графо» сөзінен шыққан, ол жазамын деген ұғымды білдіреді. «График», «биография», «голография», деген сөздердің де түбірі сол. Граф ұғымын мысал арқылы түсіндірейік.

Топтар арасындағы сайысты қарасырайық. Үстел тенисі бойынша топ біріншілігіне 6 студент қатыссын: Айгүл, Бекжан, Тимур, Гүлім, Дамир, Еркін. Біріншілік айналу жүйесі бойынша өткізіледі – жарысқа қатысушы әрбір адам қалғандарымен бір-бір рет ойнап шығады. Бұған дейін бірнеше ойын өткізілген болатын: Айгүл Бекжанмен, Гүліммен Еркінмен; Тимур, бұрын айтылғандай, Айгүлмен және Гүліммен; Тимур – Гүліммен, Дамир – Тимурмен және Еркін – Айгүлмен және Тимурмен ойнаған. Бұған дейін неше ойын ойналған және тағы неше ойын қалды?

Талқылау. Берілген есепті схема түрінде кескіндейік. Қатысушыларды нүктемен кескіндейміз: Айгүлді – А нүктесімен, Бекжанды – Б нүктесімен т.с.с. Егер қатысушылардың екеуі ойнап кеткен болса онда оларды кескіндейтін нүктені кесінділермен қосамыз. Сонда 1-суретте көрсетілгендей схема шығады.