Основные понятия теории графов

Левый берег

Правый берег

Коэффициент напряженности работ

Характеризует степень свободы в сроках начала и окончания работ, не лежащих на критическом пути

Kн = t(Lij)max - t(штрих)(Lкр)/ (t(Lкр) - t(штрих)(Lкр))

Существовала популярная задача: можно ли, выйдя из дома, вернуться обратно, пройдя по каждому мосту ровно один раз?

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

Задачу о мостах Эйлер сформулировал так: можно ли, начав движение из любой вершины, и двигаясь вдоль линий, пройти по каждой линии точно по одному разу и вернуться в исходную вершину?

В современной постановке задача звучит так: существует ли в данном мультиграфе простой цикл, содержащий все ребра?

В своей работе Эйлер

1) доказал, что эта задача не имеет решения;

2) сформулировал и доказал необходимое и достаточное условие существования в произвольном графе такого (Эйлерова) цикла.

Потом о теории графов забыли, чтобы вспомнить в 19 веке, когда возникли задачи исследования электрических цепей, моделей кристаллов и структур молекул. Новый всплеск интереса к теории графов приходится на средину 20 века. Выяснилось, что к задачам о графах сводится множество производственных и научных задач – прокладка трасс, проектирование систем управления и интегральных схем, построение логических схем в экономике, химии, биологии. В терминах теории графов формулируются основные алгоритмы, связанные с перебором вариантов. Без преувеличения можно сказать, что теория графов – язык дискретной математики.

Изображение графа в виде точек и линий – это лишь наиболее наглядный способ их представления. Формально граф определяется так: граф – это пара объектов G = (V, E), где V – некоторое конечное множество, Е – отношение на V: E ÍV´V. V – множество вершин, E – множество ребер.

Ребро принято обозначать либо как элемент Е: e₁, …, e_m, e_j ÎE, либо указанием его начальной и конечной вершины (v_i, v_j). Второе обозначение не всегда однозначно, например, в задаче о мостах обозначению (v₁, v₃) соответствуют два различных ребра.

Def. Графом без кратных ребер называется граф, в котором для любых i, j существует единственное ребро e_k = (v_i, v_j). Граф с кратными ребрами называется еще мультиграфом.

Def. Пусть u, v – вершины, е = (u, v) – соединяющее их ребро. Тогда вершина u и ребро e инцидентны друг другу (также как и v и е). Два ребра, инцидентные одной вершине называются смежными. Две вершины, инцидентные одному ребру также называются смежными.

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

Def. Граф называется полным, если любые его две вершины смежны, E = V´ V. 0-граф – граф без ребер. Изолированная вершина – не смежная ни с одной другой вершиной.

Def. Дополнение графа , где = (V´V) \ E.