Задать отношение инцидентности - значит указать, какие вершины и ребра графа являются инцидентными. Такое отношение задается матрицей инцидентности.
Пусть задан (n,m) – орграф G = (Х,А). Матрица инцидентности графа G обозначается через В = [bij] и является матрицей размерности n ´ m, определяемой следующим образом:
bij = 1, если xi является начальной вершиной дуги аj,
bij = -1, если xi является конечной вершиной дуги аj,
bij = 0, если xi не является концевой вершиной дуги аj, или если аj - петля.
Пример 5. Для графа G матрица инцидентности имеет вид
| a1
| a2
| a3
| a4
| a5
| a6
| a7
| a8
| a9
| a10
| x1
| 1
| 1
| 0
| 0
| 0
| 0
| 0
| -1
| -1
| 0
| x2
| -1
| 0
| -1
| 1
| 0
| 0
| 0
| 0
| 0
| 0
| x3
| 0
| -1
| 1
| 0
| -1
| 0
| 0
| 0
| 0
| 1
| x4
| 0
| 0
| 0
| 0
| 1
| -1
| 0
| 0
| 0
| 0
| x5
| 0
| 0
| 0
| -1
| 0
| 1
| -1
| 1
| 0
| 0
| x6
| 0
| 0
| 0
| 0
| 0
| 0
| 1
| 0
| 1
| -1
|
Поскольку каждая дуга, за исключением петель, инцидентна двум различным вершинам, то каждый столбец содержит:
- либо 1 и –1, а остальные нули;
- либо все нули.
Если G – неориентированный граф, то его матрица инциденций определяется также, за исключением того, что все элементы, равные -1, заменяются на +1.
Очевидно, что матрица инциденций нечувствительна к петлям.
§ 2.4. Подграфы
Для заданного графа можно определить подграфы. Рассмотрим два вида подграфов: остовные и порождённые.
Остовной подграф. Пусть дан неориентированный граф G=(V,E). Остовным подграфом GP графа G называется граф (V,EP), для которого ЕР Ì Е. Таким образом, остовной подграф имеет то же множество вершин, что и исходный граф G, но не все его рёбра.
Порождённый подграф. Пусть дан орграф G=(Х,А). Порождённым подграфом GS графа G называется граф (XS,AS), для которого XS Ì X и AS Ì A, причём в АS входят только те дуги, обе концевые вершины которых принадлежат множеству XS; для каждой вершины xi Î XS выполняется условие
ГS(xi) = Г(xi)Ç XS.
Таким образом, порождённый подграф состоит из подмножества вершин XS множества Х вершин исходного графа и всех таких дуг графа G, у которых начальные и конечные вершины принадлежат подмножеству XS. Иногда порождённый подграф GS обозначают <XS>. При построении порождённого графа из исходного удаляются некоторые вершины и все инцидентные удалённым вершинам дуги (рёбра).
Дата добавления: 2015-09-27 | Просмотры: 744 | Нарушение авторских прав
|