-------------------
|
Множества Методы науки Обозначения Язык математики Определения Математика в физике Аксиомы множества Алгебра Алгебра логики Теория графов Теория моноидов Теория групп Конечные группы Конечные группы примеры Конечные группы таблица умножения Теория группоидов Группы ли Алгебра ли Кольцо тело поле Аффинное пространство Линейное пространство Векторная алгебра Тензорное пространство Тензорное поле Геометрия Парадоксы математики ТОПОЛОГИЯ ---Load files---
|
Поиск на странице - нажмите "Ctrl+F", Поиск на сайте - поле ввода "Яндекс-Найти" на "шапке", Поиск в интернете - 1) выделите текст, 2) нажмите правую клавишу мыши и 3) выберите поисковик. 1 Теория графов. Основные понятияАппарат теории графов широко используется в различных приложениях и, в частности, в математическом обеспечении САПР. Основные области его применения — математическое моделирование и задачи структурного синтеза. Графом G(X, U) называют совокупность множества вершин X = (x1, x2, …, xn) и ребер U = (u1, u2, …, um), если каждое ребро
инцидентно двум вершинам, другими словами, является связью двух вершин. В частном случае в качестве этих двух вершин может дважды выступать одна и та же вершина, тогда ребро называется петлей. Подграфом графа (куском, частью) называется любое подмножество вершин графа со всеми инцидентными к ним ребрами этого графа. Инцидентность - отношение типа "лежит на" или "проходит через". Если связываемые вершины xi и xj в (1) упорядочены, то ребро становится направленным и называется дугой. Граф с направленными связями называют направленным графом (ориентированным графом или орграфом), в противном случае — ненаправленным (неориентированным). Граф называют смешанным, если в нем имеются как ребра, так и дуги. Ребра, соединяющие одинаковые вершины, — кратные или параллельные. Граф без петель, но с кратными ребрами — мультиграф. Максимальное число кратных ребер называется мультичислом графа. Две вершины (ребра) называют смежными, если они инцидентны одному и тому же ребру (вершине). Граф, в котором все вершины попарно смежны, — полный граф. Граф, в котором перемещаясь по ребрам от вершины к вершине, можно попасть в любую вершину, — связный граф. Граф без ребер называют нуль-графом (пустым графом), а вершины, не имеющие инцидентных ребер, называют изолированными. Вершина, инцидентная только одному ребру, называется висячей. Число ребер (дуг), инцидентных некоторой вершине xi, есть степень вершины xi. Полустепень захода вершины определяется числом входящих в вершину дуг, а полустепень исхода — числом исходящих дуг. Граф называется однородным (регулярным) степени t, если степени всех вершин одинаковы и равны t. Граф G1(X, U1) является частичным графом (суграфом) графа G2(X, U2), если U1 Ì U2. Т.е. в частичном графе сохраняются все вершины, а некоторые ребра опущены. Если опущены некоторые вершины и инцидентные им ребра, получим подграф. Граф G1(X1, U1) называется куском графа G2(X2, U2), если X1 Ì X2 и в U1 входят все ребра из U2, инцидентные X1. При удалении из графа некоторых вершин с инцидентными им ребрами и возможно еще некоторых отдельных ребер получаем частичный подграф. Вершинам и (или) ребрам могут быть приписаны некоторые количественные или качественные признаки, называемые весами, тогда граф называют взвешенным. Последовательность ребер графа, в которой любая пара соседних ребер имеет одну и ту же инцидентную вершину, называют маршрутом. В орграфах аналогом маршрута является путь, т.е. такая последовательность дуг, в которой конец одной дуги является началом другой дуги. Маршрут, все ребра которого различны, является цепью, а если различны все вершины, то маршрут — простая цепь. Замкнутая цепь является циклом, замкнутая простая цепь — простым циклом. Цикл, содержащий все ребра графа, называют эйлеровым циклом, а граф, имеющий эйлеров цикл, — графом Эйлера. Простой цикл, который включает все вершины графа, называют гамильтоновым циклом. Для орграфов понятиям цепь и цикл соответствуют понятия путь и контур. Простой путь - путь, в котором ни одна дуга не встречается дважды. Элементарный путь - путь, в котором ни одна вершина не встречается дважды. Контур - путь, у которого конечная вершина совпадает с начальной вершиной. Длиной пути (контура) называется число дуг пути (или сумма длин его дуг, если послед ние заданы).
Рис. 1. Пример графа Деревом графа называют связный неориентированный граф без циклов. Если при этом граф несвязный, то его название — лес. Любое дерево, построенное на n вершинах, содержит n—1 ребер, а лес, состоящий из n вершин и p деревьев, имеет n - p ребер. Если дерево содержит все вершины графа, то это остов или остовное дерево (покрывающее дерево). Дерево может быть выделено из любого (ненулевого) графа. Если дерево — покрывающее, то множество ребер графа разбивается на подмножество ветвей и подмножество хорд (дополнений ребер дерева). При этом связный граф, имеющий п вершин и k ребер, содержит n—1 ветвей и k – n + 1 хорд. Если граф несвязный, то число хорд, входящих в дополнение леса, равно k – n + p. Ориентированное дерево называется прадеревом. Начальная вершина прадерева называется корнем. Граф можно задать в виде рисунка, на котором вершины изображены точками или кружками, а ребра линиями (например, рис. 1), с помощью матрицы инцидентности или матрицы смежности, показанных для графа рис. 1 в табл. 1 и табл. 2 соответственно. В матрице инцидентности столбцы соответствуют вершинам, а строки — ребрам. Если вершина xq инцидентна ребру up, то pq-й элемент матрицы неориентированного графа равен единице, иначе нулю. В орграфе элемент матрицы инцидентности равен +1, если дуга входит в вершину, и -1, если выходит из вершины. Для неориентированного графа суммы элементов матрицы в каждой строке и в каждом столбце равны степеням соответствующих вершин. Таблица 1
В квадратной матрице смежности pq-й элемент равен числу ребер, соединяющих вершины xp и xq. В этом смысле к графам применимы все операции, выполняемые над множествами (объединение, пересечение, разность, произведение). Таблица 2
Если вершины графа распределены на два подмножества x1 и x2 таким образом, что связи имеются только между вершинами разных подмножеств, то такой граф называют двудольным графом (графом Кёнига). Ребро, удаление которого приводит к замене графа на два не связанных между собой подграфа, называют перешейком. Вершина, в которой граф можно разделить на две компоненты связности путем дублирования этой вершины в обеих компонентах, называется расщепляющейся. При изображении графа в виде геометрической фигуры существует большая свобода в размещении вершин и ребер (дуг) в пространстве. Два графа называются изоморфными, если они имеют одинаковое число вершин и если каждой паре вершин, соединенных ребром (дугой) в одном графе, соответствует такая же пара вершин, соединенных ребром (дугой) в другом графе. Граф Gi изоморфно вкладывается в граф G, если Gi изоморфен какому-либо суграфу или подграфу графа G. Ребрам (дугам) и вершинам графа часто приписываются количественные и качественные признаки, характерные свойства, называемые весами. Вес может означать длину соединения, пропускную способность канала связи, интенсивность переходов и т.п.. Взвешенные ориентированные графы называются сигнальными графами.
- - - ВЫ МОЖЕТЕ ОСТАВИТЬ ПЕРВЫЙ КОММЕНТАРИЙ! - - - ---Load files---
|
Время переоткрытия сайта 03 ч 49 м по Гр. Календарь на ДЕКАБРЬ месяц 2018 г.
---Load files---
|
U:1 V:1 N:2 |