В тази статия ще обсъдим матрицата на съседство заедно с нейното представяне.
foreach машинопис
Дефиниция на матрицата на съседство
В теорията на графите матрицата на съседство е плътен начин за описване на структурата на крайната графа. Това е 2D матрицата, която се използва за картографиране на асоциацията между възлите на графиката.
Ако една графика има н брой върхове, тогава матрицата на съседство на тази графа е n x n и всеки запис на матрицата представлява броя на ръбовете от един връх до друг.
Матрицата на съседство се нарича още as матрица на свързване . Понякога се нарича още a Матрица на върховете .
Представяне на матрицата на съседство
Ако неориентиран граф G се състои от n върха, тогава матрицата на съседство на графика е n x n матрица A = [aij] и се дефинира от -
аij= 1 {ако има път, съществува от Viкъм Вй}
аij= 0 {В противен случай}
Нека да видим някои от важните точки по отношение на матрицата на съседство.
- Ако съществува ребро между връх Viи Вй, където i е ред, а j е колона, тогава стойността на aij= 1.
- Ако няма ребро между върха Viи Вй, тогава стойността на aij= 0.
- Ако в простата графика няма собствени цикли, тогава матрицата на върховете (или матрицата на съседство) трябва да има 0 в диагонала.
- Матрицата на съседство е симетрична за неориентиран граф. Той уточнява, че стойността в ithред и jthколона е равна на стойността в jthред ith
- Ако матрицата на съседство е умножена сама по себе си и ако има различна от нула стойност присъства в ithред и jthколона, след това е маршрутът от вiкъм Вйс дължина, еквивалентна на 2. Ненулевата стойност в матрицата на съседство представлява, че броят на отделните пътища присъства.
Забележка: В матрица на съседство 0 означава, че няма връзка между два възела, докато 1 означава, че има връзка между два възела.
Как да създадем матрица на съседство?
Да предположим, че има графика ж с н брой върхове, тогава матрицата на върховете (или матрицата на съседство) се дава от -
А = аединадесета12. . . . . а1падвадесет и едноа22. . . . . а2n. . . . . . . . . аn1аn2. . . . . аnn
Където aijе равен на броя на ребрата от върха i до j. Както бе споменато по-горе, матрицата на съседство е симетрична за неориентирана графа, така че за неориентирана графа, aij= ахей.
Когато графиките са прости и няма тежести по ръбовете или множество ръбове, тогава записите на матрицата на съседство ще бъдат 0 и 1. Ако няма самоцикли, тогава диагоналните записи на матрицата на съседство ще бъдат 0.
unix срещу windows
Сега нека видим матрицата на съседство за неориентиран граф и за насочени графи.
Матрица на съседство за неориентиран граф
В неориентиран график ръбовете не са свързани с посоките с тях. В неориентирана графа, ако има ребро между връх A и връх B, тогава върховете могат да бъдат прехвърлени от A към B, както и B към A.
Нека разгледаме долната неориентирана графа и се опитаме да изградим нейната матрица на съседство.
В графиката можем да видим, че няма собствен цикъл, така че диагоналните записи на съседната матрица ще бъдат 0. Матрицата на съседство на горната графика ще бъде -
Матрица на съседство за насочен граф
В насочена графа ръбовете образуват подредена двойка. Ръбата представляват специфичен път от някакъв връх A до друг връх B. Възел A се нарича начален възел, докато възел B се нарича краен възел.
Нека разгледаме насочената по-долу графа и се опитаме да изградим нейната матрица на съседство.
обратен низ в java
В горната графика можем да видим, че няма самоцикъл, така че диагоналните записи на съседната матрица ще бъдат 0. Матрицата на съседство на горната графика ще бъде -
Свойства на матрицата на съседство
Някои от свойствата на матрицата на съседство са изброени, както следва:
- Матрицата на съседство е матрица, която съдържа редове и колони, използвани за представяне на проста обозначена графика с числата 0 и 1 в позицията на (Vаз, ИНй), според условието дали двете Vi и Вйса съседни.
- За насочен граф, ако има ребро, съществува между връх i или Viкъм Vertex j или Vй, тогава стойността на A[Vi][INй] = 1, в противен случай стойността ще бъде 0.
- За неориентиран граф, ако има ребро, което съществува между връх i или Viкъм Vertex j или Vй, тогава стойността на A[Vi][INй] = 1 и A[Vй][INi] = 1, в противен случай стойността ще бъде 0.
Нека да видим някои въпроси на матрицата на съседство. Въпросите по-долу са за претеглените неориентирани и насочени графики.
ЗАБЕЛЕЖКА: Графът се нарича претеглен граф, ако на всяко ребро е присвоено положително число, което се нарича тегло на ребра.
Въпрос 1 - Каква ще бъде матрицата на съседство за долната неориентирана претеглена графика?
Решение - В дадения въпрос няма самоцикъл, така че е ясно, че диагоналните записи на съседната матрица за горната графика ще бъдат 0. Горната графика е претеглена неориентирана графа. Теглата на ръбовете на графиката ще бъдат представени като записи на матрицата на съседство.
конвертиране на char в низ java
Матрицата на съседство на горната графика ще бъде -
Въпрос 2 - Каква ще бъде матрицата на съседство за насочената по-долу претеглена графика?
Решение - В дадения въпрос няма самоцикъл, така че е ясно, че диагоналните записи на съседната матрица за горната графика ще бъдат 0. Горната графика е претеглена насочена графа. Теглата на ръбовете на графиката ще бъдат представени като записи на матрицата на съседство.
Матрицата на съседство на горната графика ще бъде -
Надяваме се, че тази статия е полезна за вас, за да разберете за матрицата на съседство. Тук обсъдихме матрицата на съседство заедно с нейното създаване и свойства. Ние също така обсъдихме формирането на матрица на съседство върху насочени или неориентирани графи, независимо дали са претеглени или не.