Оцените презентацию от 1 до 5 баллов!
Тип файла:
ppt / pptx (powerpoint)
Всего слайдов:
15 слайдов
Для класса:
1,2,3,4,5,6,7,8,9,10,11
Размер файла:
1.98 MB
Просмотров:
104
Скачиваний:
1
Автор:
неизвестен
Слайды и текст к этой презентации:
№1 слайд![](/documents_6/c2528e18079d5f3e87d8b8dfc701ac95/img0.jpg)
№2 слайд![Базовые понятия Базовые](/documents_6/c2528e18079d5f3e87d8b8dfc701ac95/img1.jpg)
Содержание слайда: Базовые понятия:
Базовые понятия:
множество
граф
бинарное отношение
смежность
инцидентность
цикл
матрица
№3 слайд![Кристофидес Н. Теория графов.](/documents_6/c2528e18079d5f3e87d8b8dfc701ac95/img2.jpg)
Содержание слайда: Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. С. 25-27.
Харари Ф. Теория графов: Пер. с англ. / под ред. Гаврилова. М.: Мир, 1973. С. 54-57, 178-184.
Новиков Ф.А. Дискретная математика для программистов. С.-П., 2001. С. 201-205.
Хаханов В.І., Хаханова І.В., Кулак Е.М., Чумаченко С.В. Методичні вказівки до практичних занять з курсу “Дискретна математика”. Харків, ХНУРЕ. 2001. 87с.
Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984. С. 64-77, 100-102.
№4 слайд![Основные принципы теории](/documents_6/c2528e18079d5f3e87d8b8dfc701ac95/img3.jpg)
Содержание слайда: Основные принципы теории графов используются при построении математической модели для проектирования и анализа сетей ЭВМ
Основные принципы теории графов используются при построении математической модели для проектирования и анализа сетей ЭВМ
Наиболее удобной моделью сети является графовая структура
Описание графовой структуры должно быть технологичным для машины
Матричная форма является удобной для представления графов
Матрицы позволяют раскрыть структуру графа
Матрицы инциденций и циклов используются при исследовании электрических цепей, входят в качестве коэффициентов в уравнение Кирхгофа, описывающее цепь
Матрицы смежностей служат основой подхода к описанию и анализу модели компьютерной сети
№5 слайд![Базовые сетевые топологии](/documents_6/c2528e18079d5f3e87d8b8dfc701ac95/img4.jpg)
Содержание слайда: Базовые сетевые топологии типа «кольцо», «звезда», «шина» и соответствующие им графы
Базовые сетевые топологии типа «кольцо», «звезда», «шина» и соответствующие им графы
№6 слайд![Матрица смежностей двумерная](/documents_6/c2528e18079d5f3e87d8b8dfc701ac95/img5.jpg)
Содержание слайда: Матрица смежностей − двумерная таблица C=||cij|| размера nn, где n − число вершин, элемент которой определяется как
Матрица смежностей − двумерная таблица C=||cij|| размера nn, где n − число вершин, элемент которой определяется как
Пример
№7 слайд![Для неориентированного графа](/documents_6/c2528e18079d5f3e87d8b8dfc701ac95/img6.jpg)
Содержание слайда: Для неориентированного графа матрица смежностей является симметричной
Для неориентированного графа матрица смежностей является симметричной
Для ориентированного свойство симметрии не обязательно. Элемент матрицы определяется как
Суммы элементов матрицы смежностей по строкам равны степеням соответствующих вершин графа
№8 слайд![Матрица инциденций B bij](/documents_6/c2528e18079d5f3e87d8b8dfc701ac95/img7.jpg)
Содержание слайда: Матрица инциденций B=||bij|| ориентированного графа G=<V,U> без петель, где |V|=p, |U|=q, есть матрица размера pq, элемент которой определяется следующим образом:
Матрица инциденций B=||bij|| ориентированного графа G=<V,U> без петель, где |V|=p, |U|=q, есть матрица размера pq, элемент которой определяется следующим образом:
Пример
№9 слайд![Матрица циклов Z zij графа](/documents_6/c2528e18079d5f3e87d8b8dfc701ac95/img8.jpg)
Содержание слайда: Матрица циклов Z=||zij|| графа − матрица размерности mn, m − количество циклов, n − число ребер, элемент zij которой определяется так
Матрица циклов Z=||zij|| графа − матрица размерности mn, m − количество циклов, n − число ребер, элемент zij которой определяется так
Пример
№10 слайд![Пример Пример](/documents_6/c2528e18079d5f3e87d8b8dfc701ac95/img9.jpg)
Содержание слайда: Пример
Пример
№11 слайд![По матрице смежностей можно](/documents_6/c2528e18079d5f3e87d8b8dfc701ac95/img10.jpg)
Содержание слайда: По матрице смежностей можно однозначно восстановить граф:
По матрице смежностей можно однозначно восстановить граф:
Матрица инциденций однозначно представляет граф:
По матрице циклов нельзя однозначно восстановить граф: если ребро не принадлежит ни одному циклу, то по матрице циклов нельзя сказать, принадлежит ли оно графу
№12 слайд![Выбор наилучшего](/documents_6/c2528e18079d5f3e87d8b8dfc701ac95/img11.jpg)
Содержание слайда: Выбор наилучшего представления определяется требованиями конкретной задачи
Выбор наилучшего представления определяется требованиями конкретной задачи
Используются комбинации или модификации известных представлений
Способы представления графов в памяти компьютера различаются объемом занимаемой памяти и скоростью выполнения операций
Для матрицы смежностей сложность представления определяется как О(n2), где n − количество вершин в графе
Для матрицы инциденций сложность определяется как O(nm), где n,m − число вершин и ребер соответственно
№13 слайд![](/documents_6/c2528e18079d5f3e87d8b8dfc701ac95/img12.jpg)
№14 слайд![Свойства модели Свойства](/documents_6/c2528e18079d5f3e87d8b8dfc701ac95/img13.jpg)
Содержание слайда: Свойства модели:
Свойства модели:
компактность представления информации о графе;
привязка к распространенному математическому
аппарату;
наличие эффективных методов анализа графовых
отношений;
возможность аналитического описания функций и
структур.
Вершины графа и переменные в булевой алгебре связаны между собой системой отношений
Аппарат булевой алгебры может быть применен для описания графовых структур
№15 слайд![](/documents_6/c2528e18079d5f3e87d8b8dfc701ac95/img14.jpg)