![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Определение. Фундаментальной системой разрезов
Фундаментальной системой разрезов называется система простых разрезов, определенных выбранным остовным деревом. Очевидно, что число разрезов в фундаментальной системе равно |V|-1. Понятие остова и коцикла являются противоположными в том смысле, что остову соответствует минимальное множество ребер, которые связывают посредством маршрутов все вершины графа. Коцикл же состоит из минимального числа ребер, отделяющих некоторые вершины связного графа от остальных. Пример
1 1 1. К(1, 2) 2. К(2, 3) V1={1} V1={1, 3} 2 3 V2={2, 3, 4, 5, 6} 2 3 V2={2, 4, 5, 6} 5 6 2 3 3. К(2, 5) V1={1, 2, 3} V2={4, 5, 6} 4 5 6
V1={1, 2, 3, 5, 6} V1={1, 2, 3, 4, 5} 6 V2={4} 4 V2={6} 5 5
Определим такое понятие как матрица фундаментальных разрезов К=[кij], в которой Построим фундаментальную матрицу разрезов для нашего примера. Для этого пронумеруем все ребра исходного графа. Сначала нумеруем хорды кодерева, а затем ребра остовного дерева. К= Число строк матрицы равно |V|-1, а число столбцов – q. Вторая часть матрицы представляет собой единичную матрицу размером (|V|-1)х(|V|-1), т.е. К=(К1 |К2), где К2- единичную матрица. Между матрицей фундаментальных циклов и матрицей фундаментальных разрезов существует следующая связь: К1 =С2Т То есть получив одну матрицу, вторую получаем автоматом.
|