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