Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.


Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

Презентация на тему Изоморфное вложение графов

Подграфы
Изоморфное вложение графов Подграфы Изоморфизм графов Изоморфизм графов Инварианты графов Локальные инварианты Локальные инварианты Локальные инвариантыПримеры инвариантов вершин:Степень вершиныКоличество путей заданной длины, проходящих через вершинуКоличество циклов, Алгоритм распознавания изоморфизма графовОсновная процедура – генерация перестановок, осуществляющих изоморфизмДо запуска этой Проверка локальных инвариантов Проверка локальных инвариантов Порождение перестановок
Слайды презентации

Слайд 2 Подграфы

Подграфы

Слайд 3 Изоморфизм графов

Изоморфизм графов

Слайд 4 Изоморфизм графов

Изоморфизм графов

Слайд 5 Инварианты графов

Инварианты графов

Слайд 6 Локальные инварианты

Локальные инварианты

Слайд 7 Локальные инварианты

Локальные инварианты

Слайд 8 Локальные инварианты
Примеры инвариантов вершин:
Степень вершины
Количество путей заданной длины,

Локальные инвариантыПримеры инвариантов вершин:Степень вершиныКоличество путей заданной длины, проходящих через вершинуКоличество

проходящих через вершину
Количество циклов, проходящих через вершину

Примеры локальных инвариантов:
Количество

путей заданной длины, принадлежащих фрагменту
Цикломатическое число фрагмента
Хроматическое число фрагмента



Слайд 9 Алгоритм распознавания изоморфизма графов
Основная процедура – генерация перестановок,

Алгоритм распознавания изоморфизма графовОсновная процедура – генерация перестановок, осуществляющих изоморфизмДо запуска

осуществляющих изоморфизм
До запуска этой процедуры производится проверка равенства инвариантов

рассматриваемых графов; если обнаружено неравенство, графы не изоморфны
Каждая перестановка-кандидат проверяется на сохранение локальных инвариантов
Для простоты будем рассматривать только инварианты вершин

Слайд 10 Проверка локальных инвариантов

Проверка локальных инвариантов

Слайд 11 Проверка локальных инвариантов

Проверка локальных инвариантов

  • Имя файла: izomorfnoe-vlozhenie-grafov.pptx
  • Количество просмотров: 99
  • Количество скачиваний: 0