Реферат Курсовая Конспект
Разрезы - раздел Математика, Остовы графов Понятие Разреза Играет Важную Роль При Изучении Вопросов, Связанных С Отделен...
|
Понятие разреза играет важную роль при изучении вопросов, связанных с отделением одного множества вершин графа от другого. Такие задачи возникают, например, при изучении потоков в сетях (сетью называется связный орграф G= потоком в сети G называется функция , которая ставит в соответствие дуги некоторое число- вес дуги). В этих задачах фундаментальную роль играют изучение поперечных сечений сети (т.е. множеств дуг, которые соединяют вершины двух непересекающихся множеств вершин) и нахождение ограниченного поперечного сечения, которое является самым узким местом. Эти узкие места определяют пропускную способность системы в целом.
Пусть G= - неорграф = разбиение множества M. Разрезом графа G (по разбиению ) называется множество всех ребер, соединяющих вершины из M1 с вершинами из M2 (рис. 4.46). Отметим, что в связном графе любой разрез непуст.
Непустой разрез K неорграфа G называется простым разрезом или коциклом, если любое непустое собственное подмножество K̕ K не является разрезом ни по какому разбиению. Другими словами, из K нельзя удалить ни одно ребро с тем,чтобы множество было непустым разрезом.
M₁ Разрез M₂
– Конец работы –
Эта тема принадлежит разделу:
тема quot Элементы теории графов Виды и способы задания графов quot... Даны населенные пункты расстояния между которыми известны Требуется найти маршрут проходящий через все пункты по...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Разрезы
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Твитнуть |
Новости и инфо для студентов