Поиск клик в графах — страница 2

  • Просмотров 2644
  • Скачиваний 422
  • Размер файла 188
    Кб

таксономии, паралельных вычмслениях на ЭВМ, при размещении предприятий обслуживания, а также источников и потребителей в энергосистемах. Часть 1 Теоретическая часть к курсовому проекту Глава1 Теория графов Понятие графа Графом G(X,U) называется совокупность двух объектов некоторого множества X и отображения этого множества в себя Г. При геометрическом представлении графа элементы множества Х изображаются точками плоскости и

называются вершинами графа. Линии, соединяющие любые пары точек x и y, из которых у является отображением х, называются дугами графа. Дуги графа имеют направление, обозначаемое стрелкой, которая направлена острием от элемента х к его отображению у. Вершины и линии графа Две вершины А и В являются граничными вершинами дуги, если А- начало дуги, а В ее конец. Смежными называются различные дуги, имеющие общую граничную точку. Две

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

степенью Р(х)<2 - антиузлом. Полустепень захода Р+(х) вершины х - количество дуг, заходящих в данную вершину. Полустепень исхода Р-(х) - количество дуг, исходящих из данной вершины. Последовательность линий на графе Путь - последовательность дуг (U1, U2, ...Un), в которой конец каждой предыдущей дуги совпадает с началом последующей. Путь может быть конечным и бесконечным. Путь называется простым, если в нем никакая дуга не встречается

дважды, и составным, если любая из дуг встречается более одного раза. Путь, в котором ни одна из вершин не встречается более одного раза, называется элементарным путем. Гамильтонов путь - путь проходящий через все вершины, но только по одному разу, Эллеров путь - путь содержащий все дуги графа, при этом только по одному разу. Длинна пути - число дуг последовательности (U1, U2, ...Un). Ветвь - путь, в котором начальная и конечная вершины

являются узлами. Дуга (x,y) называется замыкающей, если удаление ее не приводит к аннулированию пути из x в y. Контур - конечный путь, начинающийся и заканчивающийся в одной и той же вершине. Контур единичной длинны называется петлей. Ориентированный граф - граф, у которого вершины соединяются направляющими стрелками. Графы можно рассматривать с учетом или без учета ориентации его дуг. Разновидности графов Нуль-граф - граф (X,U),