Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Топ:
Марксистская теория происхождения государства: По мнению Маркса и Энгельса, в основе развития общества, происходящих в нем изменений лежит...
Комплексной системы оценки состояния охраны труда на производственном объекте (КСОТ-П): Цели и задачи Комплексной системы оценки состояния охраны труда и определению факторов рисков по охране труда...
Основы обеспечения единства измерений: Обеспечение единства измерений - деятельность метрологических служб, направленная на достижение...
Интересное:
Распространение рака на другие отдаленные от желудка органы: Характерных симптомов рака желудка не существует. Выраженные симптомы появляются, когда опухоль...
Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Дисциплины:
2017-12-12 | 504 |
5.00
из
|
Заказать работу |
|
|
Подмножества x(in) множества х вершин, графа G(X) называется внутренне устойчивым, если вершины множества x(in) не соединены ребрами. В противном случае неуст. Множество называется максимальным внутренне устойчивым, если оно становится внутренне неустойчивым при добавлении любой вершины.
Пример {x1,x3,x5},{x2.x5}- внутр. уст.
{x1,x3,x5}- максимальное внутрен.уст
{x1,x3}- просто внутр. Устр
Любое внутреннее устойчивое множество вершин графа содержится в некотором максимальном внутр. устр. Максимальных несколько.
Не особо важное определение, но можно написать:
Числом внутренней устойчивостиa (G) графа G(X) называется максимально число из чисел |x(in)|, x(in) –внутр.устр.множества, |x(in)| - число элементов множества x(in), те a(G)=max|x(in)|,1£a(G)£n
Хроматическое число и число внутр. устойчивости, графа G(X)связаны следующим неравенством:
a (G) ×n (G) ³ n = | x|
Доказательство. Пусть n (G) - хроматическое число графа G(X). Тогда множества вершин можно разбить на g (G) внутренне устойчивых множеств.
Образованных вершинами одинакового цвета. Если mi - число элементов
таких множеств, то mi =a (G). Откуда = åmi£n(G)×a(G)
Задача о четырех красках.
Подмножества множества х вершин, графа G(X) называется внутренне устойчивым, если вершины множества не соединены ребрами. В противном случае неуст. Множество называется максимальным внутренне устойчивым, если оно становится внутренне неустойчивым при добавлении любой вершины.
Пример (x1,x3,x5), (x2,x5) - внутр. уст.
(x1,x3,x5) - максимальное внутрен.
уст. (x1,x3) - просто внутр. устр.
Любое внутреннее устойчивое множество вершин графа содержится в некотором максимальном внутр. устр. Максимальных несколько.
Числом внутренней устойчивости (G) графа G(X) называется
|
максимально число из чисел | |, - внутр. устро. множества, | | - число элементов множества , т.е. (G) = max | |, 1≤ ≤n
Гипотеза четырех красок.
Достаточно ли четырех цветов для раскраски любой карты?
В 1890 году Хейвуд доказал, что достаточно пяти цветов.
Недавно американские математики Аппель и Хакон доказали гипотезу о четырех красках, существенно использовав ЭВМ. Таким образом для раскраски карты достаточно четырех красок. Для этого необходимо правильно подобрать внутренне устойчивые множества Вершин графа.
17. Задача Рамсея.
Доказать, что среди любых шести человек найдутся либо трое попарно незнакомых, либо трое попарно знакомых.
Отношение «быть знакомым» изобразим связывая вершин ребрам. Тогда три попарно знакомых образуют треугольник. В G – нет, Δ- ков, - есть.
Доказательство. Пусть - произвольная вершина графа шестью вершинами.
Подберем три другие вершины графа G с которыми связан с ребром. Если нет таких и каждая вершина соединена только двумя другими вершинами, то такие вершины найдутся в и рассмотрим дополнение. Если при этом u 1, u 2, u 3 не соед. ребром то они незнакомы, если есть хотя бы одно ребро то найдутся три знакомых. Теория доказана.
|
|
Адаптации растений и животных к жизни в горах: Большое значение для жизни организмов в горах имеют степень расчленения, крутизна и экспозиционные различия склонов...
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!