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

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


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

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

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

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

Презентация на тему Моделирование систем и процессов. Теория графов. (Лекция 2)

Понятия теории графовГраф - некоторое конечное множество V точек на плоскости и конечный набор линий X, соединяющих некоторые пары точек из V.Граф состояний - наглядная геометрическая схема, изображающая возможные состояния системы с указанием (в виде стрелок)
Моделирование систем и процессовЛекция 2. Понятия теории графов Понятия теории графовГраф - некоторое конечное множество V точек на плоскости и Понятия теории графовОмскНовосибирскПавлодарКрасноярск650420590800АВСD1500Число вершин: V={A,B,C,D}Число ребер: X={(AB),(BC),(AC),(CD)}Смежные ребра: (АС)и(АВ); (AC),(BC)и(DC); (AB),(BC)и(BD); (BD)и(CD).Смежные Понятия теории графовСтепень вершин: deg A=deg D=2, deg C=deg B=3.Изолированная вершина deg Понятия теории графовМультиграфПсевдографНеориентиро-ванный графОриентиро-ванный граф Пример графаОхарактеризовать граф,Перечислить вершины, смежные вершины, изолированные вершины,Назвать ребра, петли, дугиСоставить матрицу смежности, матрицу инцидентности Характерные свойства графов1. Сумма степеней вершин графа равна удвоенному числу его ребер2. Изоморфизм графов4 графа одного порядка, с одинаковым числом ребер,Сравнить смежные вершины Способы задания графов:Графический. Все элементы множества V обозначаются точками на плоскости, проводятся Понятия теории графовОриентированный, неориентированный графПустой графСвязанный, несвязанный графСтепень графа, порядок вершиныПолный граф,
Слайды презентации

Слайд 2 Понятия теории графов
Граф - некоторое конечное множество V

Понятия теории графовГраф - некоторое конечное множество V точек на плоскости

точек на плоскости и конечный набор линий X, соединяющих

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


Слайд 3 Понятия теории графов




Омск
Новосибирск
Павлодар
Красноярск
650
420
590
800
А
В
С
D
1500
Число вершин: V={A,B,C,D}
Число ребер: X={(AB),(BC),(AC),(CD)}
Смежные ребра:

Понятия теории графовОмскНовосибирскПавлодарКрасноярск650420590800АВСD1500Число вершин: V={A,B,C,D}Число ребер: X={(AB),(BC),(AC),(CD)}Смежные ребра: (АС)и(АВ); (AC),(BC)и(DC); (AB),(BC)и(BD);

(АС)и(АВ); (AC),(BC)и(DC); (AB),(BC)и(BD); (BD)и(CD).
Смежные вершины: A и В; А

и С; С и В; C и D; В и D.
Инцидентны: вершина А и ребра (АВ) и (АС); вершина В и ребра (АВ), (ВС), (ВD); вершина С и ребра (АС), (ВС), (С D); вершина D и ребра (ВD), (СD).

Слайд 4 Понятия теории графов

Степень вершин: deg A=deg D=2, deg

Понятия теории графовСтепень вершин: deg A=deg D=2, deg C=deg B=3.Изолированная вершина

C=deg B=3.
Изолированная вершина deg V=0, концевая deg V=1.
Порядок графа:

число вершин n=4, число ребер m=5.
Граф (n,m) с n вершинами и m ребрами

Матрица инцидентности
(для неориентированного графа)

Матрица
смежности


Слайд 5 Понятия теории графов
Мультиграф
Псевдограф
Неориентиро-
ванный граф
Ориентиро-
ванный граф

Понятия теории графовМультиграфПсевдографНеориентиро-ванный графОриентиро-ванный граф

Слайд 6 Пример графа
Охарактеризовать граф,
Перечислить вершины, смежные вершины, изолированные вершины,
Назвать

Пример графаОхарактеризовать граф,Перечислить вершины, смежные вершины, изолированные вершины,Назвать ребра, петли, дугиСоставить матрицу смежности, матрицу инцидентности

ребра, петли, дуги
Составить матрицу смежности, матрицу инцидентности


Слайд 7 Характерные свойства графов
1. Сумма степеней вершин графа равна

Характерные свойства графов1. Сумма степеней вершин графа равна удвоенному числу его

удвоенному числу его ребер



2. В любом графе число вершин

нечетной степени четно

Слайд 8 Изоморфизм графов
4 графа одного порядка, с одинаковым числом

Изоморфизм графов4 графа одного порядка, с одинаковым числом ребер,Сравнить смежные вершины

ребер,
Сравнить смежные вершины


Слайд 9 Способы задания графов:
Графический. Все элементы множества V обозначаются

Способы задания графов:Графический. Все элементы множества V обозначаются точками на плоскости,

точками на плоскости, проводятся линии, соединяющие вершины.

Матричный. С помощью

матрицы смежности и матрицы инцидентности.

Аналитический. Задается список ребер и список вершин.

  • Имя файла: modelirovanie-sistem-i-protsessov-teoriya-grafov-lektsiya-2.pptx
  • Количество просмотров: 101
  • Количество скачиваний: 0