Дискретная математика. Прокушев Л.А. - 35 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

33
номеров слева направо. Построение следующего уровня начинается с
вершины с меньшим номером. Например, для графа на рис. 2 построим
дерево от вершины v
2
как корня (рис. 5).
Путь от корня прадерева до других вершин – это элементарный путь
минимальной длины (по количеству дуг).
Получение отображений Гv, Г
n
v,
ˆ
Гv
– есть процесс нахождения
множества вершин, в которые можно прийти от вершины v. Аналогич-
но, обратные отображения Г
-
v, Г
- n
v,
ˆ
Гv
−
представляют множества
вершин, из которых можно прийти в вершину v (дуги (стрелки) схо-
дятся к вершине v).
Например, для графа на рис. 2 получим множества вершин, смеж-
ных с вершинами графа, в которые можно придти за одну дугу:
Гv
1
= {v
2
}; Гv
2
= {v
1
, v
3
}; Гv
3
= {v
3
, v
4
}; Гv
4
= {v
1
}; Гv
5
= {v
4
, v
5
}.
Эти же множества можно получить по матрице смежности графа на
рис. 2. Для каждой строки v
i
не нулевые значения в строке указывают
смежные вершины (обозначения столбцов), в которые можно прийти из
вершины v
i
за одну дугу.
Множества вершин, в которые можно прийти за две дуги от вер-
шин v
1
, v
2
:
Г
2
v
1
= Г{Гv
1
} = Г{v
2
} = {v
1
, v
3
};
Г
2
v
2
= Г{Гv
2
} = Г{v
1
, v
3
} = Гv
1
ИГv
3
= {v
2
} И {v
3
, v
4
} = {v
2
, v
3
, v
4
}.
Множества вершин, в которые можно прийти за три дуги от вер-
шин v
1
, v
2
:
Г
3
v
1
= Г{Г
2
v
1
} = Г{v
1
, v
3
} = Гv
1
∪Гv
3
= {v
2
}∪{v
3
, v
4
} = {v
2
, v
3
, v
4
};
Г
3
v
2
= Г{Г
2
v
2
) = Г{v
2
, v
3
, v
4
} = Гv
2
∪ Гv
3
∪ Гv
4
= {v
1
, v
3
} ∪ {v
3
, v
4
} ∪
{v
1
} = {v
1
, v
3
, v
4
}.
Транзитивные замыкания вершин v
1
, v
2
, т. е. множества вершин, в
которые можно придти от этих вершин без повторения дуг:
2
11 1 1
ˆ
{}vv v vΓ = ∪Γ ∪Γ ∪
…
= {v
1
} ∪ {v
2
} ∪ {v
1
, v
3
} ∪ {v
2
, v
3
, v
4
} =
={v
1
, v
2
, v
3
, v
4
};
2
22 2 2
ˆ
{}vv v vΓ = ∪Γ ∪Γ ∪
…
= {v
2
} ∪ {v
1
, v
3
} ∪ {v
2
, v
3
, v
4
} ∪ {v
1
, v
3
,
v
4
} = {v
1
, v
2
, v
3
, v
4
};
Из вершин v
1
, v
2
в вершину v
5
нельзя придти никаким путем.
Для графа на рис. 2 получим множества вершин, смежных с верши-
нами графа, из которых можно придти за одну дугу:
Г
-
v
1
= {v
2
, v
4
}; Г
-
v
2
= {v
1
}; Г
-
v
3
= {v
2
, v
3
}; Г
-
v
4
= {v
3
, v
5
}; Г
-
v
5
= {v
5
}.

Страницы