|
В коммерческой деятельности коммерсантам постоянно приходится решать задачи поиска покупателей продукции, товаров, имеющихся в распоряжении у предприятий, клиентов-посредников как на территории России, так и за рубежом. При этом в движении постоянно пребывают люди, деньги, товары, документы, информация. После определения возможных мест, которые необходимо посетить, возникает задача выбора оптимального маршрута их посещения, так называемая задача коммивояжера.
Граф задается двумя множествами: непустым множеством X и множеством U, содержащим пары элементов из множества X. При этом элементы множества U могут повторяться, а также могут повторяться элементы в парах. Граф, заданный на множествах X и U, обозначается G = (X, U). Если элементы в парах множества U не упорядочены, то граф называется неориентированным, в противном случае — ориентированным, или орграфом.
Элементы множества X называют вершинами графа, а множества U — ребрами для неориентированного графа и дугами для орграфа. На плоскости граф задается в виде точек (вершин) и линий, соединяющих некоторые из них (ребер или дуг).
Вершины называются смежными, или соседними, если существует ребро, их соединяющее (х1, х2), (х3, х4), (х3, х5), (х4, х5), (х5, х6), вершины х3 и х6 несмежные.
Если вершина Является началом или концом ребра, то вершина и ребро называются инцидентными.
Степенью вершины называется число инцидентных ей ребер, степень вершины х обозначается d(x). Последовательность вершин и ребер, в которой конец предыдущего ребра совпадает с началом следующего, называется маршрутом. Цепью называется маршрут, в котором все ребра попарно различны. Простой называется цепь, в которой все вершины попарно различны. Граф называется связным, если для любых двух его вершин существует цепь, соединяющая эти вершины. асстоянием между вершинами связного графа называется длина самой короткой цепи, соединяющей вершины.
Диаметром графа называется максимальное расстояние между его вершинами.
Циклом (простым циклом) называется цепь (простая цепь), начало и конец которой совпадают).
Цикл в графе называется эйлеровым, если он содержит все ребра графа. Связный граф, в котором есть эйлеров цикл, называется эйлеровым графом. Подграфом графа G называется граф G1 с множеством вершин Х1 и множеством ребер U1, такой, что Х1 X, U1 U. Подграф называется собственным, если он отличен от самого графа, например G1 и G2.
Компонентой связности графа называется его связный подграф, не являющийся собственным подграфом никакого другого связного подграфа данного графа, на рис. 1.3 граф имеет две компоненты связности.
Вершина графа, удаление которой повышает число компонент связности, называется точкой сочленения. Под удалением вершины понимается удаление самой вершины и всех инцидентных ей ребер. Точкой сочленения является, например, вершина х3, удаление которой приводит к появлению третьей компоненты связности.
Вершина х1 является корнем дерева.
Граф называется полным, если любые две его вершины соединены ребром.
Граф называется регулярным степени d, если все его вершины имеют степень d. Регулярный граф, все вершины которого имеют степень 1, называется паросочетанием. Граф называется двухдольным, если множество его вершин X может быть разделено на два непересекающихся подмножества таким образом, что каждое ребро графа соединяет вершины из двух разных подмножеств.
Гамильтоновой цепью называется простая цепь, содержащая все вершины графа. Гамильтоновым циклом называется гамильтоновая цепь, начало и конец которой совпадают. Если в конец предыдущей цепи дописать вершину 6, получим гамильтонов цикл.
Граф называется гамильтоновым, если в нем имеется гамильтонов цикл.
Термин гамильтонов связано с именем голландского математика У. Гамильтона, который в 1859 г. предложил игру «Кругосветное путешествие». Каждой из двенадцати вершин додекаэдра соответствует один из городов мира. Необходимо, переезжая из города в город по ребрам додекаэдра, посетить каждый город только один раз и вернуться назад. Эта задача сводится к поиску простого цикла, проходящего через каждую вершину графа.
Задачи, касающиеся эйлеровых и гамильтоновых цепей и циклов, часто встречаются на практике. Например, в ситуациях, когда качество выполнения комплекса коммерческих операций, работ, мероприятий существенно зависит от последовательности, в которой они выполняются.
Граф называется взвешенным, если каждому его ребру поставлено в соответствие некоторое число, называемое весом ребра, например расстояние между городами, стоимость или время проезда между ними.
Предложенный вариант решения задачи коммивояжера представляет собой кольцевой маршрут, где каждый город посещается только один раз, начиная с любого населенного пункта.
Для ориентированных графов в основном все определения сохраняются, однако имеются некоторые отличия. Последовательность дуг, в которой конец предыдущей дуги совпадает с началом следующей, называется путем. Длина пути определяется количеством в нем дуг. Путь называется простым, если в нем дуга не встречается дважды, в противном случае он является составным. Путь, в котором никакая вершина не встречается дважды, называется элементарным. Путь, который начинается и заканчивается в одной и той же вершине, называется контуром.
В неориентированном графе пользуются термином не путь, а цепь, а вместо контура — цикл.
Для ориентированного графа вместо степени вершины вводится понятие полустепеней исхода и захода. Если вершина является началом дуги, то дуга называется исходящей из вершины, если концом, то — заходящей. Полустепенью исхода вершины d-(x) называется число дуг, исходящих из этой вершины, полустепенью захода d+(x) — число дуг, заходящих в вершину.
При выполнении анализа на компьютере граф неудобно задавать графически, а лучше представлять его в виде матриц, операции с которыми достаточно просто проводить на компьютере.
Известно несколько типов матриц, позволяющих задавать граф.
Матрицей смежности графа, содержащего n-вершин, называется квадратная матрица Аnхm, каждый элемент которой аij определяется следующим образом:
1, если вершины i и j соединены ребром или дугой;
0, в противном случае.
Для графа с кратными ребрами (дугами) вместо 1 записывается число ребер (дуг) между вершинами i и j.
Матрицу смежности чаще применяют для задания неориентированного графа. Для задания ориентированного графа лучше использовать матрицу инцидентности.
|
