ТОР 5 статей: Методические подходы к анализу финансового состояния предприятия Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века Характеристика шлифовальных кругов и ее маркировка Служебные части речи. Предлог. Союз. Частицы КАТЕГОРИИ:
|
Глава 5. Элементы теории графов.Основные понятия теории графов. Теория графов представляет собой область дискретной математики, особенностью которой является геометрический подход к изучению объектов и связей между ними. Графы используются при анализе и проектировании сетей электроснабжения, водоснабжения, газоснабжения, теплоснабжения; при анализе и проектировании транспортных сетей, грузовых и пассажирских перевозок и т.д. Основной объект теории графов – граф – совокупность двух множеств – вершин и ребер. Пример: схема автодорог, соединяющие населенные пункты Московской области. Множество точек (населенных пунктов) – это множество вершин: . Соединяющие линии (автодороги) – множество ребер: Два множества в объединении образуют граф: G=(V,X). Некоторые ребра могут быть изображены в виде стрелок, направленных от начальной вершины к конечной. Их называют дугами. Граф называют ориентированным (орграф), если он содержит дуги. Неориентированный граф состоит только из ребер. Смешанным называют граф, содержащий и ребра и дуги. Один и тот же граф можно изобразить по-разному. Вершины можно располагать по своему усмотрению и произвольно выбирать форму соединяющих линий. В этом проявляется изоморфизм графов. Ребро, концевые вершины которого совпадают, называется петлей. Пары вершин графа могут соединяться двумя и более ребрами (дугами одного направления). Такие дуги (ребра) называются кратными. Граф с кратными дугами (ребрами) называется мультиграфом. Изолированная вершина не соединена с другими вершинами. Пример: З адан граф , состоящий из вершин и ребер . -- изолированная вершина, и -- кратные ребра, -- петля, и -- концевые вершины ребра . Пример: З адан орграф . У дуги вершина -- начальная, а вершина -- конечная; -- петля. Маршрут длины m – это последовательность m ребер графа (не обязательно различных) таких, что любые два соседних ребра имеют общую концевую вершину. Замкнутый маршрут приводит в ту же вершину, из которой он начался. Цепь – это маршрут, все ребра которого различны. Простая цепь – это цепь без повторяющихся вершин. Замкнутая цепь называется циклом. Простой цикл – это простая замкнутая цепь. Пример: Задан граф G. -- это маршрут длины 6, соединяющий вершины и . -- замкнутый маршрут длины 7. Он начинается и заканчивается в вершине . -- цепь длины 5 (все ребра в ней различны). Эта цепь не является простой, т.к. при обходе вершину мы посетили два раза. -- пример простой цепи (все вершины на нашем пути были различны). -- цикл. -- простой цикл. В случае орграфа вместо слова «цепь» говорят «путь», а слово «цикл» заменяют на слово «контур». Итак, для задания графа необходимо указать два множества: V – множество вершин и X – множество ребер или дуг. Но при большом числе элементов рисунок графа становится громоздким. В этом случае используют матричный способ. Различают матрицу смежности и матрицу инцидентности. Если дан граф G с вершинами и ребрами , то Матрица смежности графа G – это квадратная матрица A(G) размерности n x n (n – число вершин) с элементами Матрица инцидентности графа G – это матрица В(G) размера n x m (n – число вершин, m – число ребер) с элементами Пример: Для графа G построим матрицу смежности А(G) и матрицу инцидентности В(G). Так как у графа 5 вершин и 6 ребер, то размер матрицы А(G) будет 5x5, а матрицы В(G) – 5x6. , . Граф G называется связным, если для любых двух его вершин существует маршрут, их соединяющий. Связный граф, не содержащий циклов, называется деревом. Пример: генеалогический граф (родословное дерево), совокупность всех файлов на дискете. Граф называется структурным (сетью), если ребра помечены числами. Вершины сети называют узлами, ребра – дугами. Код дерева – последовательность 0 и 1, количество которых в 2 раза больше числа ребер и число нулей равно числу единиц. Начинать обход нужно от корня дерева. По каждому ребру нужно пройти дважды. Первый проход по ребру отмечается 0. Повторный проход – 1. Из всех возможных вариантов выбирается обход по крайнему левому ребру. Заканчивается в корне. Пример: определим код, соответствующий следующему дереву. Обозначим ребра дерева буквами латинского алфавита. Тогда обход дерева задается следующей последовательностью: a,b,b,c,c,a,d,e,e,f,f,d. По этой последовательности построим код дерева. Двигаемся по последовательности слева направо. Если буква встречается в последовательности первый раз, то пишем 0, второй – 1. Тогда код равен 001011001011. По коду дерева можно восстановить само дерево. Двигаемся по последовательности 0 и 1 слева направо. Если очередной символ равен 0, то рисуем новое ребро, если – 1, то двигаемся обратно. Пример: коду 00011001011101 соответствует следующее дерево. Задачи
Не нашли, что искали? Воспользуйтесь поиском:
|