Планарные графы - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Планарные графы. Доклад-сообщение содержит 20 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Планарные графы Лекция 6

Слайд 2

Описание слайда:

Определение планарного графа Граф, изображенный на плоскости или на шаре, называется плоским или планарным графом, если его ребра (дуги) не пересекаются в точках, отличных от вершин графа.

Слайд 3

Описание слайда:

ПРИМЕРЫ

Слайд 4

Описание слайда:

Что такое «грань» Гранью (страной) в плоском представлении графа называется часть плоскости, ограниченная простым циклом и не содержащая внутри других циклов.

Слайд 5

Описание слайда:

пример

Слайд 6

Описание слайда:

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

Слайд 7

Описание слайда:

ТЕОРЕМА О 4-Х КРАСКАХ Любую плоскую карту или карту на сфере можно раскрасить 4-я красками так, что страны, имеющие общую границу, будут разного цвета. Раскрасить минимальным числом красок

Слайд 8

Описание слайда:

САМОСТОЯТЕЛЬНО РАСКРАСИТЬ МИНИМАЛЬНЫМ ЧИСЛОМ КРАСОК

Слайд 9

Описание слайда:

САМОСТОЯТЕЛЬНО Для каких из этих тел справедлива теорема о четырех красках?

Слайд 10

Описание слайда:

Теорема эйлера Пусть В - количество вершин в графе, Г - количество граней в плоском представлении графа, Р - количество рёбер в графе. Тогда получаем формулу Эйлера для связного планарного графа: В + Г - Р = 2