Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
Нуль-граф и полный граф
|
|
Существуют некоторые специальные графы, встречающиеся во многих приложениях теории графов. Будем пока опять рассматривать граф как наглядную схему,иллюстрирующую ход спортивных состязаний. Доначала сезона, пока еще никакие игры не проводились, на графе нет никаких ребер. Такой граф состоит из одних изолированных вершин, т. е. извершин, не соединенных никакими ребрами. Граф такого вида называется нуль-графом. На рис. 3приведены такие графы для случаев, когда число команд, или вершин, равно 1, 2, 3, 4 и 5. Эти нуль-графы обычно обозначаются символами O1, O2, O3 и т. д., такчто On – это нуль-граф с n вершинами, не имеющий ребер.
Рассмотрим другой крайний случай. Предположим, что по окончании сезона каждая команда сыграла по одному разу с каждой из остальных команд. Тогда на соответствующем графе каждая пара вершин будет соединена ребром. Такой граф называется полным графом. На рис. 4 изображены полные графы с числом вершин n = l, 2, 3, 4, 5.
Рис. 3. Нуль-графы для различного числа команд: 1,2,3,4 и 5
Рис. 4. Полные графы для различного числа команд: 1,2,3,4 и 5
Обозначим этиполные графы соответственно через U1, U2, U3, U4, U5, так что граф Un состоит из n вершин и ребер, соединяющих все возможные пары этих вершин. Этот граф можно представлять себе как n -угольник, в котором проведены все диагонали.
Имея некоторый граф, например граф G, изображенный на рис. 1, всегда можно превратить его в полный граф с теми же самыми вершинами, добавив недостающие ребра (т. е. ребра, соответствующие играм, которые только еще будут сыграны). На рис. 5 это сделано для графа, представленного на рис. 1 (еще не состоявшиеся игры изображены пунктиром).
Рис. 5. Граф с рис. 1, дополненный ребрами до полного графа
Можно также отдельно начертить граф, соответствующий пока еще не сыгранным, будущим играм. Для графа G при этом получится граф, изображенный на рис. 6.
Рис. 6. Граф 
, являющийся дополнением графа G с рис. 1 до полного графа
Этот новый граф называется дополнением графа G; принято обозначать его через . Взяв дополнение графа , мы снова получим граф G. Ребра обоих графов G и вместе составляют полный граф с теми же вершинами.
Date: 2016-02-19; view: 665; Нарушение авторских прав