 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Операция дополнения графа
Пусть дан граф 
и 
. Дополнением графа 
называется граф 
с множеством верши 
, в котором две вершины смежные тогда и только тогда, когда они несмежные в графе . Из этого определения получается правило построения графа , для чего необходимо построить полный граф 
и удалить из него все ребра, принадлежащие графу . Очевидно, что, например, дополнением полного графа является пустой граф, и наоборот – дополнением пустого графа является полный граф. На рис. 2.11 Приведен граф , являющейся дополнением графа .
Рис. 2.11
Поиск по сайту: