Графтар теориясы-шектеулі математиканың кейбір мәселелерді шешуге геометриялық тұрғыдан келу тән бюолып табылатын бөлім. Граф теориясының негізгі мазмұны графтарды зерттеу болып табылады. Граф – «граф» — «жазамын» деген мағанадағы грек сөзінен алынған.
Жазықтықта әртүрлі бес A,B,C,D,E нүктелерін белгілейік. Осы нүктелерді графтың төбелері, ал оларды қосатын сызықтарды \түзу немесе қисық\ графтың қабырғалары деа атайды.
Бұл графты A,B,C,D,E нүктелерін қосатын сызықтар осы нүктелерден басқа ешбір нүктелерден қиылыспайтындай етіп те кескіндеуге боладыв. Қабырғалары тек төбелерінде ғана қиылысатын графты жазық граф деп атайды.
Графтың мынадай негізгі қасиеттері болады:
Оның тақ төбелерінің саны әрқашан жұп болады. Тақ төбелерінің саны тақ сан болатын графты сызып көрсету мүмкін емес.
Егер графтың барлық төбелері жұп болса онда графты бір сызықтықпен сызып шығуға болады.
Тақ төбелерінің саны екіге тең болатын графты бір сызықпен сызып шығуға болады. Мұнда қозғалысты тақ тқбелердің кез – келген біреуінен бастап екіншісінен аяқтау қажет.
Тақ төбелерінің саны екіден артық болатын графты бір сызықпен сызып шығу мүмкін емес.
Анықтама. Өзара қиылысу нүктелерінде екі ғана рет бола отырып сызып шығуға болатын жазық қисықты бір бағытты қисық деп атайды.
Теорема. Қисық бір бағытты (уникурсал) болу үшін оның тақ түйіндерінің саны екіден артықболмауы қажетті және жеткілікті.
Теорема. Кез — келген жазық граф үшін Т – Қ + Ж= 2 теңдігі орындалады. Мұндағы Т – граф төбелерінің саны, Қ – граф қабырғаларының саны, Ж –оның жақтарының саны. Бұл теорема жазық графтар үшін Эйлер теоремасы деп аталады. Жалпы апйтқанда, графтар төбелерден , қабырғалардын және жақтардан тұрады. Берілген граф арқылы жазықтықтың бөлінген бөліктері жақтар деп аталады.
Толық жазық графтардың мынадай қасиеттерін \дәлелдеусіз\ келтіреміз:
- Төбелерініңң саны n – ге тең болатын толық жазық графтың қабырғаларының саны 3n – 6 – тең боады, мұндағы n ≥3.
- Егер толық графтың төбелерінің саны n –ге/ n≤4/ тең болса , онда ол жазық граф болып табылады.
Графтағы ешбір қабырға арқылы бірден артық рет өтпейтін сызық шынжыр деп аталады. Егер қозғалысты А нүктесінен бастап барлық төбелерден қайта оралу мүмкін болса , мұндай жолды цикл деп атайды. Егер циклдыңң барлық төбелері әртүрлі болса, мұндай цикл қарарайым цикл, ал қарсы жағдайда қарапайым емес цикл деп аталады. Кей жағдайда цикл графтың барлық қабырғаларын дәл бір реттен қамтиды. Мұндай циклдарды Эйлер сызықтарды деп атайды.
Анықтама. X жиынынY жиынын ішкі жиынына беәнелеу деп әрбір xX элементінің бейнесі бір және теке бір ғана yY болатын X жәнеY жиындар арасындағы сәйкестікті айтады. Басқа сөзбен айтқанда, кез – келген xY
Үшін xPy болатын бір және тек бір ғана yY табылады деп аталады.
Егер f-Х жиынын У жиынына бейнелейтін болса,онда он f ;Х –У түрінде жазады.
F –Х жиынын У жиынына бейнелеу болса .Осы f бейнелеудегі х=Х элементіне сәйкес келетін у=У элементі х элементінің бейнесі деп аталады және f [х],яғни у=f [ х] деп. белгілейді.