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

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Планарные графы, слайд №1Планарные графы, слайд №2Планарные графы, слайд №3Планарные графы, слайд №4Планарные графы, слайд №5Планарные графы, слайд №6Планарные графы, слайд №7Планарные графы, слайд №8Планарные графы, слайд №9Планарные графы, слайд №10Планарные графы, слайд №11Планарные графы, слайд №12Планарные графы, слайд №13Планарные графы, слайд №14Планарные графы, слайд №15Планарные графы, слайд №16Планарные графы, слайд №17Планарные графы, слайд №18Планарные графы, слайд №19Планарные графы, слайд №20Планарные графы, слайд №21Планарные графы, слайд №22Планарные графы, слайд №23Планарные графы, слайд №24Планарные графы, слайд №25Планарные графы, слайд №26
Скачать

Содержание ▲

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

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

Слайд 1


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

Слайд 2


Географические карты Политическая Физическая карта карта
Описание слайда:
Географические карты Политическая Физическая карта карта

Слайд 3


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

Слайд 4


тор Теорема 2: Любую карту, нарисованную на торе, можно раскрасить пятью красками так, что любые две страны, имеющие общую границу, будут разного цвета.
Описание слайда:
тор Теорема 2: Любую карту, нарисованную на торе, можно раскрасить пятью красками так, что любые две страны, имеющие общую границу, будут разного цвета.

Слайд 5


крендель Теорема 3: Любую карту, нарисованную на поверхности кренделя, можно раскрасить шестью красками так, что любые две страны, имеющие общую границу, будут разного цвета.
Описание слайда:
крендель Теорема 3: Любую карту, нарисованную на поверхности кренделя, можно раскрасить шестью красками так, что любые две страны, имеющие общую границу, будут разного цвета.

Слайд 6


топология В топологии считается, что все тела сделаны из эластичного материала, и потому их можно сжимать и растягивать и они не порвутся. Такие деформации зовутся гомеоморфизмом. Т.о. топология изучает свойства гомеоморфных тел.
Описание слайда:
топология В топологии считается, что все тела сделаны из эластичного материала, и потому их можно сжимать и растягивать и они не порвутся. Такие деформации зовутся гомеоморфизмом. Т.о. топология изучает свойства гомеоморфных тел.

Слайд 7


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

Слайд 8


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

Слайд 9


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

Слайд 10


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

Слайд 11


самостоятельно Определить (занумеровать) все грани на планарном графе G(X,U):
Описание слайда:
самостоятельно Определить (занумеровать) все грани на планарном графе G(X,U):

Слайд 12


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

Слайд 13


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

Слайд 14


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

Слайд 15


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

Слайд 16


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

Слайд 17


самостоятельно Проверить планарность графа G(X,U), изображенного ниже.
Описание слайда:
самостоятельно Проверить планарность графа G(X,U), изображенного ниже.

Слайд 18


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

Слайд 19


Правило правой руки Построение двойственной дуги: 4 пальца указывают направление дуги исходного графа, а большой палец – двойственного.
Описание слайда:
Правило правой руки Построение двойственной дуги: 4 пальца указывают направление дуги исходного графа, а большой палец – двойственного.

Слайд 20


пример Исходный орграф Двойственный орграф
Описание слайда:
пример Исходный орграф Двойственный орграф

Слайд 21


Свойства двойственных графов Простому контуру исходного графа, «закрученному» по часовой стрелке, соответствует вершина-источник двойственного графа. Простому контуру исходного графа, «закрученному» против часовой стрелки, соответствует вершина-сток двойственного графа. Грани исходного графа, образованной встречно ориентированными дугами, соответствует вершина двойственного графа, которой инцидентны, как заходящие, так и исходящие дуги.
Описание слайда:
Свойства двойственных графов Простому контуру исходного графа, «закрученному» по часовой стрелке, соответствует вершина-источник двойственного графа. Простому контуру исходного графа, «закрученному» против часовой стрелки, соответствует вершина-сток двойственного графа. Грани исходного графа, образованной встречно ориентированными дугами, соответствует вершина двойственного графа, которой инцидентны, как заходящие, так и исходящие дуги.

Слайд 22


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

Слайд 23


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

Слайд 24


самостоятельно Построить граф, двойственный заданному ниже смешанному графу G(X,U):
Описание слайда:
самостоятельно Построить граф, двойственный заданному ниже смешанному графу G(X,U):

Слайд 25


самостоятельно Определить вес дуг и ребер графа, двойственного заданному ниже взвешенному смешанному графу G(X,U):
Описание слайда:
самостоятельно Определить вес дуг и ребер графа, двойственного заданному ниже взвешенному смешанному графу G(X,U):

Слайд 26


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

Скачать

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