Матрица инцидентности графа — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Инцидентность ребра и вершины)
Строка 3: Строка 3:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Инцидентность''' - отношение между ребром и его концевыми вершинами, т. е. если в графе <tex>G = (V,E), u \in V, v \in V</tex> - вершины, а <tex>e \in E, e = (u,v)</tex> - соединяющее их ребро, то вершина <tex>u</tex> и ребро <tex>e</tex> инцидентны, вершина <tex>v</tex> и ребро <tex>e</tex> также инцидентны.
+
'''Инцидентность''' {{---}} отношение между ребром и его концевыми вершинами, т. е. если в графе <tex>G = (V,E), u \in V, v \in V</tex> {{---}} вершины, а <tex>e \in E, e = (u,v)</tex> {{---}} соединяющее их ребро, то вершина <tex>u</tex> и ребро <tex>e</tex> инцидентны, вершина <tex>v</tex> и ребро <tex>e</tex> также инцидентны.
 
}}
 
}}
  
Строка 45: Строка 45:
 
==Источники==
 
==Источники==
  
Асанов М., Баранский В., Расин В. - Дискретная математика: Графы, матроиды, алгоритмы Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.
+
Асанов М., Баранский В., Расин В. {{---}} Дискретная математика: Графы, матроиды, алгоритмы {{---}} Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.
  
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Основные определения теории графов]]
 
[[Категория: Основные определения теории графов]]

Версия 07:56, 3 февраля 2012

Инцидентность ребра и вершины

Определение:
Инцидентность — отношение между ребром и его концевыми вершинами, т. е. если в графе [math]G = (V,E), u \in V, v \in V[/math] — вершины, а [math]e \in E, e = (u,v)[/math] — соединяющее их ребро, то вершина [math]u[/math] и ребро [math]e[/math] инцидентны, вершина [math]v[/math] и ребро [math]e[/math] также инцидентны.


Определения для ориентированного и неориентированного графов

Определение:
Матрицей инцидентности (инциденций) неориентированного графа называется матрица [math]I (|V| \times |E|)[/math], для которой [math]I_{i,j} = 1[/math], если вершина [math]v_i[/math] инцидентна ребру [math]e_j[/math], в противном случае [math]I_{i,j} = 0[/math].


Определение:
Матрицей инцидентности (инциденций) ориентированного графа называется матрица [math]I (|V| \times |E|)[/math], для которой [math]I_{i,j} = 1[/math], если вершина [math]v_i[/math] является началом дуги [math]e_j[/math], [math]I_{i,j} = -1[/math], если [math]v_i[/math] является концом дуги [math]e_j[/math], в остальных случаях [math]I_{i,j} = 0[/math].


Пример

Граф Матрица инцидентности Ориентированный граф Матрица инцидентности
Граф.JPG [math]\begin{pmatrix} 1 & 1 & 1 & 0 & 1 & 0\\ 1 & 0 & 0 & 1 & 0 & 0\\ 0 & 1 & 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 & 0 & 1\\ 0 & 0 & 0 & 1 & 1 & 0\\ \end{pmatrix}[/math] Орграф.jpg [math]\begin{pmatrix} -1 & 1 & -1 & 0 & -1 & 0\\ 1 & 0 & 0 & -1 & 0 & 0\\ 0 & -1 & 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 & 0 & -1\\ 0 & 0 & 0 & 1 & 1 & 0\\ \end{pmatrix}[/math]

Источники

Асанов М., Баранский В., Расин В. — Дискретная математика: Графы, матроиды, алгоритмы — Ижевск: ННЦ "Регулярная и хаотическая динамика", 2001, 288 стр.