Кіріспе

Квадраттық матрица графты немесе желіні көрсету үшін қолданылады. Графтар теориясы мен компьютерлік ғылымда, қатарлас матрица – шекті графты көрсетуге қолданылатын квадраттық матрица. Матрицаның элементтері графтың төбелерінің жұптары қатарлас па, жоқ па екенін көрсетеді. Егер граф қарапайым болса, қатарлас матрица диагоналінде нөлдері бар (0,1) матрица болады. Егер граф бағытталмаған болса (яғни оның барлық қабырғалары екі бағытта жүрсе), қатарлас матрица симметриялы болады. Граф пен оның қатарлас матрицасының өзіндік мәндері мен өзіндік векторлары арасындағы байланыс спектрлік графтар теориясында зерттеледі. Графтың қатарлас матрицасын оның түйіспе матрицасынан – элементтері төбе-қабырға жұптарының түйісіп жататынын немесе жатпайтынын көрсететін басқа матрицалық бейнелеуден, сондай-ақ әр төбесінің дәрежесі туралы ақпаратты қамтитын дәреже матрицасынан ажырату керек.

Анықтама

Басы бар қарапайым график үшін, көршілік матрицасы – квадраттық n × n матрицасы A, ондағы Aij элементі ui төбесінен uj төбесіне жиек бар болса 1, ал жиек болмаса 0 болады. Матрицаның диагональ элементтерінің бәрі 0-ге тең, себебі қарапайым графтарда төбеден өзіне жиектерге (циклдерге) рұқсат етілмейді. Алгебралық графтар теориясында нөлдік емес элементтерді алгебралық айнымалылармен алмастыру да кейде пайдалы. Осы ұғымды мультиграфтарға және циклдары бар графтарға кеңейтуге болады: әр екі төбе арасындағы жиектер санын тиісті матрица элементінде сақтау және нөлдік емес диагональ элементтеріне рұқсат беру арқылы. Циклдер бір рет (бір жиек ретінде) немесе екі рет (екі төбелік жиек инциденті ретінде) саналады, егер біркелкі қағида сақталса. Бағытталмаған графтар көбінесе циклдерді екі рет санау қағидасын қолданады, ал бағытталған графтар әдетте бірінші қағиданы қолданады.

Вариациялар

Қарапайым графтың іргелес матрицасы А егер (i, j) жиек болса, b егер болмаса, ал диагональде c болады. Сейдельдің іргелестік матрицасы – іргелес матрицаның бір түрі. Бұл матрица күшті тұрақты графтарды және екі графты зерттеуде қолданылады. Қашықтық матрицасының (i, j) орнында vi және vj төбелері арасындағы қашықтық көрсетіледі. Қашықтық – бұл төбелерді қосатын ең қысқа жолдың ұзындығы. Егер қабырғалардың ұзындығы нақты көрсетілмесе, жолдың ұзындығы оның қабырғаларының санымен анықталады. Қашықтық матрицасы іргелес матрицаның жоғары дәрежесіне ұқсас, бірақ екі төбе байланысты ма, жоқ па дегенді ғана көрсетудің орнына (яғни, бульдік мәндері бар байланыс матрицасы), олардың арасындағы нақты қашықтықты көрсетеді.

Бағытталмаған графиктер

Мұнда (бағытталмаған графтар үшін) қолданылатын конвенция бойынша, әрбір қабырға матрицадағы тиісті ұяшыққа 1-ді, ал әрбір цикл 2-ні қосады. Бұл, қанағаттану матрицасындағы тиісті қатар немесе бағанның мәндерінің қосындысын есептеу арқылы төбелік дәрежесін оңай табуға мүмкіндік береді. Белгіленген графтың қанағаттану матрицасы: Координаттары 1–6. Науру графының координаталары 0–23. Ақ түсті ұяшықтар нөлдерді, ал боялған ұяшықтар бірліктерді білдіреді.

Трифуальдық графиктер

Толық графтың жапсарлас матрицасында диагональ бойынша ғана нөлдер болады, ал қалғандары біліктерден тұрады. Бос графтың жапсарлас матрицасы нөлдік матрица болып табылады.

Спектр

Бағытталмаған қарапайым графиктің көршілес матрицасы симметриялық, сондықтан нақты өзіндік мәндердің толық жиынтығы және ортогональды өзіндік векторлар негізі болады. Графиктің өзіндік мәндерінің жиынтығы – графтың спектрі. Өзіндік мәндерді былай белгілеу қабылданған:

Ең үлкен өзіндік мән максималды дәрежеден жоғары болмайды. Бұл Перрон-Фробень теоремасының салдары ретінде көрінеді, бірақ оны оңай дәлелдеуге болады. v –ге сәйкес келетін бір өзіндік вектор, ал x – v-нің абсолюттік мәні ең үлкен болатын компоненті болсын. Жалпылықты жоғалтпай, vx оң деп қабылдайық, әйтпесе сіңірген өзіндік векторды аламыз, ол да сәйкес келеді. Сонда

d-тұрақты графтар үшін d – A матрицасының вектор үшін бірінші өзіндік мәні (оның өзіндік мән екенін тексеру оңай және жоғарыда көрсетілген шектен оның максималды екені белгілі). Бұл өзіндік мәннің көптігі G-нің байланысқан компоненттерінің санына тең, атап айтқанда, байланысқан графтар үшін. Кез келген өзіндік мән үшін оның теріс мәні де G екі жақты граф болса, A-ның өзіндік мәні екенін көрсетуге болады. Атап айтқанда, -d кез келген d-тұрақты екі жақты графтың өзіндік мәні болып табылады. Айырмашылық спектрлік саңылау деп аталады және ол G-нің кеңеюімен байланысты. Сондай-ақ, спектрлік радиусты енгізу пайдалы, ол деп белгіленеді. Бұл санмен шектеледі. Бұл шек Раманужан графтарында толық, олар көптеген салаларда қолданылады.

Изоморфизмдер мен инварианттар

Екі бағытталған немесе бағытталмаған G1 және G2 графиктері, олардың жапсарлас матрицалары A1 және A2 берілген болсын. G1 және G2 графиктері изоморфты болады, егер және тек қана P пермутациялық матрицасы болса. Атап айтқанда, A1 және A2 матрицалары ұқсас, демек, олардың минималды полиномдары, сипаттамалық полиномдары, өзіндік мәндері, детерминанты және іздері бірдей болады. Осылайша, олар графтардың изоморфизмі инварианттары ретінде қолданылуы мүмкін. Дегенмен, екі графтың өзіндік мәндер жиыны бірдей болғанымен, олар изоморфты болмауы мүмкін. Мұндай сызықтық операторлар изоспектрлі деп аталады.

Матрицалық күштер

Егер A – бағытталған немесе бағытталмаған G графының жабыстық матрицасы болса, онда Aⁿ матрицасының (яғни A-ның n көшірмелерінің матрицалық көбейтіндісі) қызықты түсіндірмесі бар: элемент aᵢⱼ n ұзындығындағы (бағытталған немесе бағытталмаған) i төбесінен j төбесіне дейінгі жолдар санын көрсетеді. Егер n – ең кіші теріс емес бүтін сан болса, онда кейбір i, j үшін Aⁿ-нің aᵢⱼ элементі оң болса, онда n – i және j төбелері арасындағы қашықтық. Бұл қалай пайдалы екеніне керемет мысал – бағытталмаған G графындағы үшбұрыштар санын есептеу, бұл A³-тің іздерін 3-ке немесе 6-ға бөлу арқылы табылады, граф бағытталған немесе бағытталмаған болуына байланысты. Біз осы мәндерге бөлеміз, өйткені әр үшбұрыш екі рет саналып қойылады. Бағытталмаған графтарда әрбір үшбұрыш үш төбесі үшін де екі рет есептеледі, себебі жол сағат тілімен немесе сағат тіліне қарсы бағытта жүруі мүмкін: ijk немесе ikj. Жабыстық матрицасы графтың байланысқан немесе байланыспаған екенін анықтау үшін қолданылуы мүмкін. Егер бағытталған графтың nilpotent жабыстық матрицасы болса (яғни, Aⁿ нөлдік матрицаға тең болатын n болса), онда ол бағытталған ациклді граф болып табылады.

Деректер құрылымы

Жақындық матрицасы компьютерлік бағдарламаларда графиктерді өңдеу үшін графиктерді ұсынуға арналған дерек құрылымы ретінде қолданылуы мүмкін. Бұл қолданба үшін негізгі баламалы дерек құрылымы – жапсарлас тізім. Жақындық матрицасын ұсынуға қажетті жад және оған операциялар орындауға қажетті уақыт негізгі матрица үшін таңдалған матрицалық ұсыну тәсіліне байланысты. Сирек матрицалық ұсынулар тек нөлдік емес матрицалық элементтерін ғана сақтайды және нөлдік элементтерді жасырын түрде көрсетеді. Мысалы, оларды сирек графиктің жақындық матрицасында көптеген нөлдік элементтерді сақтаудан жадты үнемдеп, сирек графикті ұсыну үшін пайдалануға болады. Келесі бөлімде жақындық матрицасы массивтік дерек құрылымы арқылы ұсырылған деп ескереді, сондықтан нөлдік және нөлдік емес элементтер тікелей жадта көрсетіледі. Жақындық матрицадағы әрбір элементке бір бит қана қажет болғандықтан, оны өте ықшам түрде көрсетуге болады, бағытталған графикті ұсыну үшін |V|²/8 байт, ал бағытталмаған графикті ұсыну үшін (жинақы үшбұрышты форматты пайдаланып және матрицаның төменгі үшбұрышты бөлігін ғана сақтау арқылы) шамамен |V|²/16 байт алады. Кем дегенде, сәл ықшам ұсынулар да мүмкін, бірақ бұл әдіс барлық n төбелі графикті ұсыну үшін қажетті биттердің ақпараттық теориялық ең төменгі шегіне жақын. Графиктерді мәтіндік файлдарда сақтау үшін, барлық байттар мәтіндік символдар болып табылуын қамтамасыз ету үшін, мысалы, Base64 ұсынымын пайдалану арқылы байтқа қажетті биттердің санын азайтуға болады. Бұл ықшамдық жадты ысыраптап жібермеумен қатар, деректерге жылдам қолжетімділікті қамтамасыз етеді. Дегенмен, үлкен сирек график үшін жапсарлас тізімдер аз жадты қажет етеді, себебі олар жоқ қабырғаларды ұсынуға жадты жұмсамайды.