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

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

Содержание ▲

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

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

Слайд 1

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

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

Слайд 2

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

Географические карты Политическая Физическая карта карта

Слайд 3

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

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

Слайд 4

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

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

Слайд 5

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

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

Слайд 6

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

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

Слайд 7

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

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

Слайд 8

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

ПРИМЕРЫ

Слайд 9

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

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

Слайд 10

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

пример

Слайд 11

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

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

Слайд 12

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

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

Слайд 13

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

Примеры G1(X,U) G2(X,U)

Слайд 14

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

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

Слайд 15

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

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

Слайд 16

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

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

Слайд 17

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

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

Слайд 18

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

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

Слайд 19

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

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

Слайд 20

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

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

Слайд 21

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

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

Слайд 22

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

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