![]() ТОР 5 статей: Методические подходы к анализу финансового состояния предприятия Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века Характеристика шлифовальных кругов и ее маркировка Служебные части речи. Предлог. Союз. Частицы КАТЕГОРИИ:
|
Глава 5. Элементы теории графов.Основные понятия теории графов. Теория графов представляет собой область дискретной математики, особенностью которой является геометрический подход к изучению объектов и связей между ними. Графы используются при анализе и проектировании сетей электроснабжения, водоснабжения, газоснабжения, теплоснабжения; при анализе и проектировании транспортных сетей, грузовых и пассажирских перевозок и т.д. Основной объект теории графов – граф – совокупность двух множеств – вершин и ребер. Пример: схема автодорог, соединяющие населенные пункты Московской области. Множество точек (населенных пунктов) – это множество вершин: Два множества в объединении образуют граф: G=(V,X). Некоторые ребра могут быть изображены в виде стрелок, направленных от начальной вершины к конечной. Их называют дугами. Граф называют ориентированным (орграф), если он содержит дуги. Неориентированный граф состоит только из ребер. Смешанным называют граф, содержащий и ребра и дуги. Один и тот же граф можно изобразить по-разному. Вершины можно располагать по своему усмотрению и произвольно выбирать форму соединяющих линий. В этом проявляется изоморфизм графов. Ребро, концевые вершины которого совпадают, называется петлей. Пары вершин графа могут соединяться двумя и более ребрами (дугами одного направления). Такие дуги (ребра) называются кратными. Граф с кратными дугами (ребрами) называется мультиграфом. Изолированная вершина не соединена с другими вершинами. Пример: З адан граф
Пример: З адан орграф Маршрут длины m – это последовательность m ребер графа Пример: Задан граф G.
В случае орграфа вместо слова «цепь» говорят «путь», а слово «цикл» заменяют на слово «контур». Итак, для задания графа необходимо указать два множества: 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 соответствует следующее дерево. Задачи
Не нашли, что искали? Воспользуйтесь поиском:
|