Дәріс №1 Кіріспе. Жиындар теориясының негізгі ұғымдары. Жиындарға амалдар қолдану

Салбыраған элемент 2–ге тең. Графтың көршілес (сыбайлас) төбелерінің

0. 
   төбелермен құралған матрица ^{B b}ij өлшемі болатын квадраттық матрица жолдары мен тік қатарлары төбелеріне сәйкестенеді де, теріс емес элемент
   

Егер инцинденттіктен пайда болған матрица бір мағынада беретін болса, онда матрицаның көршілес төбелері графтың кез – келген бағытсыз қырын қарама – қарсы бағытталған доғалармен сол төбелер сақталып өзгертілуі көрсетіледі. Бірақ графтың үлессіз қырлары үшін графтың берілуі бір мағынада осы матрицамен анықталады да көршілес матрицаның элементі мұндай жағдайда 0 не 1 тең болады.

Көрнекілік үшін көрсетуге болады: төбелерге кеңістікте (жазықтықта) әртүрлі бөлінген нүктелер сәйкес келеді де, қырларыныың соңы емес, бөлінген нүктелерден өтпейтін қисық сызықтың кесінділері сәйкес нүктелерге байланыстырады.

Графтың төбелері мен қырларының инцинденттілік қатынасына бөлінген нүктелер мен сызықтары бар геометрикалық инцинденттілік сәйкес келеді.

Одан басқа ішкі нүктеде қос – қостан қиылыспайды. Графтың мұндай көрінісі орындау (жүзеге асыру)деп аталады.

Мынаны көрсетуге болады, кез – келген шекті (типті саналатын) саны бар элементтерден тұратын графтік үштік кеңістікте орындалуы, мүмкіндік жағдайда, егер графтың еселік қабырғалары болмаса, онда қырға түзудің кеңістіктері арқылы орындату қажетті.

Тегіс емес графты жазықтықта бейнелеу өте қолайлы, суретте төбелерді оның қырларының қиылысуын ажырата білу керек (мысалы төбелерді дөңгелектермен бейнелейді) қырлардың бағытын стрелкамен көрсетеді.

Егер графпен көшенің жолдарының тармақтарын көрсетсе, мұнда көршілес төбелерді байланыстыратын жолдарын кесіндімен бейнелеу көрсетіледі.

Алаң және көшенің түйіскен жері – тарап кішкентай ел мекендеген жерлерге графтың тегіс болуы мүмкін, бірақта қала үшін жол өтпелерде, көшелерде транспортардың шешімінде әр деңгейде тегіс граф қолданылады.

1 – суретте граф 8 төбелері және 11 қабырғалары бар граф бейнеленген. Сурет арқылы кейбір ұғымдар кіргізілген 1 ,3 , 6 , 7 , 8 , 10 доғалар болады, 6 -

0. 
   Графтың түрлері
   

Еселік қырлары бар графтарды толық граф деп атайды (кейде ілмексіз). Кез – келген екі төбесі қыры арқылы қосылған еселік қырлары бар графты

атайды, себебі ол дөңгелек жүйесі бойынша жарысқа түскенде оның нәтижесі бір дөңгелекпен бейнеленеді.

а б в г
2-сурет

Толық граф бинарлық R қатынасын көрсетеді, егер R рефлексивті болса,

0. 
   симетрияға қарсы қатынаста болса, онда граф бағытты.
   

2 а, б, в суреттерге ^K3 , ^K4 , ^K5 графтары бейнеленеді. 2 г суретте

а б в 3-сурет

Екі үлесті граф дегеніміз төбелері екі қиылыспайтын сынықтарға бөлінген:

0. 
   өлшемді бірлік кубы дегеніміз Eⁿ граф төбелерінде барлық алынған ұзындығы n нольдер мен бірлер, ал қырлары өзгешелігі бір компонент болатын төбелерді қосады. 4- суретте n = 3 көрініс көрсетілген.
   
1. 
   ₁₁₁
   

001
101

Граф H = (V’, E’) G = (V, E) графының ішкі графы деп аталады да, мынадай белгімен көрсетіледі H G, егер V’ V, E’ E және V’, E’ жиындары үшін G графтың ицинденттігін сақтайды.