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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 3: Строка 3:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
'''Инцидентность''' - отношение между ребром и его концевыми вершинами, т. е. если в графе <math>G = (V,E) </math>  <math>u \in V, v \in V</math> - вершины, а <math>e \in E</math> - соединяющее их ребро (e = (u,v)), то вершина u и ребро e инцидентны, вершина v и ребро e также инцидентны.
+
'''Инцидентность''' - отношение между ребром и его концевыми вершинами, т. е. если в графе <tex>G = (V,E) </tex>  <tex>u \in V, v \in V</tex> - вершины, а <tex>e \in E</tex> - соединяющее их ребро (e = (u,v)), то вершина u и ребро e инцидентны, вершина v и ребро e также инцидентны.
 
}}
 
}}
  
Строка 10: Строка 10:
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
'''Матрицей инцидентности''' (инциденций) неориентированного графа называется матрица <math>I (V \times E)</math>, (i, j)-й элемент которой равен 1, если вершина <math>v_i</math> инцидентна ребру <math>e_j</math>, и 0 в противном случае.
+
'''Матрицей инцидентности''' (инциденций) неориентированного графа называется матрица <tex>I (V \times E)</tex>, (i, j)-й элемент которой равен 1, если вершина <tex>v_i</tex> инцидентна ребру <tex>e_j</tex>, и 0 в противном случае.
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
−
'''Матрицей инцидентности''' (инциденций) ориентированного графа называется матрица <math>I (V \times E)</math>, (i, j)-й элемент которой равен 1, если вершина <math>v_i</math> является началом дуги <math>e_j</math>, -1, если <math>v_i</math> является концом дуги <math>e_j</math>, и 0 в остальных случаях.
+
'''Матрицей инцидентности''' (инциденций) ориентированного графа называется матрица <tex>I (V \times E)</tex>, (i, j)-й элемент которой равен 1, если вершина <tex>v_i</tex> является началом дуги <tex>e_j</tex>, -1, если <tex>v_i</tex> является концом дуги <tex>e_j</tex>, и 0 в остальных случаях.
 
}}
 
}}

Версия 23:34, 13 октября 2010

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

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


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

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


Определение:
Матрицей инцидентности (инциденций) ориентированного графа называется матрица [math]I (V \times E)[/math], (i, j)-й элемент которой равен 1, если вершина [math]v_i[/math] является началом дуги [math]e_j[/math], -1, если [math]v_i[/math] является концом дуги [math]e_j[/math], и 0 в остальных случаях.
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Матрица_инцидентности_графа&oldid=3851»