Успешное подключения к БД.

-------------------
Вы знаете, как устроен наш мир?



---Load files---
Совет: если изображения отображаются неправильно, попробуйте очистить кеш браузера!
Поиск на странице - нажмите "Ctrl+F", Поиск на сайте - поле ввода "Яндекс-Найти" на "шапке",
Поиск в интернете - 1) выделите текст, 2) нажмите правую клавишу мыши и 3) выберите поисковик.

С О Д Е Р Ж А Н И Е

------- Тимин В.А. (mail: timinva@yandex.ru) Дата последней загрузки: October 31 2017. -------
Ссылка на этот материал: teoriya_grafov.htm)
Теория графов

1         Теория графов. Основные понятия

Аппарат теории графов широко используется в различных приложениях и, в частности, в математическом обеспечении САПР. Основные области его применения — математическое моделирование и задачи структурного синтеза.

Графом G(X, U) называют совокупность множества вершин X = (x1, x2, …, xn) и ребер U = (u1, u2, …, um), если каждое ребро

uk = (xi, xj)

 (1)

инцидентно двум вершинам, другими словами, является связью двух вершин. В частном случае в качестве этих двух вершин может дважды выступать одна и та же вершина, тогда ребро называется петлей. Подграфом графа (куском, частью) называется любое подмножество вершин графа со всеми инцидентными к ним ребрами этого графа.

Инцидентность - отношение типа "лежит на" или "проходит через". Если связываемые вершины 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 ветвей и kn + 1 хорд. Если граф несвязный, то число хорд, входящих в дополнение леса, равно kn + p. Ориентированное дерево называется прадеревом. Начальная вершина прадерева называется корнем.

Граф можно задать в виде рисунка, на котором вершины изображены точками или кружками, а ребра линиями (например, рис. 1), с помощью матрицы инцидентности или матрицы смежности, показанных для графа рис. 1 в табл. 1 и табл. 2 соответственно.

В матрице инцидентности столбцы соответствуют вершинам, а строки — ребрам. Если вершина xq инцидентна ребру up, то pq-й элемент матрицы неориентированного графа равен единице, иначе нулю. В орграфе элемент матрицы инцидентности равен +1, если дуга входит в вершину, и -1, если выходит из вершины. Для неориентированного графа суммы элементов матрицы в каждой строке и в каждом столбце равны степеням соответствующих вершин.

Таблица 1    

 

1

1

0

0

0

0

1

0

1

0

0

0

1

0

0

0

0

1

0

1

0

1

0

0

0

0

1

0

1

0

0

0

1

0

0

1

0

1

1

0

0

0

0

0

0

1

1

0

0

0

0

0

1

1

0

0

0

1

0

1

 

В квадратной матрице смежности pq-й элемент равен числу ребер, соединяющих вершины xp и xq. В этом смысле к графам применимы все операции, выполняемые над множествами (объединение, пересечение, разность, произведение).

Таблица 2

 

0

1

1

0

0

1

1

0

1

1

0

0

1

1

0

0

1

1

0

1

0

0

1

1

0

0

1

1

0

1

1

0

1

1

1

0

 

Если вершины графа распределены на два подмножества x1 и x2 таким образом, что связи имеются только между вершинами разных подмножеств, то такой граф называют двудольным графом (графом Кёнига).

Ребро, удаление которого приводит к замене графа на два не связанных между собой подграфа, называют перешейком. Вершина, в которой граф можно разделить на две компоненты связности путем дублирования этой вершины в обеих компонентах, называется расщепляющейся.

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

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

 

Ссылка на этот материал: teoriya_grafov.htm)

- - - ВЫ МОЖЕТЕ ОСТАВИТЬ ПЕРВЫЙ КОММЕНТАРИЙ! - - -


Введите логин:      Введите эл.адрес:

Введите пароль:    Ваш телефон:        

Введите Ваш комментарий:
Формулы:

(возможно использование BB-кодов для оформления комментария и кодов LaTeX для ввода формул)

Решите пример: 12 to increase on 6 =

---Load files---
Сегодня - 20_08_2019
Время переоткрытия сайта 14 ч 36 м по Гр.
Календарь
на АВГУСТ месяц 2018 г.
Пн Вт Ср Чт Пт Сб Вс
      1; 2; 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31 1
(8 431)

---Load files---

---Load files---

© Все права защищены 2017-2019 При использовании материалов сайта ссылка на http://lowsofphisics.ru обязательна.

В НАЧАЛО
КОММЕНТ
В КОНЕЦ
U:5 V:6
Уникальных посетителей: 5 Просмотров: 6