Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Определение. Цикломатическое число графа , с к компонентами связности






Цикломатическое число графа , с к компонентами связности

 

Цикломатическое число дерева равно 0. Цикломатическое число леса равно сумме цикломатических чисел деревьев и также равно 0.

 

Теорема

Цикломатическое число графа всегда больше равно 0.

 

Доказательство

Цикломатическое число несвязного графа равно сумме цикломатических чисел его связных компонент. Поэтому будем рассматривать связный граф.

Если - не дерево, то в нем существует хотя бы один цикл. Удалим из графа одно из ребер цикла, которое не является мостом, получим граф . Если в существует цикл, то уберем опять одно из ребер цикла, получим граф . Процесс будем повторять до тех пор, пока не получим граф без циклов. будет деревом и для него будет выполняться соотношения:

Тогда .

 


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.006 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал