русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Ядро графа


Дата добавления: 2015-07-23; просмотров: 5013; Нарушение авторских прав


 

Пусть G = (V, E) – ориентированный граф. Множество вершин N V называется ядром, если оно одновременно внешне и внутренне устойчиво.

 

Примеры.Граф на рис. 2 обладает единственным ядром {2, 4}. Граф на рис. 3 ядер не имеет.


 

1

 

 

 

 

 

 

Рис. 3

 

Граф на рис. 4 имеет два ядра: {1, 3} и {2, 4}.

 

 

2 3

 

 

1 4

 

 

Рис. 4

 

 

Теорема.Множество вершин ориентированного графа является ядром тогда и только тогда, когда оно максимальное внутренне устойчивое и минимальное внешне устойчивое множество.

Предположим, что ориентированный граф G = (V, E) представляет некоторое отношение предпочтения. Более точно: множество вершин V – это множество вариантов (альтернатив); наличие дуги из x в y означает, что y «лучше», чем x. Для ситуаций выбора типично, когда известно, что значит «лучше», но не известно, что значит «хорошо». Ядро, которое называют решением задачи выбора по Нейману – Моргенштерну, это в


 

 

некотором смысле множество «хороших» вариантов. В соответствии с определением для каждого невыбранного варианта в ядре содержится вариант, который лучше него. Кроме того, если некоторый вариант попал в ядро, худшие, чем он, варианты в это ядро уже не попадут. В «простых» случаях ядро дает естественное решение задачи выбора. Так, если граф G не содержит циклов, а отношение предпочтения транзитивно, то единственным ядром графа G служит множество вершин уровня 0 (множество недоминируемых альтернатив). Ядро дает решение задачи выбора и в более сложных случаях.

 

Пример. Пусть имеются шесть вариантов {1, 2, 3, 4, 5, 6}, которые оцениваются по четырем критериям. Возможные оценки по каждому критерию: 0, 1, 2, 3, 4.




 

 

В следующей таблице приведены оценки вариантов.

 

 

Показатели П1 П2 П3 П4
Варианты

 

Будем считать, что вариант x лучше варианта y, если x не содержит ни одной нулевой оценки и число показателей, по которым он лучше варианта y, больше, чем число показателей, по которым y лучше, чем x. На рис. 5 изображен

соответствующий граф предпочтений.

 

 

5 6

 

 

 

1 2

 

 

Рис. 5

 

Единственным ядром графа служит множество {2, 5}. Это и есть множество «хороших» вариантов. Чтобы сделать выбор


 

 

между вторым и пятым вариантом, требуется привлечь дополнительную информацию.

 

Пример. Граф на рис. 6 обладает двумя ядрами: {1, 5, 7}

 

и {2, 4, 6, 8}.

 

 

1 2

 

3 5

 

 

6 7 8

 

Рис. 6

 

 

Вопросы для итогового контроля

1. Множества

1. Понятие множества

2. Подмножества

3. Пересечение и объединение множеств

4. Разность множеств. Дополнение множества

5. Свойства операций над множествами

6. Диаграммы Эйлера – Венна

7. Прямое произведение множеств

2. Отображения и соответствия

1. Понятие отображения

2. Специальные виды отображений

3. Операции

4. Характеристические функции

5. Соответствия

6. Композиция соответствий

3. Отношения

1. Понятие отношения

2. Свойства бинарных отношений

3.Отношения эквивалентности

4. Натуральные числа

1. Натуральный ряд

2. Метод математической индукции



<== предыдущая лекция | следующая лекция ==>
Внутренняя устойчивость | Графы. Основные понятия


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.602 сек.