3.02.4. Матрица инцидентности

Пусть G -- (N,M)-граф, V(G) = {1, 2, 3, …, N}, E(G) = {E1, E2, E3, …, Em}. Матрицей инцидентности графа G Называется бинарная N´M-Матрица I(G) = (Iij), такая, что:

Iij =

Понятно, что такая матрица имеет ровно по две единицы в каждом столбце (ведь всякое ребро имеет два конца -- две инцидентные данному ребру вершины). Число единиц в каждой строке матрицы инцидентности равно степени соответствующей вершины. Матрицы инцидентности изоморфных графов получаются друг из друга путём обычных (непарных, в отличие от матрицы смежности и матрицы Кирхгофа) перестановок строчек и столбцов.

Для ориентированного графа:

Iij =

Существует следующая связь между матрицей инцидентности I и матрицей Кирхгофа K графа G. Пусть G -- простой граф. Превратим его в ориентированный граф задав на каждом ребре (произвольную) ориентацию, другими словами, расставим стрелки на всех рёбрах графа G. Полученный граф называется ориентацией графа G.

Теорема. Если K -- матрица Кирхгофа графа G И I -- матрица инцидентности какой-либо его ориентации, то K = I × IТ, где IТ – транспонированная матрица.

< Предыдущая		Следующая >