Математика. Курзина В.М - 209 стр.

                                 209

полустепенью захода вершины v . Степенью di вершины ui графа G назы-
вается число дуг, инцидентных этой вершине.
      Обходом графа называется маршрут, содержащий все вершины или
ребра графа и обладающий определенными свойствами. Наиболее извест-
ными обходами графов являются эйлеровы и гамильтоновы цепи и циклы.
      Маршрут (замкнутый маршрут) называется            эйлеровой це-
пью(эйлеровым циклом), если он содержит все ребра графа и проходит че-
рез каждое ребро по одному разу. Имеется эффективный критерий сущест-
вования эйлеровых циклов (теорема Эйлера): связный граф имеет эйлеров
цикл тогда и только тогда, когда каждая его вершина имеет четную сте-
пень.
      Маршрут (замкнутый маршрут) называется гамильтоновой цепью
(гамильтоновым циклом), если он содержит все вершины графа и через
каждую проходит по одному разу. Известен ряд достаточных условий су-
ществования гамильтоновых циклов, например: граф не имеет петель и
кратных ребер и для любых двух его несмежных вершин сумма степеней
не меньше числа вершин этого графа; граф является плоским и четырех-
связным; граф не имеет петель и кратных ребер, а число n его вершин и
число m его ребер удовлетворяют условиям n ≥ 3 и m ≥ 0,5(n2 − 3n + 6).
      Граф называется гамильтоновым (эйлеровым), если он имеет га-
мильтонов (эйлеров) цикл. Граф называется гамильтоново связным, если
любые две его вершины соединены гамильтоновой цепью, и k-
гамильтоновым, если любая простая цепь длины k входит в некоторый га-
мильтонов цикл.
      Введенных понятий из теории графов достаточно для логического
описания теории, приводящей к методу критического пути, лежащего в
основе сетевого метода планирования.

              8.2. Сетевой график и его характеристики

      Проект (комплекс операций) − совокупность операций, необходимых
для достижения некоторой цели, длительность (детерминированная или
случайная) каждой из которых нам известна и которые связаны отношени-
ем порядка (обязательным предшествованием).
      Проект может быть представлен сетевым графиком .
      Сетевой график − это ориентированный граф без контуров. В сете-
вом графике главными элементами являются работа и событие.
      Работа − это активный процесс, протяженный во времени, требую-
щий затрат ресурсов, либо пассивный (ожидание), приводящий к достиже-
нию намеченного результата.
      Фиктивная работа − это связь между результатами работ (события-
ми), не требующая затрат времени и ресурсов.