5В060200 «Информатика» мамандығына арналған

• 
  Графтар-логикалық структурасы,анықтамасы,орграф ұғымы
  
• 
  Бұтақтар
  

• 
  Анықтамасы
  
• 
  Екілік бинарлы бұтақтар
  
• 
  ЭЕМ-дегі жазылуы
  
• 
  Балансты бұтақтар
  

Графтар.

Бұл - күрделі объектінің байланысы мен қасиеттерін көрсететін, күрделі, сызықты емес көпбайланысты динамикалық структура.

Көпбайланысты структураның қасиеттері:

1. Әрбір элементке (түйін, төбе) саны еркін алынған сілтемелер болуы мүмкін.

2. Әрбір элемент кез келген басқа элементпен кез келген рет байланысады.

3. Әрбір байланыстырушы жасаушының (қабырға, доға) бағыты және салмағы болады.

Граф түйіндерінде объектінің элементтері туралы ақпарат болады. Түйіндердің арасындағы байланыс граф қабырғаларымен беріледі. Қабырғалардың бағыты көрсетілсе, оны бағдарлы қабырға, егер бағыты көрсетілмесе бағдарсыз қабырға деп аталады.

Барлық қабырғалары бағдарлы болса, ондай графты орграф дейді, егер байланыс қабырғалары бағытталмаған болса - бағдарсыз граф, егер бағытты және бағытсыз қабырғалары бар болса - аралас граф дейді. Қабырғасыз графты нөл граф дейді.

Бағдарлы графтың түйінге енетін қабырғалар саны түйін кірісінің жартыдәрежесі, ал шығатын қабырғалар саны шығыс жарты дәрежесі деп аталады. Графтың кіріс, шығыс қабырғалар саны кез келген болады, болмауы да мүмкін.

Егер графтың қабырғаларына қандай да бір мәндер сәйкес болса, онда графты және қабырғаларды өлшенген дейді. Графтың параллель қабырғалары бар болса, оны мультиграф дейді. Басқа жағдайда жай граф дейді.

Графқа жол - қабырғалармен байланыстырылған түйіндер тізбегі. Жол элементарлы жол деп аталады, егер графтың қабырғалары әр түрлі болса, егер төбелері әр түрлі болса, онда жол жай жол деп аталады. Түйіннің өзіне қайту жолы бар болса, онда циклдық жол деп аталады. Графтың екі түйіні қатарлас деп аталады егер оның бір түйінінен екінші түйініне жол бар болса. Түйін инцидентті деп аталады, егер ол граф төбемі болса, яғни қабырға осы түйінге бағытталса.

Ағаштар.

Келесі қасиеттері бар графтарды ағаштар дейді:

- Басқа ешбір элемент сілтемейтін жалғыз элементі (түйін, төбе) бар болса және ол түбір деп аталады.

- Түбірден бастап элементтерде бар белгілі бір көрсеткіштер тізбегі бойымен структураның басқа кез келген элементіне қатынас жасауға болса.

- Түбірден басқа әрбір элементке тек бір ғана сілтеме жасалса, яғни әрбір элементтің жалғыз адресі болса.

Бағдарлы ағаш деп түбір деп аталатын бір төбесі бар, кіріс жартыдәрежесі нөлге тең, басқа кіріс жартыдәрежелері 1-ге тең болатын циклдік графты айтады. Бұл ағаштардың ең болмағанда бір төбесі бар болады. Аластатылған, дара төбе де бағдарлы ағаш деп аталады.

Шығыс жартыдәрежесі нөлге тең бағдарлы ағаштың төбесі ілінген, соңғы төбе деп аталады. Одан басқа төбелері тармақталу төбелері деп аталады. Түбірден әлдебір төбеге дейінгі жолдың ұзындығы осы төбенің деңгейі - немесе ярус номері деп аталады. Түбір деңгейі нөлге тең болады, ал басқа төбелердің деңгейлері түбір мен төбелердің арасындағы ұзындықпен анықталады, немесе төбелер деңгейлерінің номерлерінің модулі бойынша айырмасына тең.

Бинарлы ағаштар.

m - арлы ағаштар бар, олар әрбір төбелердің шығыс жартыдәрежесі m-нен кіші не тең болатын ағаштар. m=0,1,2,3,... Егер әрбір төбеніңғ шығыс жартыдәрежесі m-ге немесе нөлге тең болса, оны толық ағаш немесе m - арлы ағаш дейді.

m=2 болғанда ағаштарды бинарлы немесе толық бинарлы дейді.

Кез келген ағашты, тоғайларды бинарлы ағашпен көрсету.

1. Әрбір түйінде үлкен ұлға (вертикальды жалғау) тек бір ғана бұтақ қалдыру.

2. Горизонтальды қабырғалармен бір әкелі барлық бауырларды жалғастыру.

3. Сонда мына ережемен ағаш қайта құрылады: сол жақтағы ұл - берілген төбенің астында орналасқан төбе, оң жақ ұл - берілген төбенің оң жағында орналасқан төбе, яғни яруста орналасқан төбе.

4. Ағашты вертикальды бұтақтары сол жақтағы ұлдарды, горизонтальды бұтақтары оң жақтағы ұлдарды көрсететіндей етіп төңкеру.

Нәтижесінде кез келген ағашты бинарлы ағашқа алмастырғанда түбірлі төбеге ілінген сол жақтағы ішкі ағаш түріндегі ағаш алынады.

Балансталған ағаш. Бинарлы ағашта іздеу операциясын жылдамдатуға көмектеседі. Балансты ағаш деп әрбір түйін үшін оның екі ішкі ағашының биіктігінің айырмашылығы біреу болса ғана айтады.

Өзін тексеру сұрақтары

1. 
   Графтар қайда қолданылады?
   
2. 
   Бұтақ деген не?
   

1. 
   Е. Бидайбеков, Е. Медеуов, А. Ниязбаев. Информатика бастамалары (алгоритмдеу). Алматы, 1990ж.
   
2. 
   Вирт Н. Алгоритмы + структуры данных. Программы. – СПб, 2001ж.
   
3. 
   Симонович С., Евсеев Г.Практическая информатика: Инфорком- Пресс, 1998г.
   
4. 
   Острейковский В.А. Информатика, Москва, 2000 г.
   
5. 
   Петров А.В., Алексеев В.Е., Ваулин А.С., Петрова М.А., Титов М.А., Шкатов П.Н. Вычислительная техника и программирование, Москва, 1990.