Пәнді меңгеру жөніндегі әдістемелік нұсқаулар

Кафедра меңгерушісі ___________ Оспанова Н.Н. 2012 ж. «_»____

ФМжАТ факультетінің ОӘК мақұлданды.

2012 ж. «_____»______________ №____хаттама

ОӘК төрағасы __________ Искакова А.Б. 2012 ж. «____»____________

ОӘБ бастығы ____________ Жұманқұлова Е.Н.

2012 ж. «____»_____________

1-тақырып Графтар теориясына кіріспе.

Графтар теориясының жалпы элементтері. Бинарлық ағаштар. Бинарлық ағаштарда қолданылатын амалдар. Бинарлық ағаштың көрсетілімі. Толық бинарлық ағаштар және AVL-ағаштар. Графтың түрлері.

Мысалы, журналда: ажырату – жол соңы, іздеу – нөмір бойынша Кестелік құрылым – реттелген құрылым, мұнда әрбір элемент өзі орналасқан ұяшықтың адресімен, яғни қиылысуында ұяшық орналасқан жол мен бағаның нөмірі арқылы анықталады.

Мысалы:

жүргізіледі.

Мысалы, С:\Мои документы\Группа 1В\Сауле

• 
  Граф — бұл жүйенің құрамын және құрылымын көрнекі көрсетуге арналған құрал.
  
• 
  Граф қырлармен немесе доғалармен байланыстырылған төбелерден тұрады. Төбелер дөңгелек, овал, нүкте, тіктөртбұрыш және басқа түрлерінде бейнеленуі мүмкін. Төбелер арасындағы байланыс сызықтармен бейнеленеді. Егер сызық бағытталған (нұсқамалы) болса, онда ол доға деп аталады, егер бағытталмаған болса, онда қыр деп аталады. Бір қыр, қарама қарсы бағытталған екі доғаны ауыстырады.
  
• 
  Барлық сызықтары нұсқамалы графты – бағытталған граф деп атайды.
  
• 
  Егер графтың қырлары төбелердің реттелген қостарымен анықталса, онда ол графты бағытталған деп атайды.
  
• 
  Доғамен немесе қырмен байланысқан екі төбе шектес деп аталады.
  
• 
  Граф қос жиын: төбелер жиыны және қырлар жиыны болып беріледі.
  
• 
  Информацияны жүйенің құрамы және құрылымы туралы граф түрінде көрсеткенде, жүйенің компоненттері төбелері, ал олардың арасындағы байланыс сызықтармен (доғалармен немесе қырлармен) бейнелінеді. Графтар адамдардың көптеген практикалық және ғылыми қызмет аймақтарында қолданылады.
  

2-ші мысал. Бұл мысал органикалық химияға жатады. Көмірсутектер деп аталатын заттардың қасиеті, молекуладағы тек қана көміртектің және сутектің атомдарының санына ғана тәуелді болмай, олардың қосылу тәсілінеде байланысты екені белгілі.

Дейкстр алгоритмі. Флойда алгоритмі. Форд-Беллман алгоритмі.

5-ші мысал. Бәріне белгілі блок-схемалар алгоритмнің құрылымын бейнелейтін граф болып табылады. Бұл графтарды төбелері – теңқұқықсыз. Олар бірнеше типке бөлінеді – есептеу, тармақталу, басы/соңы, т.б. блоктары. Блоктың типі туралы информация оның формасы арқылы беріледі. (тіктөртбұрыш, ромб, овал). Әр блоктың нақты мазмұны осы блоктың ішіндегі жазумен беріледі. Тармақталу-төбесінен шығатын доғаларда «иә» немесе «жоқ» белгі болады. Ағаш— объектілер арасындағы қабаттылық, бағыныштылық, мұрагерлік сияқты байланыстарды бейнелеуге арналған граф.

Ағаш — ол бағытталмаған байланысқан граф.

Ол былай құрылады. Ең алдымен еш бір басқа төбелерге тәелді емес «бас» төбе салынады. Бұл төбе «1-ші деңгейлі» ағаштың тамыры деп аталады. Ары қарай «2-ші деңгейлі» төбелерді қосамыз. Олардың саны нешеу болсада әр қайсысы тамырмен - 1-ші деңгейдегі төбемен байланысыды, бірақ өз-ара байланыспайды.

Келесі қадамда 3-ші деңгейдегі төбелерді қосамыз. Оның әр қайсысы 2-ші деңгейдің бір төбесімен ғана байланыста болады.

2-ші деңгейдің кез келген төбесіне 3-ші деңгейдің қанша болсын (оның ішінде бірде біреуі) байланысуы мүмкін, т. с. с.

5-ші мысал. Бәріне белгілі блок-схемалар алгоритмнің құрылымын бейнелейтін граф болып табылады. Бұл графтарды төбелері – теңқұқықсыз. Олар бірнеше типке бөлінеді – есептеу, тармақталу, басы/соңы, т.б. блоктары. Блоктың типі туралы информация оның формасы арқылы беріледі. (тіктөртбұрыш, ромб, овал). Әр блоктың нақты мазмұны осы блоктың ішіндегі жазумен беріледі. Тармақталу-төбесінен шығатын доғаларда «иә» немесе «жоқ» белгі болады. Ағаш— объектілер арасындағы қабаттылық, бағыныштылық, мұрагерлік сияқты байланыстарды бейнелеуге арналған граф.

Ағаш — ол бағытталмаған байланысқан граф.

Ол былай құрылады. Ең алдымен еш бір басқа төбелерге тәелді емес «бас» төбе салынады. Бұл төбе «1-ші деңгейлі» ағаштың тамыры деп аталады. Ары қарай «2-ші деңгейлі» төбелерді қосамыз. Олардың саны нешеу болсада әр қайсысы тамырмен - 1-ші деңгейдегі төбемен байланысыды, бірақ өз-ара байланыспайды.

Келесі қадамда 3-ші деңгейдегі төбелерді қосамыз. Оның әр қайсысы 2-ші деңгейдің бір төбесімен ғана байланыста болады.

2-ші деңгейдің кез келген төбесіне 3-ші деңгейдің қанша болсын (оның ішінде бірде біреуі) байланысуы мүмкін, т. с. с.

Ұсынылатын әдебиеттер: [1] – 47 - 94 бб., [5] – 1 -29 бб.
3-тақырып Бағдарламалауда графтарды қолдану.
Бағдарламалауда графтарды қолдану сұрақтары. Ағаштардағы алгоритмдер класы. Контурсыз графтардағы алгоритмдер класы. Бағдарламалаудағы граф-модельдер.

Сызықтық модельде жүйедегі элемент реттік номерімен анықталады.

Кестелік модельде элемент орналасқан бағанның және жолдың номерімен анықталады.

Иерархиялы модель графтар мен ағаштар түрінде болады.

Граф дегеніміз төбелер мен төбелер жұптарының жиыны. Граф доғалармен және қабырғалармен байланысқан төбелерден тұрады.

Егер сызық бағытталған болса онда ол доға, ал бағытталмаған болса қабырға деп аталады. Доға қарама-қарсы бағытталған болса, онда оны бір қабырғамен көрсетуге болады. Барлық сызықтары бағытталған болса граф бағытталған деп аталады. Доға немесе қабырғаға байланысқан екі сызықты сыбайлас деп атайды.

Әдебиеттер тізімі

1. 
   Дюсембаев .Е. Информатика. Структуры данных, сортировка, поиск. – Алматы: ТОО «Диар», 2008. – 144 с.
   

3. Костюкова Н.И. Графы и их применение. Комбинаторные алгоритмы для программистов БИНОМ. Лаборатория знаний, Интернет-университет информационных технологий - ИНТУИТ.ру, 2007

4. Алексеев В.Е., Таланов В.А. Графы и алгоритмы. Структуры данных. Модели вычислений БИНОМ. Лаборатория знаний, Интернет-университет информационных технологий - ИНТУИТ.ру, 2006.

5. http://www.iis.nsk.su/files/articles/sbor_kas_07_kasyanov_primenenie.pdf.

6. Емеличев В.А. Лекции по теории графов. М.: Наука, 1990

7. Л. Ловас, М. Пламмер Прикладные задачи теории графов М.: Мир, 1998.