Математическая культура. Мациевский С.В. - 44 стр.

                         § 5. Цепь Маркова
                                   И решил Браконьер в одиночку рискнуть,
                                   И, влекомый высокою целью,
                                   Он бесстрашно свернул на нехоженый путь
                                   И пошел по глухому ущелью.
                                              Льюис Кэрролл. Охота на Снарка.
                               п. 1. Орграф
    1. Определение. Орграфом, или ориентированным графом, называется
пара (V, A), где V — непустое множество элементов, называемых вершина-
ми, а A — множество упорядоченных (не обязательно различных) пар вершин
из V, называемых дугами, или ориентированными ребрами. Дуга, у которой
1-й элемент — вершина v, а второй — вершина w, называется дугой из v в w
и обозначается (v, w). Заметим, что дуги (v, w) и (w, v) различны!
    Граф, полученный из орграфа «удалением стрелок», т.е. заменой всех
дуг на ребра, называется основанием орграфа.
    Пример. Ниже приведены два орграфа и посередине — их основание.
         u          z              u            z              u   z


   v           w           v              w           v             w

    Упр. 1. Выпишите множество V вершин и множество A дуг этих оргра-
фов.
    Два орграфа изоморфны, если существует изоморфизм между их осно-
ваниями, сохраняющий порядок вершин на каждой дуге.
    Упр. 2. В примере приведены два орграфа. Они изоморфны? Почему?
    2. Орцикл. Ориентированный маршрут в орграфе — это последова-
тельность дуг, где окончание предыдущей является началом следующей.
Орцепь — это ориентированный маршрут, у которого все дуги различны.
Простая орцепь — это орцепь, у которой различны и все вершины, кроме,
быть может, первой и последней. Орцепь замкнута, когда ее первая вер-
шина совпадает с последней. Орцикл — это замкнутая простая орцепь.
    Упр. 3. Выпишите все три орцикла для орграфов из примера.
    3. Связность. Орграф связен, или слабо связен, если связно его осно-
вание. Другими словами, связный орграф нельзя представить в виде объе-
динения двух различных орграфов.
    Орграф сильно связен, или орсвязен, если для любых двух его вершин
v и w существует простая орцепь из v в w. Ясно, что любой сильно связный
граф связен, но обратное неверно.
    Упр. 4. Оба орграфа из примера связны. Они сильно связны? Почему?


                                    43