- Хроматическое число

Презентация "Хроматическое число" по математике – проект, доклад

Слайд 1
Слайд 2
Слайд 3
Слайд 4
Слайд 5
Слайд 6
Слайд 7
Слайд 8
Слайд 9
Слайд 10
Слайд 11
Слайд 12
Слайд 13
Слайд 14

Презентацию на тему "Хроматическое число" можно скачать абсолютно бесплатно на нашем сайте. Предмет проекта: Математика. Красочные слайды и иллюстрации помогут вам заинтересовать своих одноклассников или аудиторию. Для просмотра содержимого воспользуйтесь плеером, или если вы хотите скачать доклад - нажмите на соответствующий текст под плеером. Презентация содержит 14 слайд(ов).

Слайды презентации

Хроматическое число
Слайд 1

Хроматическое число

Определение. Пусть G=(V,E) – обыкновенный граф и k – натуральное число. Функция f: V → {1,…,k} называется раскраской графа. Раскраска называется правильной, если для любых смежных вершин x,y ϵ V справедливо неравенство f(x) ≠ f(y). Число k – число красок раскраски f.
Слайд 2

Определение. Пусть G=(V,E) – обыкновенный граф и k – натуральное число. Функция f: V → {1,…,k} называется раскраской графа. Раскраска называется правильной, если для любых смежных вершин x,y ϵ V справедливо неравенство f(x) ≠ f(y). Число k – число красок раскраски f.

Наименьшее число красок, необходимое для правильной раскраски графа G называется хроматическим числом графа G. Правильную раскраску таким числом красок будем называть оптимальной. Хроматическое число обозначается через χ(G).
Слайд 3

Наименьшее число красок, необходимое для правильной раскраски графа G называется хроматическим числом графа G. Правильную раскраску таким числом красок будем называть оптимальной. Хроматическое число обозначается через χ(G).

Оба графа содержат трехэлементный полный подграф К3, поэтому для правильной раскраски необходимо, по крайней мере, три краски. Для графа G1 этого достаточно .Граф G2 имеет цикл длины 5. Нетрудно понять, что для правильной раскраски вершин цикла необходимо три краски. Но центральная вершина графа G2
Слайд 4

Оба графа содержат трехэлементный полный подграф К3, поэтому для правильной раскраски необходимо, по крайней мере, три краски. Для графа G1 этого достаточно .Граф G2 имеет цикл длины 5. Нетрудно понять, что для правильной раскраски вершин цикла необходимо три краски. Но центральная вершина графа G2 смежна со всеми вершинами цикла, поэтому для правильной раскраски графа понадобится четвертая краска. Итак, χ(G1)=3 и χ(G2)=4.

Рассмотрим примеры графов, изображенных на рисунке

Очевидно, что если компоненты связности графа G правильно раскрасить k красками, то и сам граф окажется правильно раскрашенным этими красками. Отсюда следует, что если G1,G2,…,Gc – (все) компоненты связности графа G, то. χ(G)=max{χ(G1), χ(G2),…, χ(Gc)}. Аналогичное утверждение справедливо и для комп
Слайд 5

Очевидно, что если компоненты связности графа G правильно раскрасить k красками, то и сам граф окажется правильно раскрашенным этими красками. Отсюда следует, что если G1,G2,…,Gc – (все) компоненты связности графа G, то

χ(G)=max{χ(G1), χ(G2),…, χ(Gc)}.

Аналогичное утверждение справедливо и для компонент двусвязности.

Теорема Пусть любой блок графа G можно правильно раскрасить k расками. Тогда и сам граф G можно правильно раскрасить k красками. Доказательство проведем индукцией по числу блоков. Можно считать, что G – связный граф. Если граф содержит один блок, то утверждение теоремы, очевидно, справедливо. Предпо
Слайд 6

Теорема Пусть любой блок графа G можно правильно раскрасить k расками. Тогда и сам граф G можно правильно раскрасить k красками.

Доказательство проведем индукцией по числу блоков. Можно считать, что G – связный граф. Если граф содержит один блок, то утверждение теоремы, очевидно, справедливо. Предположим, что теорема справедлива для любых графов, имеющих не более k блоков. Пусть граф G имеет k+1 блок. Зафиксируем один из концевых блоков графа G. Этот блок обозначим через В, а объединение остальных блоков – через В' . Графы В и В’ имеют точно одну общую вершину а (которая является точкой сочленения графа G). По предположению индукции графы В и В’ можно правильно раскрасить k красками. Если вершина а в обоих графах В и В’ окрашена одинаково, то в результате получаем правильную раскраску графа G. Если вершина а в графах В и В’ окрашена по-разному, то очевидным образом перекрашиваем граф В так, чтобы новая краска вершины а совпадала с краской этой вершины в графе В’.

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

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

Задача составления расписаний. Предположим, что в учебном центре надо провести несколько занятий за кратчайшее время. Длительность всех занятий одинакова, скажем, один час. Некоторые занятия не могут проводиться одновременно, например, это занятия в одной и той же учебной группе (по разным предметам
Слайд 8

Задача составления расписаний. Предположим, что в учебном центре надо провести несколько занятий за кратчайшее время. Длительность всех занятий одинакова, скажем, один час. Некоторые занятия не могут проводиться одновременно, например, это занятия в одной и той же учебной группе (по разным предметам), или занятия проводит один и тот же преподаватель. Для решения задачи построим граф G, вершинам которого биективно соответствуют занятия. Две вершины соединены ребром, если соответствующие занятия нельзя проводить одновременно. Ясно, что правильная раскраска графа G определяет расписание, удовлетворяющее требованиям несовместимости по времени: занятия, соответствующие вершинам, окрашенным одинаково, можно проводить одновременно. Справедливо и обратное, любое такое расписание определяет правильную раскраску графа G. Следовательно, кратчайшее время необходимое для проведения всех занятий равно χ(G), а из оптимальной раскраски графа G получается необходимое расписание.

Задача распределения ресурсов. Необходимо выполнить некоторое множество V={v1,v2,…,vn} работ. Имеется множество S={s1,s2,…,sr} ресурсов, необходимых для выполнения этих работ. Каждая работа использует часть указанных ресурсов, одновременно могут выполняться работы, использующие разные ресурсы. Все р
Слайд 9

Задача распределения ресурсов. Необходимо выполнить некоторое множество V={v1,v2,…,vn} работ. Имеется множество S={s1,s2,…,sr} ресурсов, необходимых для выполнения этих работ. Каждая работа использует часть указанных ресурсов, одновременно могут выполняться работы, использующие разные ресурсы. Все работы выполняются за одно и то же время t. Необходимо распределить ресурсы так, чтобы общее время выполнения всех работ было минимальным.

Рассмотрим граф G с множеством вершин V. Две различные вершины v и v’ графа G смежны тогда и только тогда, когда для выполнения работ v и v’ требуется хотя бы один общий ресурс. Наименьшее время выполнения всех работ равно χ(G)·t. Оптимальная раскраска графа G определяет распределение ресурсов.

Задача экономии памяти. Предположим, что необходимо написать программу для вычисления функции φ(х1,x2,…,xn). Вычисление этой функции разбито на ряд блоков, у каждого из блоков имеются входные и выходные переменные Так, например, у блока 2 входные переменные a и b, выходная – с, у блока 3 входная пер
Слайд 10

Задача экономии памяти. Предположим, что необходимо написать программу для вычисления функции φ(х1,x2,…,xn). Вычисление этой функции разбито на ряд блоков, у каждого из блоков имеются входные и выходные переменные Так, например, у блока 2 входные переменные a и b, выходная – с, у блока 3 входная переменная a, выходная – d.

Верхнюю часть можно назвать блок–схемой по информации. Нижняя часть этого рисунка представляет собой «систему координат», где по вертикальной оси отложены введенные в блок–схеме переменные, а по вертикальной «время их жизни» при вычислении значения функции φ.
Слайд 12

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

Предположим, что значения переменной занимают одну ячейку памяти. Задача состоит в том, чтобы определить наименьшее число ячеек памяти, необходимое для хранения указанных в блок – схеме переменных. Решить эту задачу можно следующим образом. На множестве переменных V={a,b,…,g,h} введем структуру граф
Слайд 13

Предположим, что значения переменной занимают одну ячейку памяти. Задача состоит в том, чтобы определить наименьшее число ячеек памяти, необходимое для хранения указанных в блок – схеме переменных. Решить эту задачу можно следующим образом. На множестве переменных V={a,b,…,g,h} введем структуру графа: две переменных соединим ребром, если времена их жизни пересекаются. Полученный граф будем называть графом несовместимости переменных. Значения переменных не могут занимать одну ячейку памяти тогда и только тогда, когда переменные соединены ребром в графе несовместимости. Следовательно, задача экономии памяти сводится к нахождению оптимальной раскраски графа несовместимости. В нашем случае достаточно четырех ячеек памяти

Как мы видели выше, при решении ряда практических задач необходимо уметь вычислять хроматическое число графа. Естественно попытаться найти формулу, которая выражала бы хроматическое число через «привычные» величины: число вершин, ребер, компонент связности, степени вершин. Однако несложные примеры п
Слайд 14

Как мы видели выше, при решении ряда практических задач необходимо уметь вычислять хроматическое число графа. Естественно попытаться найти формулу, которая выражала бы хроматическое число через «привычные» величины: число вершин, ребер, компонент связности, степени вершин. Однако несложные примеры показывают, что такой формулы нет. Рассмотрим графы, изображенные на рис.

У этих графов одно и то же число вершин, ребер, компонент связности. Распределение степеней вершин тоже совпадает: четыре вершины имеют степень 4, остальные – степень 2. Однако хроматическое число первого графа равно четырем, а второго – двум.

Список похожих презентаций

Умножение суммы на число

Умножение суммы на число

Очень трудная наука Математика для вас. Но учиться в наше время Нужно каждому из нас! Устный счёт. Математический диктант. 1*6 3*9 9*4 7*6 6*6 8*9 ...
Умножение дроби на число

Умножение дроби на число

Цели:. научить давать определение произведения десятичной дроби на натуральное число, умножать десятичную дробь на натуральное число, в том числе ...
Умножение на однозначное число

Умножение на однозначное число

14 марта Классная работа . Математический диктант. УСТНЫЙ СЧЕТ. 6 умножить на 8. 7 увеличить в 4 раза. Первый множитель 9, второй 5. Найти произведение. ...
Умножение вектора на число

Умножение вектора на число

ЗАДАЧА№1 Найдите:. ЗАДАЧА№2 Докажите:. ЗАДАЧА№3. ABCD-прямоугольник AB=5; AD=12. Докажите: Найдите:. Умножение вектора на число. . Произведение любого ...
Умножение десятичной дроби на натуральное число

Умножение десятичной дроби на натуральное число

Урок-путешествие. Слоны бывают африканские и азиатские. Самое крупное животное – африканский слон. Вычислите высоту, длину и массу взрослого африканского ...
Прибавить и вычесть число 2

Прибавить и вычесть число 2

Перед зайцем не дрожал, От медведя убежал, А лисице на зубок Все ж попался…. 10 4 О 6 9 Ы 5 Л 2 8 Ц Д. Физкультминутка. 2+2 4-1 3+2 5+2 7+2 9+1 10-2 ...
Сложение и вычитание десятичных дробей. Умножение десятичных дробей на натуральное число

Сложение и вычитание десятичных дробей. Умножение десятичных дробей на натуральное число

Цель: 1. Закрепить и систематизировать знания и умения в применении правил сложения, вычитания десятичных дробей, умножения десятичной дроби на натуральное ...
Деление на двузначное число

Деление на двузначное число

Вновь играя и шаля Перед носом корабля. Над водой мелькают спины, - Мчатся шустрые…. Деление на двузначное число. Чистописание. Прочитайте текст Выпишите ...
Деление на двузначное число

Деление на двузначное число

Математическая разминка. 32* 4. 720:6. 880:11. 560:14. . 810:27. Проверь 40 130 120 30. Определи, сколько цифр в частном. 2 123 856 : 36 45 846 : ...
Деление на двузначное число

Деление на двузначное число

1. 2014 Мобильная видео коммуникация. . Видео Емеил V-mail. 1. Конструктор видео сообщений и видео визиток 2. Функция записи видео сообщений 3. Автоматическая ...
Деление на двузначное число

Деление на двузначное число

4 6 3 0. Первому неполному делимому соответствует одна цифра частного, а всем остальным цифрам делимого – ещё по одной цифре частного. 1 5 2. 8. 7 ...
Деление десятичных дробей на натуральное число

Деление десятичных дробей на натуральное число

Отрабатывать умения и навыки выполнения деления десятичной дроби на натуральное число; Развивать самостоятельность в деятельности; Развивать интерес ...
Деление десятичной дроби на натуральное число

Деление десятичной дроби на натуральное число

Это растение бергамот. Это цитрусовое растение. Плоды его несъедобны, но масло, которое получают из кожуры этих плодов, листьев и цветов, имеет приятный ...
число 12

число 12

Математику, друзья, Не любить никак нельзя. Очень строгая наука, Очень точная наука, Интересная наука - МАТЕМАТИКА! 12 знаков зодиака. 12 месяцев ...
Деление на двузначное число

Деление на двузначное число

75:15 3 5. 45:15 4. 51:17 2. 70:35. 48:16 1. 60:15 6. 34: 17. 50:25. 64:16. 36:12. 52:13. 72:12 7. 84:14. 96:12 8. Здорово! http://dlm3.meta.ua/pic/0/51/193/P7K6KDqfij.jpg ...
Деление десятичной дроби на натуральное число

Деление десятичной дроби на натуральное число

Мы отправляемся в экспедицию! Работают три научно-исследовательские лаборатории . Чтобы узнать куда мы отправляемся, надо устно решить примеры. Вычислите ...
Деление на двузначное число

Деление на двузначное число

Математику, друзья, Не любить никак нельзя. Очень тонкая наука, Очень строгая наука, Интересная наука- это математика! 1. Организационный момент. ...
Примеры деления на однозначное число

Примеры деления на однозначное число

Тема: Деление многозначных чисел на однозначные. Цели: Делить многозначные числа «уголком» Решение задач Учиться оценивать себя. Листок путешествий. ...
Деление на однозначное число двузначного с помощью разложения на разрядные слагаемые

Деление на однозначное число двузначного с помощью разложения на разрядные слагаемые

. . . Дружба. . Тема: Деление на однозначное число двузначных чисел с помощью разложения на разрядные слагаемые. . . Физминутка. К морю быстро мы ...

Конспекты

Умножение нуля на число

Умножение нуля на число

Тема.  . «Умножение нуля на число». Цели:. Рассмотреть случай умножения нуля на число. . Создать условия для формирования навыка умножения ...
Умножение круглых чисел, сводящееся на умножение на двузначное число

Умножение круглых чисел, сводящееся на умножение на двузначное число

Муниципальное автономное общеобразовательное учреждение. . Видновская средняя общеобразовательная школа № 9. Урок математики. 3 класс. ...
Умножение на двузначное число

Умножение на двузначное число

Тип урока: Урок введения нового знания. Тема: Умножение на двузначное число. Цель: Научить выполнять умножение в столбик. Задачи: Вывести алгоритм ...
Умножение и деление двузначного числа на однозначное число без перехода через разряд

Умножение и деление двузначного числа на однозначное число без перехода через разряд

Казённое специальное (коррекционное) образовательное учреждение Ханты-Мансийского автономного округа –Югры для учащихся, воспитанников с ограниченными ...
Умножение и деление на однозначное число

Умножение и деление на однозначное число

Тип урока. : урок обобщение и систематизация знаний по данной теме. Цель урока. : закрепить полученные знания по теме «умножение и деление на ...
Больше на некоторое число

Больше на некоторое число

Тема:. Больше на некоторое число. Тип урока:. урок изучения нового материала и первичного закрепления. Цель:. познакомить учащихся с возможностью ...
Умножение десятичной дроби на целое число

Умножение десятичной дроби на целое число

Урок математики в 7 классе. Морозова Ольга Владимировна - учитель математики. ГБОУ школы-интерната №16 Пушкинского района СПб. Тема: «Умножение ...
Деление десятичной дроби на натуральное число

Деление десятичной дроби на натуральное число

Азарова Лидия Васильевна, учитель математики МБОУ Михейковская СОШ. Тема:. «Деление десятичной дроби на натуральное число». Класс:. 5. . Тип ...
Деление и умножение суммы на число

Деление и умножение суммы на число

Спресова Наталья Николаевна. Муниципальное общеобразовательное учреждение: средняя общеобразовательная школа, с.Нялинское Ханты-Мансийского района ...
Деление двузначного числа на однозначное и двузначное число, деление чисел с остатком, решение задач

Деление двузначного числа на однозначное и двузначное число, деление чисел с остатком, решение задач

. ТЕМА: «. Деление двузначного числа на однозначное и двузначное число, деление чисел с остатком, решение задач». . Сухова Т.А. . ...

Советы как сделать хороший доклад презентации или проекта

  1. Постарайтесь вовлечь аудиторию в рассказ, настройте взаимодействие с аудиторией с помощью наводящих вопросов, игровой части, не бойтесь пошутить и искренне улыбнуться (где это уместно).
  2. Старайтесь объяснять слайд своими словами, добавлять дополнительные интересные факты, не нужно просто читать информацию со слайдов, ее аудитория может прочитать и сама.
  3. Не нужно перегружать слайды Вашего проекта текстовыми блоками, больше иллюстраций и минимум текста позволят лучше донести информацию и привлечь внимание. На слайде должна быть только ключевая информация, остальное лучше рассказать слушателям устно.
  4. Текст должен быть хорошо читаемым, иначе аудитория не сможет увидеть подаваемую информацию, будет сильно отвлекаться от рассказа, пытаясь хоть что-то разобрать, или вовсе утратит весь интерес. Для этого нужно правильно подобрать шрифт, учитывая, где и как будет происходить трансляция презентации, а также правильно подобрать сочетание фона и текста.
  5. Важно провести репетицию Вашего доклада, продумать, как Вы поздороваетесь с аудиторией, что скажете первым, как закончите презентацию. Все приходит с опытом.
  6. Правильно подберите наряд, т.к. одежда докладчика также играет большую роль в восприятии его выступления.
  7. Старайтесь говорить уверенно, плавно и связно.
  8. Старайтесь получить удовольствие от выступления, тогда Вы сможете быть более непринужденным и будете меньше волноваться.

Информация о презентации

Ваша оценка: Оцените презентацию по шкале от 1 до 5 баллов
Дата добавления:15 мая 2019
Категория:Математика
Содержит:14 слайд(ов)
Поделись с друзьями:
Скачать презентацию
Смотреть советы по подготовке презентации