КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Разделяющие множества. РазрезыПусть - некоторый связный граф. Подмножество ребер графа называется разделяющим множеством, если удаление их из графа изменяет число компонент связности. Разделяющее множество называется разрезом графа, если любое его собственно подмножество не является разделяющим. Пример - разделяющее множество, разрез. цикл разрез (коцикл) Коциклический ранг - число линейно независимых коциклов графа. . Пример Алгоритм нахождения базисной системы разрезов 1. Построить остов графа . Пример
Число коциклов в графе равно . Устойчивость графа
|