double arrow

ГАМИЛЬТОНОВЫ ПУТИ И КОНТУРЫ

3

В 1857 г. ирландский математик Вилльям Гамильтон (1805-1865) предложил игру "путешествие по додекаэдру" (рис.14а), где нужно было прогуляться по ребрам через все вершины, не попадая ни в одну из них дважды (додекаэдр - многогранник, гранями которого служат пятиугольники - 20 вершин и 30 ребер). При желании додекаэдр можно (вырезав грань АBCDE) развернуть на плоскости (рис.14b) и обнаружить достаточно простой порядок перехода (рис.14с).

Рис.14

 

Путь в графе, проходящий через все вершины графа только по одному разу, называется гамильтоновым. Если он замкнут (конец пути совпадает с его началом, говорят о гамильтоновом контуре.

В полном графе (любая пара вершин соединена путем хотя бы в одном направлении) всегда есть гамильтонов путь. К сожалению, для любого графа конструктивный алгоритм отсутствует.

Эйлеровы и гамильтоновы пути сходны по способу задания. Первые содержат все ребра, по одному разу каждое, вторые - все вершины, по одному разу каждую. Но, несмотря на внешнее сходство, задачи их поиска резко отличаются по степени трудности. Для решения вопроса о наличии эйлерова цикла в графе достаточно выяснить, все ли его вершины четны. Критерий же существования гамильтонова цикла в произвольном графе еще не найден.

Сетевые графики

для инженера граф - это набор кружков (прямоугольников, треугольников и проч.), соединенных направленными или ненаправленными отрезками. В этом случае сами кружки (или другие используемые фигуры) по терминологии теории графов будут называться "вершинами", а соединяющие их ненаправленные отрезки - "ребрами", направленные (стрелки) - "дугами". Если все отрезки являются направленными, граф называется ориентированным, если ненаправленными - неориентированным.

Наиболее распространенный тип сетевого графика работ представляет систему кружков и соединяющих их направленных отрезков (стрелок), где стрелки отображают сами работы, а кружки на их концах ("события") - начало или окончание этих работ.

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

В самих кружках (разделенных на секторы) также содержится информация, смысл которой будет пояснен в дальнейшем. Фрагмент возможного сетевого графика с такими данными представлен на рисунке ниже.

В графике могут использоваться пунктирные стрелки - это так называемые "зависимости" (фиктивные работы), не требующие ни времени, ни ресурсов.

Они указывают на то, что "событие", на которое направлена пунктирная стрелка, может происходить только после свершения события, из которого исходит эта стрелка.

Корректировка сетевых графиков производится как на этапе их составления, так и использования. Она состоит в оптимизации строительных работ по времени и по ресурсам (в частности по движению рабочей силы). Если, например, сетевой график не обеспечивает выполнения работ в необходимые сроки (нормативные или установленные контрактом) производится его корректировка по времени, т.е. сокращается продолжительность критического пути.

 

 


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  


3

Сейчас читают про: