§ 2.3.3. Матрица инцидентности Задать отношение инцидентности - значит указать, какие вершины и ребра графа являются инцидентными. Такое отношение задается матрицей инцидентности.
Пусть задан (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>. При построении порождённого графа из исходного удаляются некоторые вершины и все инцидентные удалённым вершинам дуги (рёбра).