Студопедия

КАТЕГОРИИ:

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


Внутренняя устойчивость графа




Подмножество вершин графа называется внутренне устойчивым, если они попарно несмежны между собой. Внутренне устойчивое множество вершин называется пустым подграфом, если при добавлении хотя бы одной вершины свойство внутренней устойчивости пропадает.

Пример

- не является внутренне устойчивым - является внутренне устойчивым (но не является пустым подграфом) - является внутренне устойчивым (и является пустым подграфом)

Мощность максимального пустого подграфа называется числом внутренней устойчивости графа .

Пусть - некоторый граф, - некоторая вершина, - окрестность вершины . Неокрестность (коокрестность) вершины графа обозначим - подграф графа , порожденный .

Теорема
Пустой подграф, содержащий вершину содержит по крайней мере одну вершину из коокрестности вершины .


Поделиться:

Дата добавления: 2015-02-10; просмотров: 250; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты