🗊Презентация Планарные графы

Категория: Математика
Нажмите для полного просмотра!
Планарные графы, слайд №1Планарные графы, слайд №2Планарные графы, слайд №3Планарные графы, слайд №4Планарные графы, слайд №5Планарные графы, слайд №6Планарные графы, слайд №7Планарные графы, слайд №8Планарные графы, слайд №9Планарные графы, слайд №10Планарные графы, слайд №11Планарные графы, слайд №12Планарные графы, слайд №13Планарные графы, слайд №14Планарные графы, слайд №15Планарные графы, слайд №16Планарные графы, слайд №17Планарные графы, слайд №18Планарные графы, слайд №19Планарные графы, слайд №20
Скачать
Вы можете ознакомиться и скачать презентацию на тему Планарные графы. Доклад-сообщение содержит 20 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1


Планарные графы Лекция 6
Описание слайда:
Планарные графы Лекция 6

Слайд 2


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

Слайд 3


ПРИМЕРЫ
Описание слайда:
ПРИМЕРЫ

Слайд 4


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

Слайд 5


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

Слайд 6


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

Слайд 7


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

Слайд 8


САМОСТОЯТЕЛЬНО РАСКРАСИТЬ МИНИМАЛЬНЫМ ЧИСЛОМ КРАСОК
Описание слайда:
САМОСТОЯТЕЛЬНО РАСКРАСИТЬ МИНИМАЛЬНЫМ ЧИСЛОМ КРАСОК

Слайд 9


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

Слайд 10


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

Слайд 11


Примеры G1(X,U) G2(X,U)
Описание слайда:
Примеры G1(X,U) G2(X,U)

Слайд 12


Формула эйлера для несвязного графа Для несвязного планарного графа с K компонентами связности формула Эйлера имеет вид: В + Г - Р = K + 1.
Описание слайда:
Формула эйлера для несвязного графа Для несвязного планарного графа с K компонентами связности формула Эйлера имеет вид: В + Г - Р = K + 1.

Слайд 13


пример Несвязный планарный граф с К = 3 компонентами:
Описание слайда:
пример Несвязный планарный граф с К = 3 компонентами:

Слайд 14


Теорема куратовского - понтрягина Граф планарен тогда и только тогда, когда он не содержит подграфов типов, приведённых ниже:
Описание слайда:
Теорема куратовского - понтрягина Граф планарен тогда и только тогда, когда он не содержит подграфов типов, приведённых ниже:

Слайд 15


Самостоятельно проверить планарность графа
Описание слайда:
Самостоятельно проверить планарность графа

Слайд 16


САМОСТОЯТЕЛЬНО Проверить планарность графов, приведенных ниже в персональных заданиях.
Описание слайда:
САМОСТОЯТЕЛЬНО Проверить планарность графов, приведенных ниже в персональных заданиях.

Слайд 17


Персональные задания 1- 6
Описание слайда:
Персональные задания 1- 6

Слайд 18


Персональные задания 7 - 12
Описание слайда:
Персональные задания 7 - 12

Слайд 19


Персональные задания 13 - 18
Описание слайда:
Персональные задания 13 - 18

Слайд 20


Персональные задания 19 - 24
Описание слайда:
Персональные задания 19 - 24

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию