Какво е матрица на инцидентност?
Матрица инцидентности е матрицата, която представя графа така, че с помощта на тази матрица можем да начертаем граф. Тази матрица може да бъде обозначена като [AC]. Както във всяка матрица, в матрица на инцидентността [AC] има редове и колони.
Редовете на матрицата [AC] представляват броя на възлите, а колоните на матрицата [AC] представляват броя на клонките в дадения граф. Ако в дадена матрица на инцидентността има 'n' реда, това означава, че в графа има 'n' възела. Аналогично, ако в дадената матрица на инцидентността има 'm' колони, това означава, че в графа има 'm' клонки.
В показания по-горе граф или ориентиран граф, има 4 възела и 6 клонки. Следователно матрицата на инцидентността за горния граф ще има 4 реда и 6 колони.
Стойностите на матрицата на инцидентността винаги са -1, 0, +1. Тази матрица е винаги аналогична на KCL (Закон на Кирхоф за тока). Следователно от KCL можем да изведем, че,
| Тип клонка | Стойност |
| Изходяща клонка от kти възел | +1 |
| Входяща клонка към kти възел | -1 |
| Други | 0 |
Стъпки за конструиране на матрица на инцидентността
Следните са стъпките за изчертаване на матрица на инцидентността:
Ако даден kти възел има изходяща клонка, записваме +1.
Ако даден kти възел има входяща клонка, записваме -1.
Останалите клонки се считат за 0.
Примери за матрица на инцидентността
За показания по-горе граф запишете неговата матрица на инцидентността.
Намалена матрица на инцидентността
Ако от дадена матрица на инцидентността [AC] е изтрит произволен ред, новата образувана матрица ще бъде намалена матрица на инцидентността. Тя се обозначава с символ [A]. Поредността на намалената матрица на инцидентността е (n-1) × b, където n е броят на възлите, а b е броят на клонките.
За показания по-горе граф, намалената матрица на инцидентността ще бъде :-
[Забележка: В показаната по-горе матрица ред 4 е изтрит.]
Сега нека разгледаме нов пример, свързан с намалената матрица на инцидентността. За показания по-горе граф запишете неговата намалена матрица на инцидентността.
Отговор:- За да начертаем намалената матрица на инцидентността, първоначално трябва да начертаем нейната матрица на инцидентността. Нейната матрица на инцидентността е :-
Сега начертаваме нейната намалена матрица на инцидентността. За това просто трябва да изтрием произволен възел (в този случай сме изтрит възел 2). Нейната намалена матрица на инцидентността е:-
Това е търсеният отговор.
Неща, които трябва да се помнят
За проверка на правилността на матрицата на инцидентността, която сме начертали, трябва да проверим сумата на колоните.
Ако сумата на колоната е нула, тогава матрицата на инцидентността, която сме съставили, е правилна, в противен случай - неправилна.
Матрицата на инцидентността може да се приложи само към ориентирани графи.
Броят на входите в ред, освен нула, ни дава броя на клонките, свързани с този възел. Това се нарича степен на този възел.
Рангът на пълната матрица на инцидентността е (n-1), където n е броят на възлите на графа.
Поредността на матрицата на инцидентността е (n × b), където b е броят на клонките на графа.
От дадена намалена матрица на инцидентността можем да начертаем пълната матрица на инцидентността
