Основные понятия теории графов - Нахождение максимального потока в графе
Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин "граф" впервые ввел в 1936 году венгерский математик Денеш Кениг. Графами были названы схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых.
С помощью графов часто упрощалось решение задач, сформулированных в различных областях знаний: в автоматике, электронике, физике, химии и др. С помощью графов изображаются схемы дорог, газопроводов, тепло - и электросети. Помогают графы в решении математических и экономических задач.
Простым графом G называется пара (V, E), где V - непустое конечное множество, элементы которого называются вершинами графа, а E - конечное множество неупорядоченных пар различных элементов из V, элементы множества E называются ребрами.
В дальнейшем будем рассматривать только простые графы, опуская при этом слово простые.
Если (u, v) - некоторое ребро графа G, то вершины u и v называются смежными, а вершины u и ребро (u, v), также как вершина v и ребро (u, v), называются инцидентными друг другу. Степенью вершины v в графе G называется число ребер графа G, инцидентных вершине v.
Пример графа представлен на рисунке 1.
V3 |
V4 |
V1 |
V5 |
V2 |
V6 |
Рисунок 1- Пример графа
В данном примере
V = {v1, v2, v3, v4, v5, v6},
E = {(v1, v2), (v2, v3), (v1, v3), (v3, v4), (v4, v5), (v4, v6), (v5, v6)}
Пусть G = (V, E) - некоторый граф, u и v - его вершины. Маршрутом в графе G, соединяющим вершины u и v, называется конечная чередующаяся последовательность вершин и ребер вида v1, e1, v2, e2,...,eK-1, vK, где v1,...,vK из V, а e1,...,eK-1 из E. Маршрут называют цепью, если все его ребра различны. Цепь называют путем (или простой цепью), если все ее вершины кроме, быть может, концевых различны. Если начальная и конечная вершина пути совпадают, то его называют замкнутым путем или циклом.
Граф называется связным графом, если для любых двух его вершин существует соединяющий их маршрут.
Теперь мы можем определить особый класс графов - деревья. Деревом называется связный граф без циклов.
Ориентированным графом D называется пара (V, A), где V - непустое конечное множество, элементы которого называются вершинами графа, а A - конечное множество упорядоченных пар различных элементов из V, элементы множества A называются дугами.
Подобно графам для ориентированных графов вводятся понятие смежности вершин, понятие инцидентности и так далее.
Основанием ориентированного графа D = (V, A), называется граф G = (V, E), где E = A, то есть упорядоченные пары вершин заменяются на неупорядоченные.
Транспортной сетью называется конечный Связный орграф G(V, E) без петель, каждой дуге которого поставлено в соответствие некоторое неотрицательное число c(), называемое пропускной способностью дуги, и существует:
- 1) ровно одна вершина, в которую не заходит ни одна дуга, называемая источником или началом сети; 2) ровно одна вершина, из которой не выходит ни одной дуги; эта вершина называется стоком или концом сети.
Потоком сети называется неотрицательная функция f(1) такая, что f(e) меньше или равно c(e). (Поток не может превышать пропускную способность дуги.)
Дуга называется насыщенной потоком f, если (Поток называется полным, если содержит насыщенную дугу f(e)=c(e).)
Разрезом L сети G(V, E) называется множество насыщенных дуг, отделяющих источник s от стока t.
Похожие статьи
-
Введение - Нахождение максимального потока в графе
Актуальность задачи о максимальном потоке постоянно возрастает вместе со строительством трубопроводов, новых дорог, роста пользователей Интернета и любых...
-
Основные понятия сетевых и графовых моделей Объектом исследования является сеть, состоящая из узлов и линий связи. Предполагается, что в сети имеется два...
-
При анализе больших объемов данных зачастую их можно представить в виде графа. Основными атрибутами графа являются вершины и ребра, поэтому изучение...
-
Свойство 1. Вероятность достоверного события равна единице. Действительно, если событие достоверно, то каждый элементарный исход испытания...
-
Гамильтоновы циклы, Основные понятия и определения - Гамильтоновы циклы
Название "гамильтонов цикл" произошло от задачи "Кругосветное путешествие" предложенной ирландским математиком Вильямом Гамильтоном в 1859 году. Нужно...
-
Введение, Основные положения - Эволюционные процедуры решения комбинаторных задач на графах
Среди набора комбинаторно-логических задач на графах важное место занимает проблема определения паросочетаний, раскраски графа, выделения в графе...
-
Пусть { , , ..., } - множество возможных состояний некоторой физической системы. В любой момент времени система может находиться только в одном...
-
Моделирование начинается с формирования предмета исследований -- системы понятий, отражающей существенные для моделирования характеристики объекта. Эта...
-
ФУНКЦИИ, Основные понятия - Свойства функций
Основные понятия При изучении различного рода явлений приходится иметь дело с совокупностью переменных величин, которые связаны между собой таким...
-
Модель в общем смысле (обобщенная модель) есть создаваемый с целью получения и (или) хранения информации специфический объект (в форме мысленного образа,...
-
Введение - Основные понятия теории вероятностей
Каждая наука, развивающая общую теорию какого-либо круга явлений, содержит ряд основных понятий, на которых она базируется. Таковы, например, в геометрии...
-
РЕШЕНИЕ ЗАДАЧИ О КОММИВОЯЖЕРЕ МЕТОДОМ ВЕТВЕЙ И ГРАНИЦ: ОСНОВНАЯ СХЕМА - Задача коммивояжера
Пусть - конечное множество и - вещественно-значная функция на нем; требуется найти минимум этой функции и элемент множества, на котором этот минимум...
-
О клике. Определим формально задачу поиска максимальной клики, согласно статьи On the maximum quasi-clique problem [17]. Пусть G=(V, E) - простой...
-
К основным понятиям и категориям статистической науки относятся следующие: - совокупность, - признак, - показатель, - система показателей и др....
-
Модели теории игр. Основные определения и термины В разных областях целенаправленной деятельности, например при разработке и эксплуатации АСУ, часто...
-
Конкретные модели процессов управления в социальных и экономических системах исходят из общей методологии, которую и формулируем в настоящей статье....
-
Пока неизвестно никакого простого критерия или алгебраического метода, позволяющего ответить на вопрос, существует или нет в произвольном графе G...
-
Введение - Моделирование крупномасштабной транспортной сети предфрактальными графами
Транспорт - важный стратегический комплекс, в значительной степени определяющий мощь экономики страны и обеспечивающий нужды общества в перемещении людей...
-
Задача поиска маршрутов в графе (путей в орграфе)
Задача поиска маршрутов в графе (путей в орграфе) Алгоритм Тэрри поиска маршрута в связном графе, соединяющем вершины и. Правила. 1) Идя по произвольному...
-
Определим понятие предфрактального графа индуктивно. Обозначим через - конечный связный n-вершинный граф с множеством вершин и множеством ребер, который...
-
О квази-клике. - Использование квази-клик для анализа графа рынка России
Квази-клика - представляет собой релаксацию строгого условия полноты клики, то есть допускается отсутствие некоторых ребер в искомом подграфе. На данный...
-
Основные понятия корреляционно-регрессионного анализа Теория и методы корреляционного анализа используются для выявления связи между случайными...
-
Понятие и применение графа рынка - Использование квази-клик для анализа графа рынка России
Динамика характеристик отражающих тенденцию поведения фондового рынка может быть интересна многим участникам фондовой биржи и, в особенности, инвесторам....
-
Основные понятия и отношения - Системная революция и принцип дуального управления
Все структурные образования и процессы, с которыми приходится иметь дело в систематике, существуют в самых различных по своей природе пространствах...
-
Основная теория сезонности временного ряда - Методы изучения сезонных колебаний. Примеры расчетов
Основными составляющими временного ряда являются тренд и сезонная компонента. Составляющие этих рядов могут представлять собой либо тренд, либо сезонную...
-
Опытным путем, задолго до появления молекулярно-кинетической теории, был открыт целый ряд законов, описывающих равновесные изопроцессы в идеальном газе....
-
ОСНОВНЫЕ ПОНЯТИЯ И ЗАКОНЫ ХИМИИ, Атомно-молекулярное учение - Основные понятия и законы химии
Химия - наука о веществах, закономерностях их превращений (физических и химических свойствах) и применении. В настоящее время известно более 100 тыс....
-
Основные понятия и обозначения Динамическое программирование как самостоятельная дисциплина сформировалась в пятидесятых годах двадцатого века. Большой...
-
Комплексные соединения - соед-я, обр-ся сочетанием нескольких, способных к существованию ионов, сост. из атома в опр. валентном сост-ии, связ. с одной...
-
Заключение - Основные понятия теории вероятностей
Эмпирическое "определение" вероятности связано с частотой наступления события исходя из того, что при достаточно большом числе испытаний частота должна...
-
Основные понятия теории экономико-математического моделирования Кибернетический подход к исследованию экономико-математических систем Обычно...
-
Наличие особых ситуаций на террайне зависит от характеристик его сложности. Ниже приведена возможная классификационная схема характеристик сложности...
-
При решении экономических задач часто анализировать ситуации, в которых сталкиваются интересы двух или более конкурирующих сторон, преследующих различные...
-
Кинетическая теория вещества - Строение и превращение веществ
Движением атомов и молекул с давних пор уже пытались объяснить тепловые явления. Параллельно с развитием этого, несомненно, существовавшего общего...
-
Классический способ задания вероятности. Примеры, Элементы комбинаторики - Теория вероятности
При данном способе пространство элементарных событий является конечным, и все элементарные события равновероятны. Тогда вероятность события определяется...
-
Формирование З -областей в матрице R осуществляется в процессе ее эволюционной модификации. Эволюционная модификация матрицы R производится путем...
-
ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ СКАЛЯРНЫХ И ВЕКТОРНЫХ ВЕЛИЧИН Величины называют Скалярными (скалярами), Если они после выбора единиц измерения полностью...
-
В зависимости от содержания задачи может быть два случая: когда ребра графа G единичной длины; когда ребра графа произвольной длины. Для каждого из этих...
-
Пусть имеется конечное число объектов, которые будем обозначать натуральными числами 1, 2, 3, ..., K и называть "носителем". Под кластеризованной...
-
Модели линейного программирования. Основные определения Еще одним классом задач экономико-математического моделирования являются задачи линейного...
Основные понятия теории графов - Нахождение максимального потока в графе