Лекция №5 Раскраска графа. Теорема о пяти красках

Исследование темперамента в России

Основоположниками этого направления являются Б.М.Теплов и В.Д.Небылицын.

Темперамент рассматривается В.Д.Небылицыным как «характеристика индивида со стороны динамических особенностей его психической деятельности, то есть темпа, быстроты, ритма, интенсивности составляющих эту деятельность психических процессов и состояний». В структуре темперамента было выделено два основных компонента- активность и эмоциональность.

Активность связана с энергетическими потенциалами человека, позволяющими ему с большей или меньшей эффективностью осваивать и преобразовывать окружающий мир. Динамические характеристики активности могут проявляться и в общении, и в познавательной деятельности.

Об активности можно судить по трем ее проявлениям - по индивидуальному темпу деятельности (по скорости двигательной реакции, которая свойственна испытуемому и которую он склонен сам выбирать), по склонности к разнообразию реакций и по склонности к действиям в ситуации, когда, по условиям эксперимента, действие не является обязательным (одни люди склонны, а другие не склонны к проявлениям сверхнормативной активности).

Эмоциональность рассматривается как «особенности возникновения, протекания и прекращения разнообразных чувств, аффектов и настроений», то есть/иначе говоря, эмоциональность связана с динамикой эмоциональной жизни человека.

Было предположено, что наиболее важными видами эмоций являются три из них - удовольствие (радость), гнев и страх.

Генетические исследования темперамента начались с середины 70-х гг.

При анализе изменений в свойствах темперамента у детей при переходе от дошкольного к школьному возрасту (от 6 к 7 годам) были получены данные, свидетельствующие о влиянии генотипа на индивидуальные различия в свойствах темперамента.

Коэффициент наследуемости темперамента – 90%.

В 1878 г. английский математик Кэли на заседании английского королевского научного общества предложил задачу, добавив, что размышлял над ней длительное время и не смог её решить. Суть задачи: можно ли на любой политико-административной карте раскрасить страны так, чтобы никакие две страны, имеющие общую границу, не были раскрашены одинаковой краской, и чтобы были использованы всего четыре краски? В терминах графов эта задача ставится следующим образом: можно ли каждую вершину неориентированного графа раскрасить с помощью одной из четырёх красок так, чтобы никакие две смежные вершины не были закрашены одним цветом. Эту задачу, известную как задача о четырёх красках, удалось решить только с помощью компьютера, после длительной проверки огромного числа случаев, которые иначе проанализировать не удавалось.

Ещё до решения проблемы четырёх красок было доказано, что для раскраски любого плоского графа достаточно пяти красок.

Определение. Граф G = (Х, Г) называется правильно раскрашенным l красками, если каждая его вершина раскрашена одной из l красок и если из (x_i, x_j) Î Г следует, что x_i и x_j раскрашены разными красками. Если выполнены все условия определения, то говорят, что задана правильная раскраска графа G l красками.

Определение. Граф называется р -хроматическим, если существует правильная раскраска этого графа р красками. Минимальное из таких чисел р называется хроматическим числом данного графа.

Доказательство основной теоремы опирается на следующую лемму.

Лемма. В любом связном плоском графе без кратных рёбер, без тупиков и мостов существует вершина, степень которой не превосходит 5.

Теорема. Любой плоский граф 5-хроматичен.

Рассмотрим пример графа, для правильной раскраски которого недостаточно 3 цветов.

·

·

· ·

Рис. 18.

Кроме раскраски вершин графа можно рассматривать раскраску его рёбер, которая будет соответствовать одному из бинарных отношений, заданных на множестве вершин графа.

Дата добавления: 2014-01-20