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

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

Презентацию Моделирование систем и процессов. Теория графов. (Лекция 2), из раздела: Математика,  в формате PowerPoint (pptx) можно скачать внизу страницы, поделившись ссылкой в социальных сетях! Презентации взяты из открытого доступа или загружены их авторами, администрация сайта не отвечает за достоверность информации в них. Все права принадлежат авторам материалов: Политика защиты авторских прав

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

Слайд 1

Моделирование систем и процессов

Лекция 2.
Понятия теории графов



Слайд 2

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

Понятия теории графов

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


Слайд 3

(BD)и(CD).Смежные вершины: A и В; А и С; С и В; C и D; В

Понятия теории графов





Омск

Новосибирск

Павлодар

Красноярск

650

420

590

800

А

В

С

D

1500

Число вершин: V={A,B,C,D}
Число ребер: X={(AB),(BC),(AC),(CD)}
Смежные ребра: (АС)и(АВ); (AC),(BC)и(DC); (AB),(BC)и(BD); (BD)и(CD).
Смежные вершины: A и В; А и С; С и В; C и D; В и D.
Инцидентны: вершина А и ребра (АВ) и (АС); вершина В и ребра (АВ), (ВС), (ВD); вершина С и ребра (АС), (ВС), (С D); вершина D и ребра (ВD), (СD).


Слайд 4

deg V=0, концевая deg V=1.Порядок графа: число вершин n=4, число ребер m=5.Граф (n,m) с n

Понятия теории графов


Степень вершин: deg A=deg D=2, deg C=deg B=3.
Изолированная вершина deg V=0, концевая deg V=1.
Порядок графа: число вершин n=4, число ребер m=5.
Граф (n,m) с n вершинами и m ребрами

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

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


Слайд 5

Понятия теории графов

Мультиграф

Псевдограф

Неориентиро-
ванный граф

Ориентиро-
ванный граф


Слайд 6

матрицу смежности, матрицу инцидентности

Пример графа

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


Слайд 7

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

Характерные свойства графов

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



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


Слайд 8

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

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


Слайд 9

проводятся линии, соединяющие вершины.Матричный. С помощью матрицы смежности и матрицы инцидентности.Аналитический. Задается список ребер и

Способы задания графов:

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

Матричный. С помощью матрицы смежности и матрицы инцидентности.

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


Слайд 10

граф, пустой графМультиграф, псевдографРебро, дуга, петляПутьКонтурМаршрут

Понятия теории графов

Ориентированный, неориентированный граф
Пустой граф
Связанный, несвязанный граф
Степень графа, порядок вершины
Полный граф, пустой граф
Мультиграф, псевдограф
Ребро, дуга, петля
Путь
Контур
Маршрут


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