Введение 

     В коммерческой деятельности большинство  возникающих задач удобно представлять для восприятия и анализа в  виде сетей, которые позволяют ответить на два главных вопроса: до какого места необходимо дойти (цель) и какой путь следует избрать (как). Коммерческую деятельность можно рассматривать как совокупность задач, предназначенных для передвижения, складирования и распределения товаров, денег, документов, информации о поставках и покупателях воды, нефти, газа, электроэнергии, теле- и радиосистем. Наглядность и логическая обоснованность методов сетевого анализа позволяет выбрать довольно естественный подход к решению задач коммерческой деятельности. Сетевые модели для людей, не занимающихся научной работой, являются более понятными, чем другие модели, поскольку для них все же лучше один раз увидеть, чем сто раз услышать. В значительной степени методы сетевого анализа основаны на теории графов – области математики, началом развития которой явилась задача о кенигсбергских мостах, сформулированная швейцарским ученым Л. Эйлером в 1736 г. Через реку Прегель, на которой стоял город Кенигсберг, построено семь мостов (рис. 1), которые связывали с берегами и друг с другом два острова. Задача заключалась в том, чтобы пройти по всем мостам только один раз и вернуться обратно к началу маршрута. Эйлер доказал неразрешимость этой задачи.

     Позже Д.К. Максвелл и Г.Р. Кирхгоф на основе исследования электрических цепей сформулировали некоторые принципы сетевого анализа. Были разработаны методы расчета наибольшей пропускной способности телефонных линий. В 40-х годах в результате развития теории исследования операций был разработан ряд математических методов, необходимых для анализа больших систем. В 50–60-х годах проводились работы по построению новых сетевых моделей и разработке алгоритмов их решения на основе элементов теории графов.

 

      

     Теория  графов в последнее время широко используется в различных отраслях науки и техники, особенно в экономике  и социологии.

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

     Эйлер Леонард (1707–1783) швейцарский математик, механик, физик, астроном. Автор более 800 работ по различным разделам математики и другим наукам.

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

     .

     Граф  называется ориентированным, если указано направление дуг и неориентированным, если такое направление не указано. Примером неориентированного графа является карта дорог.

     В неориентированном графе понятие  дуга, путь, контур заменяются соответственно на ребро, цепь, цикл.

     .

     Граф  называется связанным, если любые его две вершины можно соединить цепью. Граф сильно связан, если для его двух любых вершин х_i ≠х_j существует путь, идущий из х_i и х_j.

     Граф, который не является связанным, может  быть разбит на конечное число связных  графов, называемых компонентами, или частями.

     На  рисунке 3 ребро к – мост, а на рисунке 4 вершина 1 – точка сочленения. 

       
 
 
 
 

 

      

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

     Если  вершин нечетной степени нет, то граф имеет замкнутый эйлеров путь. 

     В любом конечном графе сумма степеней вершин равна удвоенному числу его  ребер. В XIX в. Гамильтон придумал игру, состоящую в том, что на доске располагались города в виде додекаэдра  
 

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

             Графы 

     Граф - это пара (V,E), где V - конечное непустое множество объектов произвольной природы, называемых вершинами, а E - множество неупорядоченных пар <u,v> вершин из V называемых ребрами Говорят, что ребро s=<u,v> соединяет вершины u и v. Ребро s и вершина u называются инцидентными, а вершины u и v - смежными. Ребра, инцидентные одной и той же вершине, также называют смежными. Если ребро s=<u,v> встречается более одного раза, то s – кратное ребро. Ребро вида s=<u,u> называется петлей в вершине u. На рис.1 < 4,2 > - кратные ребра, < 1,1 > петля.

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

     Пример: G=(V,E);  V={1,2,3,4};  E=< (1,1), (1,2), (1,3), (2,4), (2,4) >  

       

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

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

     Вершину степени 0 называют изолированной.

     Граф  называют регулярным степени d, если степень  каждой его вершины равна d.

     Граф, не содержащий петель и кратных ребер, называется обыкновенным, или простым графом (simple graph). Во многих публикациях используется другая терминология: под графом понимается простой граф, граф с кратными ребрами называют мультиграфом, с петлями - псевдографом.

     Некоторые классы графов получили особые наименования. Граф с любым количеством вершин, не содержащий ребер, называется пустым. Обыкновенный граф с n вершинами, любая пара вершин которого соединена ребром, называется полным и обозначается K_n  

       

     Граф, вершины которого можно разбить  на непересекающиеся подмножества V₁ и V₂ так, что никакие две вершины, принадлежащие одному и тому же подмножеству, не смежны, называется двудольным (или бихроматическим, или графом Кенига) и обозначается B_mn (m=|V₁|, n=|V₂|, m+n=|V|). Полный двудольный граф - такой двудольный граф, что каждая вершина множества V₁ связана со всеми вершинами множества V₂, и наоборот; обозначение - K_mn.

      B₃₃ 

     Часть графа G = (V,E) - это такой граф G' = (V',E'), что V' принадлежит V и E' принадлежит E. Подграфом  графа G называется такая его часть G', которая вместе со всякой парой  вершин u, v содержит и ребро <u,v>, если только оно есть в G. Остовным подграфом (суграфом) графа G называется любой его подграф, содержащий то же множество вершин, что и G.

     Путь, соединяющий вершины u и v, - это последовательность вершин v(0), v(1),..., v(n) (n>=0) такая, что v(0)=u, u(n)=v и для любого i (0<= i <= n-1) вершины v(i) и v(i+1) соединены ребром. Длина  пути v(0), v(1),...,v(n) равна количеству его  ребер т.е. n. Путь замкнут, если v(0) = v(n). Путь называется простым, если все его  вершины различны. Замкнутый путь, в котором все ребра различны называется циклом. Простой цикл - это  замкнутый путь, все вершины которого, кроме v(0) и v(n), попарно различны. Гамильтоновым  называется граф, в котором существует простой цикл, содержащий все вершины  графа

 

     

     Основные задачи на графах

     Процедура поиска в ширину

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

     Идея  поиска в ширину состоит в том, чтобы посещать вершины в порядке  их удаленности от некоторой заранее  выбранной или указанной стартовой  вершины α. Иначе говоря, сначала  посещается сама вершина α, затем  все вершины, смежные с α, то есть находящиеся от нее на расстоянии 1, затем вершины, находящиеся от α на расстоянии 2, и т.д.

     Рассмотрим  алгоритм поиска в ширину с заданной стартовой вершиной 2. Вначале все  вершины помечаются как новые. Первой посещается вершина α, она становится единственной открытой вершиной. В  дальнейшем каждый очередной шаг  начинается с выбора некоторой открытой вершины x. Эта вершина становится активной. Далее исследуются ребра, инцидентные активной вершине. Если такое ребро соединяет вершину x с новой вершиной y, то вершина y посещается и превращается в открытую. Когда все ребра, инцидентные активной вершине, исследованы, она перестает быть активной и становится закрытой. После этого выбирается новая активная вершина, и описанные действия повторяются. Процесс заканчивается, когда множество открытых вершин становится пустым.

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

     Опишем процедуру  поиска в ширину из заданной стартовой  вершины α. В этом описании V(x) обозначает множество всех вершин, смежных с вершиной x, Q - очередь открытых вершин. Предполагается, что при посещении вершины она помечается как посещенная и эта пометка означает, что вершина уже не является новой.

     Ребра, исследуемые в процессе обхода графа, можно разделить на две категории: если ребро соединяет активную вершину x с новой вершиной y, то оно классифицируется как прямое, в противном случае - как обратное. В зависимости от решаемой задачи прямые и обратные ребра могут подвергаться различной обработке.

     Предположим, что алгоритм поиска в ширину применяется  к связному графу. Покажем, что в  этом случае по окончании обхода множество  всех прямых ребер образует дерево. Действительно, допустим, что на некотором  шаге работы алгоритма обнаруживается новое прямое ребро (x,y), а множество  прямых ребер, накопленных к этому  шагу, образует дерево F. Тогда вершина xпринадлежит дереву F, а вершина y не принадлежит ему. Поэтому при  добавлении к дереву F ребра (x,y) связность  сохранится, а циклов не появится.

     Эйлеровы циклы