Матрицей смежности - раздел Математика, Теория множеств Смежные Дуги – Это Дуги Инцидентные Одной Вершине.
...
Смежные дуги – это дуги инцидентные одной вершине.
Смежные вершины – вершины, инцидентные одной дуге.
Матрица смежности - это матрица смежных вершин.
Матрица смежности заполняется по следующему правилу:, если из i-той вершины исходит дуга в j – тую вершину; во всех остальных случаях (для удобства и наглядности на практике в матрице смежности нули не проставляются).
Для графа, представленного на рис. 3.2 матрица смежности имеет вид:
Полустепенью заходаi–той вершины называется число дуг, заходящих в данную вершину.
Полустепенью исходаi-той вершины называется число дуг, исходящих из данной вершины.
Степенью i-той вершины исходаназывается сумма полустепеней захода и исхода:
(3.2)
Свойства матрицы смежности:
1. Сумма единиц по строке определяет полустепень исхода;
2. Сумма единиц по столбцу определяет полустепень захода;
3. Сумма единиц по строкам и по столбцам определяет степень вершин.
Основное свойство графа:
В любых графах число вершин с нечетной степенью четно.
Путемв графе называется последовательность дуг такая, что каждая следующая дуга исходит из вершины, в которую заходит предыдущая дуга.
Длиной путиназывается количество пройденных дуг.
Простой путь – это такой путь, в котором дуга встречается не более одного раза.
Элементарный путь – это путь, в котором вершина встречается не более одного раза.
Контур – путь, начинающийся и заканчивающийся в одной точке.
Петля – контур длиной в одну единицу.
Графы бывают двух видов:
· ориентированный граф (орграф) - это граф, состоящий из вершин и дуг.
· неориентированный граф – это граф, состоящий из вершин и ребер. Ребро – это дуга, не имеющая направление.
Рис. 3.3. Неориентированный граф
В неориентированном графе путь называется цепью; контур – циклом.
Неориентированный граф также может быть задан с помощью матриц инцидентности и смежности.
Матрица инцидентности для неориентированного графа составляется по правилу:
· , если i-тая вершина инцидентна j-тому ребру;
· , если i-тая вершина не инцидента j-тому ребру;
· , если. в i-той вершине j-тое ребро образует петлю.
Для графа, представленного на рис. 3.3, матрица инцидентности имеет вид:
I
II
III
IV
V
VI
VII
Матрица смежности для неориентированного графа составляется по правилу: , если из i-тая и j – тая вершины смежные.
Для графа, представленного на рис. 3.3, матрица смежности имеет вид:
Матрица смежности для неориентированного графа симметрична относительно главной диагонали. Степень i- той вершины равна сумме элементов по строке или по столбцу матрицы смежности.
Если в графе присутствуют как ребра, так и дуги, то он называется смешанным.
Если между двумя вершинами существует более чем 1 дуга или ребро, то такой граф называется мультиграфом.
Рис. 3.4. Смешанный мультиграф.
Граф называется связным, если между любыми двумя вершинами которого существует путь (цепь).
Объединением множеств А и В называется множество состоящее из всех тех и только тех элементов которые принадлежат хотя бы одному из множеств А... Пересечениеммножеств А и В называется множество состоящее из тех и только тех элементов которые принадлежат...
Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ:
Матрицей смежности
Что будем делать с полученным материалом:
Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:
Теория множеств.
Множеством Sназывается объединение в одно целое объектов, хорошо различимых нашей мыслью или интуицией. Эти объекты называется элементами
Свойства подмножеств.
1. Рефлексивность. Множество А является подмножеством множества А:
Алгебра теории множеств.
Для любых множеств А, В и С выполнимы следующие тождества:
1. Коммутативный закон
Кортеж.
Кортеж -это упорядоченный набор элементов. Кортеж характеризуется элементами и их порядком расположения. Элементы кортежа называются компонентами.Компон
График и свойства графика
Графиком называется множество пар. Графики могут задаваться :
1. перечислением:
Соответствия.
Соответствием называется тройка вида . При этом
Отношения.
Отношением называется пара вида такая, что ФÍM
Транзитивность.
Отношение называется транзитивным, если для всех x выполняется условие: xjy и yjz Þ xjz или Ф
Диаграммы Хассе.
Рассмотрим отношение частичного порядка: “быть подмножеством“ на множестве-степени М={1,2}.
j=<F,M>, где
Ф={<{Æ},{Æ}>;<{Æ},{1}>;<{Æ},{
Выполнимость формулы алгебры логики
Все формулы алгебры логики делятся на три класс:
1. тождественно истинные или тавтологии:
2. тождественно ложные
Применение математической логики.
Спомощью алгебры логики можно:
· решать логические задачи;
· реализация технических устройств.
Спомощью алгебры логики м
Метод Квайна.
Алгоритм метода Квайна включает в себя следующие этапы:
1. Любая формула
Метод минимизирующих карт.
Алгоритм метода минимизирующих карт включает в себя следующие этапы:
1. Любая формула приводится к СДНФ.
2. Составляется таблица всевозможных сочетаний переменных.
3. Из
Метод минимизации с помощью карт Вейча.
Алгоритм метода карт Вейча включает в себя следующие этапы:
1. Любая формула приводится к СДНФ.
2. Составляется карта Вейча. Карта Вейча – это таблица всех возможн
Булевые функции и их свойства.
Булевой функцией называется функция n переменных, которая принимает значение 1 или 0, а так же ее аргументы тоже принимают значение 1 или 0.
Булевая фу
Функциональная полнота. Теорема Поста.
Функциональный набор логических функций - это такой набор функций, который позволяет любую функцию математической логики описать с помощью функций данного набор
Логика предикат.
Предикат - это сложное высказывание, в котором аргументы принимают значение и
Матрицей инцидентности
Матрица инцидентности - это матрица вершин и инцидентных им дуг.
Дуга инцидентна вершине, если эта дуга исходит или заходит в данную вер
Эйлеров граф.
Эйлеровой цепью называется цепь, проходящая по всем ребрам графа.
Эйлеровым циклом называется эйлеровая цепь, начинающаяся и заканчивающаяс
Множество внешней устойчивости графа
Множество внешней устойчивости – множество вершин, для которых выполняется одно из следующих правил:
1). Любая вершина входит в это множество
Ярусно-параллельная форма графов
Граф, не имеющий контуров, может быть представлен в ярусно-параллельной форме. Ярусно-параллельная форма – это такой вид графа, у которого в верхний нулевой ярус поме
Алгоритм приведения графа к ярусно-параллельной форме.
1. Составляется матрица смежности графа.
2. Матрица смежности просматривается в поисках нулевых столбцов. Вершины, которым соответствуют нулевые столбцы, помещаются в нулевой ярус.
Деревья и леса
Отделенными называются вершины, для которых не существует соединяющего эти вершины пути.
Неотделенными называются вершины, между которыми существу
Алгоритм получения дерева из графа
1. Выбирается любая вершина. Счетчик i принимаем равным 1 (i=1).
2. Если i = k, то дерево построено.
3. Если i ¹ k, то выбирается
ТЕОРИЯ АЛГОРИТМОВ
Алгоритм – это точное, понятное предписание о том, какие действия и в каком порядке должны быть выполнены, чтобы решить любую задачу из класса однотипных задач.
Функция-проекция
(4.3)
Правила преобразования функций
1. Правило
Машина Тьюринга
Если для решения некоторой массовой проблемы известен алгоритм, то для его реализации необходимо лишь четкое выполнение предписаний этого алгоритма. Автоматизм, необходимый при реализации алгоритма
Законы функционирования автоматов.
В зависимости от законов функционирования различают 3 вида автоматов:
1. Автоматы первого рода, или автоматы Мили:
Минимизация автоматов
Входным словом называется совокупность сигналов, поступающих на вход.
Выходным словом называются совокупность сигналов на выходе.
Алгоритм минимизации автомата Мили
1. По таблице выхода находятся состояния с одинаковыми выходными сигналами. Данные состояния объединяются в класс одноэквивалентных состояний. Проводится перекодировка.
2. По таблице перех
Переход от автомата Мура к автомату Мили
Переход от автомата Мура к автомату Мили заключается в построении таблицы выходов. Построение состоит в подстановке выходных сигналов, отмечающих состояния в отмеченной таблице пере
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
, если из i-той вершины исходит дуга в j – тую вершину; во всех остальных случаях 
(для удобства и наглядности на практике в матрице смежности нули не проставляются).
i–той вершины называется число дуг, заходящих в данную вершину.
i-той вершины называется число дуг, исходящих из данной вершины.
называется сумма полустепеней захода и исхода:
(3.2)
, если. в i-той вершине j-тое ребро образует петлю.
Новости и инфо для студентов