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

Инциндент графтардың матрицасы b төбелермен p қырлардан тұратын

тіктөртбұрыш матрица A=||a_ij|| b жолдарымен p тік қатардан құралған жолдары графтың төбелеріне сәйкес келеді, ал қатарлар қырларға, онда егер бағытсыз графтар матрицаның a_ij V_i төбесімен e_j қыры болған жағдайда

a _ij =

Салбыраған элемент 2–ге тең. Графтың көршілес (сыбайлас) төбелерінің B төбелермен құралған матрица В=||b_ij|| өлшемі болатын квадраттық матрица жолдары мен тік қатарлары төбелеріне сәйкестенеді де, теріс емес элемент b_ij v_j ден шығып, v_j- ға кіретін қырлардың санына тең, бірақ бағытсыз графтар үшін көршілес (сыбайлас) матрицаға симметриялық сақталады.

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

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

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

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

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

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

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

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

1 – суретте граф 8 төбелері және 11 қабырғалары бар граф бейнеленген. Сурет арқылы кейбір ұғымдар кіргізілген. l₁ , l₃ , l₆ , l₇ , l₈ , l₁₀ доғалар болады. l₆ бөлектенген (жекеленген) төбе; l₄ және l₅ параллель қырлар; l₆ , l₇ , l₈ , l₉ - параллель қырлар; l₁₁ - ілмек (тұзақ);