|
|
3 дәріс Графтар теориясы. 6 таырып Графтар теориясына кіріспе Масаты
6 тақырып
Графтар теориясына кіріспе
Мақсаты: Графтар теориясының негізгі ұғымдарымен, олардың
түрлерімен таныстыру.
Жоспар:
1.Графтың негізгі анықтамалары
2.Графтың инциденттік матрицасы
3.Графтың түрлері
1.Графтың негізгі анықтамалары
Анықтама. Граф деп – бейнеленген заттардың екі – екіден жұпталып
келген заттардың бір – бірімен қатынасының жүйесін айтады. Графтармен коммуникация жолдарын қолайлы бейнелейді, үздіксіз емес көп қадамды
процестерде («бинарлық қатынастардың жүйелерін, химиялық формулалардың
құрылымында, тағы басқа әр түрлі схемалардың диаграммаларында»)
қолданылады.
ГрафG-жүйе
V V E V G , ,
жиынының элементі граф төбесінен тұрады
да,
e E
қыры болып келген бейнелеуді көрсетеді.
2
: V E егер әрбір
элементтің E e реттелген санға сәйкес реттелген екі элементті
V V V 2 1
,
–ның
қырларының соңы сәйкес келеді.
E V (Vжәне Eжиындарының бірігуі) – графтың көптеген
элементтерінен тұрады да, ал E V = ø (Eмен Vқиылысуы) құр жиынды
көрсетеді. бейнесі әрбір соңғы қырының инцинденттігін анықтайды.
, ,E V G
үшін ең қысқа
E V G ,
. Мұнда инцинденттілігі көрсетілмеген. Олар
контекстпен анықталады. Элементтерінің санына байланысты шекті және
шексіз болып бөлінеді. Біз тек ғана шекті графпен танысамыз.
Егер
2 1
,V V e r
–екі –екіден таралып реттелген.
1 2 2 1
, , V V V V 2 1 V V
болғанда, онда e
бағытталған доғал болады да,
шыққан 1 V
-төбесі
e
доғасының басы, кіретін 2 V
төбесі
e
доғасының соңы деп
аталады.
Егер
2 1
,V V e r
жұбы ретсіз болса, онда e
қыры бағытсыз деп аталады.
Кез – келген Gграфқа сәйкестендіріліп алынған бағытсыз граф
G,Vжәне
Eжиындарынан және инцинденттіктерінен тұрады, бірақ барлық парлары
ретсіз болады.
Төбелері бірде – бір қырымен инциндентті болмаса, онда ондай қырды
бөлектенгенқыр деп атаймыз, ал төбесі бір қырымен инциндентті болса, онда
оны аяқталған қыр, не ілінген қыр деп атаймыз. Қырдың басы мен соңы
біріккен болса, оныілмекдеп атаймыз.
Егер екі төбе бір қырға инциндентті болса, ондай төбелерді көршілес, не
сыбайластөбелер деп атайды. Егер екі қыр бір төбеге инциндентті болса, онда
ондай қырды сыбайласдеп атаймыз. Қырға сәйкес қойылған екі төбені еселік,
не параллель төбелер деп атаймыз.
Әртүрлі есептер үшін бір тек сол затқа графтың әртүрлі салыстыруы
қажет.
Мысалы: жолдар тармағының үзіндісі ретсіз қырмен көрсетіледі де, бір–
бірімен қатынастарының аяқталуын бейнелейді (қоныстанған орындарымен,
қала көшелерімен, көшенің түйіскен жерімен құралдарындағы бір жақты, не екі
жақты қозғалыстар). Бірнеше доғаларымен бөлектеген әрбір бірнеше
қозғалысты – қырға қосымша жазылған сандар, оның ұзындығын, енін,
епкіштігін және сандар не басқа сипаттамасын көрсетеді.
Қандай графтар ажыратылатын және ажыратылмайтын болып бөлінуін
анықтау өте қажет болып табылады, оны тіпті графтардың изоморфизм
ұғымымен байланыстырады. Өзара сақталып инцинденттік пайда болған
Әдебиет: 8, 8-16 бет, 16, 7-18 бет
Бақылау сұрақтары: |
|
|
Скачать 25.95 Kb.